.png){kind=icon}
.png){kind=icon}
Return
Quantum Divide and Conquer
.png){kind=icon}
PRE
AI
DOI：10.1145/3723884.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 Caux(n), to give a recurrence relation C(n) <= a C(n/b) + Caux(n) for the classical complexity C(n). We describe a quantum divide-and-conquer framework that, in certain cases, yields an analogous recurrence relation CQ(n) <= root aCQ(n/b) + O(Caux 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 the regular language Sigma & lowast;20 & lowast;2 Sigma & lowast; over the alphabet Sigma = {0, 1, 2}; (ii) decision versions of String Rotation and String Suffix; and natural parameterized versions of (iii) Longest Increasing Subsequence and (iv) Longest Common Subsequence.
Keywords:
Quantum computing
quantum query complexity
divide and conquer
string algorithms
regular languages
Journal
A
IF:
6.8
Papers:
539
Citations:
508