@article {3138, title = {Quantum divide and conquer}, year = {2022}, month = {10/12/2022}, 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 Caux(n), to give a recurrence relation
C(n)\≤aC(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)\≤a\−\−\√CQ(n/b)+O(CauxQ(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.

}, keywords = {Data Structures and Algorithms (cs.DS), FOS: Computer and information sciences, FOS: Physical sciences, Quantum Physics (quant-ph)}, doi = {10.48550/ARXIV.2210.06419}, url = {https://arxiv.org/abs/2210.06419}, author = {Andrew M. Childs and Kothari, Robin and Kovacs-Deak, Matt and Sundaram, Aarthi and Wang, Daochen} }