Hybrid divide-and-conquer approach for tree search algorithms
arXiv:2007.07040 · doi:10.22331/q-2023-03-23-959
Abstract
One of the challenges of quantum computers in the near- and mid- term is the limited number of qubits we can use for computations. Finding methods that achieve useful quantum improvements under size limitations is thus a key question in the field. In this vein, it was recently shown that a hybrid classical-quantum method can help provide polynomial speed-ups to classical divide-and-conquer algorithms, even when only given access to a quantum computer much smaller than the problem itself. In this work, we study the hybrid divide-and-conquer method in the context of tree search algorithms, and extend it by including quantum backtracking, which allows better results than previous Grover-based methods. Further, we provide general criteria for polynomial speed-ups in the tree search context, and provide a number of examples where polynomial speed ups, using arbitrarily smaller quantum computers, can be obtained. We provide conditions for speedups for the well known algorithm of DPLL, and we prove threshold-free speed-ups for the PPSZ algorithm (the core of the fastest exact Boolean satisfiability solver) for well-behaved classes of formulas. We also provide a simple example where speed-ups can be obtained in an algorithm-independent fashion, under certain well-studied complexity-theoretical assumptions. Finally, we briefly discuss the fundamental limitations of hybrid methods in providing speed-ups for larger problems.
arXiv comment48 pages, 16 figures
References in corpus (17)
- Semiclassical Fourier Transform for Quantum Computation
- Trading classical and quantum computational resources
- Simulating Large Quantum Circuits on a Small Quantum Computer
- Fixed-point quantum search with an optimal number of queries
- Quantum Computing based Hybrid Solution Strategies for Large-scale Discrete-Continuous Optimization Problems
- Quantum phase estimation of multiple eigenvalues for small-scale (noisy) experiments
- Quantum-assisted Helmholtz machines: A quantum-classical deep learning framework for industrial datasets in near-term devices
- Applying quantum algorithms to constraint satisfaction problems
- Computational speedups using small quantum devices
- Quantum speedup of the Travelling Salesman Problem for bounded-degree graphs
- Quantum algorithm for tree size estimation, with applications to backtracking and 2-player games
- A hybrid algorithm framework for small quantum computers with application to finding Hamiltonian cycles
- Small quantum computers and large classical data sets
- Improved quantum backtracking algorithms using effective resistance estimates
- Dequantizing read-once quantum formulas
- Practical implementation of a quantum backtracking algorithm
- PPSZ is better than you think