The effect of local minima on quantum adiabatic optimization

We present a perturbative method to estimate the spectral gap for adiabatic quantum optimization, based on the structure of the energy levels in the problem Hamiltonian. We show that, for problems that have an exponentially large number of local minima close to the global minimum, the gap becomes exponentially small making the computation time exponentially long. The quantum advantage of adiabatic quantum computation may then be accessed only via the local adiabatic evolution, which requires phase coherence throughout the evolution and knowledge of the spectrum. Such problems, therefore, are not suitable for adiabatic quantum computation.We present a perturbative method to estimate the spectral gap for adiabatic quantum optimization, based on the structure of the energy levels in the problem Hamiltonian. We show that, for problems that have an exponentially large number of local minima close to the global minimum, the gap becomes exponentially small making the computation time exponentially long. The quantum advantage of adiabatic quantum computation may then be accessed only via the local adiabatic evolution, which requires phase coherence throughout the evolution and knowledge of the spectrum. Such problems, therefore, are not suitable for adiabatic quantum computation.

arXiv:0709.0528Physical Review LettersApr 4, 200836 citations

Algorithmic approach to adiabatic quantum optimization

Neil G. Dickson, M. H. S. Amin

It is believed that the presence of anticrossings with exponentially small gaps between the lowest two energy levels of the system Hamiltonian can render adiabatic quantum optimization inefficient. Here, we present a simple adiabatic quantum algorithm designed to eliminate exponentially small gaps caused by anticrossings between eigenstates that correspond with the local and global minima of the problem Hamiltonian. In each iteration of the algorithm, information is gathered about the local minima that are reached after passing the anticrossing nonadiabatically. This information is then used to penalize pathways to the corresponding local minima by adjusting the initial Hamiltonian. This is repeated for multiple clusters of local minima as needed. We generate 64-qubit random instances of the maximum independent set problem, skewed to be extremely hard, with between ${10}^{5}$ and ${10}^{6}$ highly degenerate local minima. Using quantum Monte Carlo simulations, it is found that the algorithm can trivially solve all of the instances in $\ensuremath{\sim}$10 iterations.It is believed that the presence of anticrossings with exponentially small gaps between the lowest two energy levels of the system Hamiltonian can render adiabatic quantum optimization inefficient. Here, we present a simple adiabatic quantum algorithm designed to eliminate exponentially small gaps caused by anticrossings between eigenstates that correspond with the local and global minima of the problem Hamiltonian. In each iteration of the algorithm, information is gathered about the local minima that are reached after passing the anticrossing nonadiabatically. This information is then used to penalize pathways to the corresponding local minima by adjusting the initial Hamiltonian. This is repeated for multiple clusters of local minima as needed. We generate 64-qubit random instances of the maximum independent set problem, skewed to be extremely hard, with between ${10}^{5}$ and ${10}^{6}$ highly degenerate local minima. Using quantum Monte Carlo simulations, it is found that the algorithm can trivially solve all of the instances in $\ensuremath{\sim}$10 iterations.

arXiv:1108.3303Physical Review AMar 5, 201240 citations

Accurate Variational Description of Adiabatic Quantum Optimization

Giuseppe Carleo, Bela Bauer, Matthias Troyer

Bulletin of the American Physical SocietyMar 14, 20160 citations

Dimensionality reduction for adiabatic quantum optimizer in presence of local disorder

Gian Giacomo Guerreschi, Salvatore Mandr `a, Al 'an Aspuru-Guzik

Bulletin of the American Physical SocietyMar 4, 20150 citations

Adiabatic optimization without local minima

Michael Jarret, Stephen P. Jordan

Several previous works have investigated the circumstances under which quantum adiabatic optimization algorithms can tunnel out of local energy minima that trap simulated annealing or other classical local search algorithms. Here we investigate the even more basic question of whether adiabatic optimization algorithms always succeed in polynomial time for trivial optimization problems in which there are no local energy minima other than the global minimum. Surprisingly, we find a counterexample in which the potential is a single basin on a graph, but the eigenvalue gap is exponentially small as a function of the number of vertices. In this counterexample, the ground state wavefunction consists of two ``lobes'' separated by a region of exponentially small amplitude. Conversely, we prove if the ground state wavefunction is single-peaked then the eigenvalue gap scales at worst as one over the square of the number of vertices.Several previous works have investigated the circumstances under which quantum adiabatic optimization algorithms can tunnel out of local energy minima that trap simulated annealing or other classical local search algorithms. Here we investigate the even more basic question of whether adiabatic optimization algorithms always succeed in polynomial time for trivial optimization problems in which there are no local energy minima other than the global minimum. Surprisingly, we find a counterexample in which the potential is a single basin on a graph, but the eigenvalue gap is exponentially small as a function of the number of vertices. In this counterexample, the ground state wavefunction consists of two ``lobes'' separated by a region of exponentially small amplitude. Conversely, we prove if the ground state wavefunction is single-peaked then the eigenvalue gap scales at worst as one over the square of the number of vertices.

Quantum Information and ComputationMar 1, 20153 citations

{10}^{5}

and

{10}^{6}

highly degenerate local minima. Using quantum Monte Carlo simulations, it is found that the algorithm can trivially solve all of the instances in $\ensuremath{\sim}$10 iterations.