2023/06/22 by Madelyn Cain, Cain, Madelyn, Sambuddha Chattopadhyay +9 · 2 citations
Computer Science · Materials Science · Physics and Astronomy · #Advanced Chemical Physics Studies #FOS: Physical sciences #Machine Learning in Materials Science #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #Statistical Mechanics (cond-mat.stat-mech) #Strongly Correlated Electrons (cond-mat.str-el)
paper · pdf · doi:10.48550/arxiv.2306.13123
openalex publication_date 2023/06/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.