Determining the Complexity of the Quantum Adiabatic Algorithm using Quantum Monte Carlo Simulations
Abstract
Quantum Monte Carlo simulations, supplemented by diagonalization, were used to see how efficiently a quantum computer could solve optimization problems using the quantum adiabatic algorithm (QAA). Comparisons were made with a classical heuristic algorithm, WalkSAT. A preliminary study was also made to see if the QAA could solve the graph isomorphism problem. Several optimization problems were considered. Those of the K-SAT type, which, in mean field theory have a "random first order transition" , were found to have an exponentially small energy gap at the quantum phase transition. We also studied a spin glass problem in which the gap was found to be exponentially small not at the phase transition but beyond it in the "quantum spin glass" phase. These results show that the simplest implementation of the QAA would require an amount of computer time which increases exponentially with problem size. For the future, it would be useful to test whether better results could be obtained by considering cleverer paths in "Hamiltonian space", and by considering different types of problem where the absolute ground state is not needed, only a good approximation to it.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 18, 2012
- Accession Number
- ADA579742
Entities
People
- Adam P. Young
Organizations
- University of California, Santa Cruz