Designing quantum algorithms with a speedup over their classical analogues is a central challenge in quantum information science. In this talk, we present experimental observations of a superlinear quantum speedup over classical simulated annealing in solving certain instances of the Maximum Independent Set problem.1 Motivated by these experimental results, we then describe 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 gives sufficient conditions for the quantum adiabatic algorithm to achieve a quadratic speedup on hard problem instances featuring flat low-energy landscapes. On instances where the speedup is not achieved, we modify 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 apply this framework to analyze the experimental observations.
References:
1Ebadiet al., Science 376, 6598 (2022)
Authors: M. Cain1, S. Chattopadhyay1, J.-G. Liu1,2, R. Samajdar3,4, H. Pichler5,6, M. D. Lukin1
1Department of Physics, Harvard University, USA
2Advanced Materials Thrust, Hong Kong University of Science and Technology (Guangzhou), China
3Department of Physics, Princeton University, USA
4Princeton Center for Theoretical Science, Princeton University, USA
5Institute for Theoretical Physics, University of Innsbruck, Austria
6Institute for Quantum Optics and Quantum Information, Austrian Academy of Sciences, Austria
