Quantum divide and conquer

Abstract

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^{\text{aux}}(n)$, to give a recurrence relation $$C(n)\le aC(n/b)+C^{\text{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)\le \sqrt{a}{C}_Q(n/b)+O(C_Q^{\text{aux}}(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.

arXiv comment24 pages, 8 figures

References in corpus (8)

• Quantum Amplitude Amplification and Estimation
• Negative weights make adversaries stronger
• Quantum query complexity of state conversion
• Quantum Algorithms for Element Distinctness
• Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function
• Span-program-based quantum algorithm for evaluating formulas
• Span programs and quantum algorithms for st-connectivity and claw detection
• Quantum Adversary (Upper) Bound

Cited by in corpus (2)

• Error mitigation and circuit division for early fault-tolerant quantum phase estimation
• Double-Ended Palindromic Trees in Linear Time