Quantum Divide and Conquer

Speaker

Matt Kovacs-Deak April 14, 2023.

Abstract

The divide-and-conquer framework, used extensively in classical algorithm design, recursively breaks a problem of size n into smaller subproblems (say, a many copies of size n/b each), along with some auxiliary work of cost T_aux(n), to give a recurrence relation T(n) ≤ a T(n/b) + T_aux(n) for the classical complexity T(n). In this talk I will describe a quantum divide-and-conquer framework that, in certain cases, yields an analogous recurrence relation Q(n) ≤ a sqrt(Q(n/b)) + O(Q_aux(n)) that characterizes the quantum query complexity Q(n). Using this framework near-optimal quantum query complexities can be derived 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.