Back to Search
Start Over
Quantum speedup for combinatorial optimization with flat energy landscapes
- Publication Year :
- 2023
-
Abstract
- Designing quantum algorithms with a speedup over their classical analogs is a central challenge in quantum information science. Motivated by recent experimental observations of a superlinear quantum speedup in solving the Maximum Independent Set problem on certain unit-disk graph instances [Ebadi et al., Science 376, 6598 (2022)], we develop a theoretical framework to analyze the relative performance of the optimized quantum adiabatic algorithm and a broad class of classical Markov chain Monte Carlo algorithms. We outline conditions for the quantum adiabatic algorithm to achieve a quadratic speedup on hard problem instances featuring flat low-energy landscapes and provide example instances with either a quantum speedup or slowdown. We then introduce an additional local Hamiltonian with no sign problem to the optimized adiabatic algorithm to achieve a quadratic speedup over a wide class of classical simulated annealing, parallel tempering, and quantum Monte Carlo algorithms in solving these hard problem instances. Finally, we use this framework to analyze the experimental observations.<br />9+27 pages, 5+8 figures
Details
- Language :
- English
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....73d8d9f9bfd09bd7c2721a9e2b972f97