Abstract
This paper presents a systematic framework for translating classical divide-and-conquer (D&C) algorithms into quantum counterparts, achieving near-quadratic speedups for several fundamental problems. By formalizing D&C into four distinct stages—Create, Conquer, Complete, and Combine—the authors establish generic conditions under which quantum search and optimization can be leveraged to reduce time complexity in domains ranging from string processing to computational geometry.
Introduction
Divide and conquer is a cornerstone of classical algorithm design, powering essential tools like Mergesort and the Fast Fourier Transform. While quantum algorithms often exploit recursive structures, research has historically focused on query complexity (the number of data accesses). However, for practical engineering, time complexity—which includes total operations and memory access—is the critical metric.
Translating D&C to the quantum realm is non-trivial due to the probabilistic nature of quantum subroutines. When nested recursively, small errors can accumulate and compromise the final result. This paper introduces the mathematical framework necessary to manage these errors and provides a general recipe for achieving quantum speedups in time complexity.
The "Four Cs" Framework
The authors propose a decomposition of any D&C algorithm into four functional steps: Create, Conquer, Complete, and Combine. This formalization allows for a targeted application of quantum subroutines.
The core insight is that if the Combine step (integrating subproblem solutions) or the Complete step (computing additional info) involves a search or optimization task, it is amenable to quantum speedup via Grover Search or Quantum Minimum Finding. For example, replacing a linear-time classical search with a square-root-time quantum search can significantly improve the efficiency of the entire recursion tree.
Implementation and Memory Models
To address the "error composition" problem, the authors suggest a bottom-up iterative approach rather than a direct recursive translation. This method is often easier to analyze and implement within a quantum circuit. Furthermore, the analysis is conducted under two quantum memory models:
- QRAM (Quantum Random Access Memory): Read-only memory where addresses can be in superposition.
- QRAG (Quantum Random Access Gate): Read-write memory supporting superposed addresses.
Key Results and Speedups
The paper demonstrates significant asymptotic speedups across several computational problems. In many cases, the quantum time upper bounds achieved by this framework match known quantum query lower bounds, suggesting near-optimality.
Notably, problems like the Single Stock Single Transaction (SSST) and Longest Distinct Substring see substantial improvements. The framework also reveals nuanced differences in the quantum "fine-grained" complexity of problems that are classically considered equivalent, such as those in the All-Pairs Shortest Paths (APSP) class.
Limitations and Future Work
While powerful, the framework requires D&C steps to meet specific "simplicity" criteria, meaning not every classical algorithm can be easily quantized. Additionally, the results rely on the future availability of robust QRAM/QRAG hardware. Future research may focus on relaxing these technical constraints and exploring the exact quantum query complexity of more complex problems like the Maximum 4-Combination.
Summary updated