Answers are grounded in this paper and cite their sources.
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ᵃᵘˣ(n)\) , to give a recurrence relation \({equation*} C(n) ≤ a \, C(n/b) + Cᵃᵘˣ(n) {equation*}\) for the classical complexity \(C(n)\) . We describe a quantum divide-and-conquer framework that, in certain cases, yields an analogous recurrence relation \({equation*} C_Q(n) ≤ √a \, C_Q(n/b) + O(Cᵃᵘˣ_Q(n)) {equation*}\) 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 \(Σ ^* 2 0^* 2 Σ ^*\) over the alphabet \(Σ = 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.
No takes yet. Share an insight, caveat, or question.
Childs et al. (2025) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: