In this work, we initiate a systematic study of the time complexity of quantum divide and conquer (QD&C) algorithms for classical problems, and propose a general framework for their analysis. We establish generic conditions under which search and minimization problems with classical divide and conquer algorithms are amenable to quantum speedup, and apply these theorems to various problems involving strings, integers, and geometric objects. These include Longest Distinct Substring, Klee's Coverage, several optimization problems on stock transactions, and k-Increasing Subsequence. For most of these problems our quantum time upper bounds match the quantum query lower bounds, up to polylogarithmic factors. We give a structured framework for describing and classifying a wide variety of QD&C algorithms so that quantum speedups can be more easily identified and applied, and prove general statements on QD&C time complexity covering a range of cases, accounting for the time required for all operations. In particular, we explicitly account for memory access operations in the commonly used QRAM (read-only) and QRAG (read-write) models, which are assumed to take unit time in the query model, and which require careful analysis when involved in recursion. Our generic QD&C theorems have several nice features. 1) To apply them, it suffices to come up with a classical divide and conquer algorithm satisfying the conditions of the theorem. The quantization of the algorithm is then completely handled by the theorem. This can make it easier to find applications which admit a quantum speedup, and contrast with dynamic programming algorithms which can be difficult to quantize due to their highly sequential nature. 2) As these theorems give bounds on time complexity, they can be applied to a greater range of problems than those based on query complexity, e.g., where the best-known quantum algorithms require super-linear time. 3) It can handle minimization problems as well as boolean functions, which allows us to improve on the query complexity result of Childs et al. [Childs et al., 2025] for k-Increasing Subsequence by a logarithmic factor.
In this work, we initiate a systematic study of the time complexity of quantum divide and conquer (QD&C) algorithms for classical problems, and propose a general framework for their analysis. We establish generic conditions under which search and minimization problems with classical divide and conquer algorithms are amenable to quantum speedup, and apply these theorems to various problems involving strings, integers, and geometric objects. These include Longest Distinct Substring, Klee's Coverage, several optimization problems on stock transactions, and k-Increasing Subsequence. For most of these problems our quantum time upper bounds match the quantum query lower bounds, up to polylogarithmic factors. We give a structured framework for describing and classifying a wide variety of QD&C algorithms so that quantum speedups can be more easily identified and applied, and prove general statements on QD&C time complexity covering a range of cases, accounting for the time required for all operations. In particular, we explicitly account for memory access operations in the commonly used QRAM (read-only) and QRAG (read-write) models, which are assumed to take unit time in the query model, and which require careful analysis when involved in recursion. Our generic QD&C theorems have several nice features. 1) To apply them, it suffices to come up with a classical divide and conquer algorithm satisfying the conditions of the theorem. The quantization of the algorithm is then completely handled by the theorem. This can make it easier to find applications which admit a quantum speedup, and contrast with dynamic programming algorithms which can be difficult to quantize due to their highly sequential nature. 2) As these theorems give bounds on time complexity, they can be applied to a greater range of problems than those based on query complexity, e.g., where the best-known quantum algorithms require super-linear time. 3) It can handle minimization problems as well as boolean functions, which allows us to improve on the query complexity result of Childs et al. [Childs et al., 2025] for k-Increasing Subsequence by a logarithmic factor.
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 \(\begin{equation*} C(n) \le a \, C(n/b) + C^{\mathrm{aux}}(n) \end{equation*}\) for the classical complexity C(n) . We describe a quantum divide-and-conquer framework that, in certain cases, yields an analogous recurrence relation \(\begin{equation*} C_Q(n) \le \sqrt {a} \, C_Q(n/b) + O(C^{\mathrm{aux}}_Q(n)) \end{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 Σ∗20∗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.
We study quantum algorithms for several fundamental string problems, including Longest Common Substring, Lexicographically Minimal String Rotation, and Longest Square Substring. These problems have been widely studied in the stringology literature since the 1970s, and are known to be solvable by near-linear time classical algorithms. In this work, we give quantum algorithms for these problems with near-optimal query complexities and time complexities. Specifically, we show that: Longest Common Substring can be solved by a quantum algorithm in Õ(n2/3) time, improving upon the recent Õ(n5/6)-time algorithm by Le Gall and Seddighin (2020). Our algorithm uses the MNRS quantum walk framework, together with a careful combination of string synchronizing sets (Kempa and Kociumaka, 2019) and generalized difference covers. Lexicographically Minimal String Rotation can be solved by a quantum algorithm in n1/2 + o(1) time, improving upon the recent Õ(n3/4)-time algorithm by Wang and Ying (2020). We design our algorithm by first giving a new classical divide-and-conquer algorithm in near-linear time based on exclusion rules, and then speeding it up quadratically using nested Grover search and quantum minimum finding. Longest Square Substring can be solved by a quantum algorithm in time. Our algorithm is an adaptation of the algorithm by Le Gall and Seddighin (2020) for the Longest Palindromic Substring problem, but uses additional techniques to overcome the difficulty that binary search no longer applies. Our techniques naturally extend to other related string problems, such as Longest Repeated Substring, Longest Lyndon Substring, and Minimal Suffix.
Abstract We study quantum algorithms for several fundamental string problems, including Longest Common Substring, Lexicographically Minimal String Rotation, and Longest Square Substring. These problems have been widely studied in the stringology literature since the 1970s, and are known to be solvable by near-linear time classical algorithms. In this work, we give quantum algorithms for these problems with near-optimal query complexities and time complexities. Specifically, we show that: Longest Common Substring can be solved by a quantum algorithm in O~(n2/3) O ~ ( n 2 / 3 ) time, improving upon the recent O~(n5/6) O ~ ( n 5 / 6 ) -time algorithm by Le Gall and Seddighin (in: Proceedings of the 13th innovations in theoretical computer science conference (ITCS 2022), pp 97:1–97:23, 2022. https://doi.org/10.4230/LIPIcs.ITCS.2022.97 ). Our algorithm uses the MNRS quantum walk framework, together with a careful combination of string synchronizing sets (Kempa and Kociumaka, in: Proceedings of the 51st annual ACM SIGACT symposium on theory of computing (STOC 2019), ACM, pp 756–767, 2019. https://doi.org/10.1145/3313276.3316368 ) and generalized difference covers. Lexicographically Minimal String Rotation can be solved by a quantum algorithm in n1/2+o(1) n 1 / 2 + o ( 1 ) time, improving upon the recent O~(n3/4) O ~ ( n 3 / 4 ) -time algorithm by Wang and Ying (in: Quantum algorithm for lexicographically minimal string rotation. CoRR, 2020. arXiv:2012.09376 ). We design our algorithm by first giving a new classical divide-and-conquer algorithm in near-linear time based on exclusion rules, and then speeding it up quadratically using nested Grover search and quantum minimum finding. Longest Square Substring can be solved by a quantum algorithm in O~(n) O ~ ( n ) time. Our algorithm is an adaptation of the algorithm by Le Gall and Seddighin (2022) for the Longest Palindromic Substring problem, but uses additional techniques to overcome the difficulty that binary search no longer applies. Our techniques naturally extend to other related string problems, such as Longest Repeated Substring, Longest Lyndon Substring, and Minimal Suffix.
We study quantum algorithms for several fundamental string problems, including Longest Common Substring, Lexicographically Minimal String Rotation, and Longest Square Substring. These problems have been widely studied in the stringology literature since the 1970s, and are known to be solvable by near-linear time classical algorithms. In this work, we give quantum algorithms for these problems with near-optimal query complexities and time complexities. Specifically, we show that: - Longest Common Substring can be solved by a quantum algorithm in O~(n2/3) time, improving upon the recent O~(n5/6)-time algorithm by Le Gall and Seddighin (2020). Our algorithm uses the MNRS quantum walk framework, together with a careful combination of string synchronizing sets (Kempa and Kociumaka, 2019) and generalized difference covers. - Lexicographically Minimal String Rotation can be solved by a quantum algorithm in n1/2+o(1) time, improving upon the recent O~(n3/4)-time algorithm by Wang and Ying (2020). We design our algorithm by first giving a new classical divide-and-conquer algorithm in near-linear time based on exclusion rules, and then speeding it up quadratically using nested Grover search and quantum minimum finding. - Longest Square Substring can be solved by a quantum algorithm in O~(n) time. Our algorithm is an adaptation of the algorithm by Le Gall and Seddighin (2020) for the Longest Palindromic Substring problem, but uses additional techniques to overcome the difficulty that binary search no longer applies. Our techniques naturally extend to other related string problems, such as Longest Repeated Substring, Longest Lyndon Substring, and Minimal Suffix.
Many problems that can be solved in quadratic time have bit-parallel speed-ups with factor w, where w is the computer word size. For example, edit distance of two strings of length n can be solved in O(n2/w) time. In a reasonable classical model of computation, one can assume w=Θ(logn). There are conditional lower bounds for such problems stating that speed-ups with factor nε for any ε>0 would lead to breakthroughs in complexity theory. However, these conditional lower bounds do not cover quantum models of computing. Indeed, Boroujeni et al. (J. ACM, 2021) showed that edit distance can be approximated within a factor 3 in sub-quadratic time O(n1.81) using quantum computing. They also showed that, in their chosen model of quantum computing, the approximation factor cannot be improved using sub-quadractic time. To break through the aforementioned classical conditional lower bounds and this latest quantum lower bound, we enrich the model of computation with a quantum random access memory (QRAM), obtaining what we call the word QRAM model. Under this model, we show how to convert the bit-parallelism of quadratic time solvable problems into quantum algorithms that attain speed-ups with factor n. The technique we use is simple and general enough to apply to many bit-parallel algorithms that use Boolean logics and bit-shifts. To apply it to edit distance, we first show that the famous O(n2/w) time bit-parallel algorithm of Myers (J. ACM, 1999) can be adjusted to work without arithmetic + operations. As a direct consequence of applying our technique to this variant, we obtain linear time edit distance algorithm under the word QRAM model for constant alphabet. We give further results on a restricted variant of the word QRAM model to give more insights to the limits of the model.
Quantum Divide-and-Conquer for the Traveling Salesman Problem: Surpassing the 2n Barrier
The traveling salesman problem (TSP) is a classic NP-hard problem. Held--Karp dynamic programming~\cite{held1962dynamic, bellman1962dynamic} solves it exactly in O(n22n) time, a barrier that has stood for over six decades. Whether quantum computing can surpass O∗(2n) is a central open question. The authors of~\cite{ambainis2019quantum}\ (SODA~2019) claimed a query complexity of O∗(1.727n), but we identify a structural counting error: when corrected, their scheme requires Ω∗(2n) queries and offers no advantage over classical Held--Karp. We design a quantum divide-and-conquer framework: partition n-vertex set into k subsets, classically precompute shortest paths within each, then search over all k-partitions via quantum minimum finding. We prove k=3 achieves O∗(1.890n), and k=4 attains the global optimum O∗(1.866n), the first quantum algorithm to surpass O∗(2n) for general TSP. To convert the query bound into a time-complexity advantage, we overcome the oracle-construction bottleneck by preparing a set partition state, requiring O(n2) gates and O(n) depth. Leveraging structured state preparation, we achieve a total time complexity of O∗(1.866n). Qiskit simulations on n=6,7 achieve 98.9% and 100% accuracy.