论文标题
量子分裂和征服
Quantum divide and conquer
论文作者
论文摘要
在经典算法设计中广泛使用的划分框架框架将大小$ n $的问题分解为较小的子问题（例如，每个尺寸$ n/b $的$ a $ a $ a $ a copies auxiliary auxilariary auxiliary of COSS $ c^{\ textrm {aux} n）$ c^remention $ reciant y reciration r reciant c（ C（n/b） + c^{\ textrm {aux}}（n）$$用于经典复杂性$ c（n）$。我们描述了一个量子划分的框架框架，在某些情况下，该框架产生了类似的复发关系$$ c_q（n）\ leq \ sqrt {a} \，c_q（n/b） + o（c^{\ textrm {aux}} _ q（n）_ q（n）_ q（n））我们应用此框架来获得各种字符串问题的近乎最佳的量子查询复杂性，例如（i）识别普通语言； （ii）字符串旋转和字符串后缀的决策版本； （iii）最长增加子序列和（iv）最长的常见子序列的自然参数化版本。
The divide-and-conquer framework, used extensively in classical algorithm design, recursively breaks a problem of size $n$ into smaller subproblems (say, $a$ copies of size $n/b$ each), along with some auxiliary work of cost $C^{\textrm{aux}}(n)$, to give a recurrence relation $$C(n) \leq a \, C(n/b) + C^{\textrm{aux}}(n)$$ for the classical complexity $C(n)$. We describe a quantum divide-and-conquer framework that, in certain cases, yields an analogous recurrence relation $$C_Q(n) \leq \sqrt{a} \, C_Q(n/b) + O(C^{\textrm{aux}}_Q(n))$$ that characterizes the quantum query complexity. We apply this framework to obtain near-optimal quantum query complexities for various string problems, such as (i) recognizing regular languages; (ii) decision versions of String Rotation and String Suffix; and natural parameterized versions of (iii) Longest Increasing Subsequence and (iv) Longest Common Subsequence.
