Quantum divide and conquer

10/12/2022
by   Andrew M. Childs, et al.
0

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^aux(n), to give a recurrence relation C(n) ≤ a C(n/b) + C^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) ≤√(a) C_Q(n/b) + O(C^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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset