Algorithmic approach to adiabatic quantum optimization

Abstract

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 non-adiabatically. 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 the instances in ~10 iterations.

7 pages, 3 figures

References in corpus (4)

• Simple proof of equivalence between adiabatic quantum computation and the circuit model
• Adiabatic approximation in open quantum systems
• A solvable model of quantum random optimization problems
• Classical and Quantum Annealing in the Median of Three Satisfiability

Cited by in corpus (25)

• Perspectives of quantum annealing: Methods and implementations
• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• Quantum annealing of the $p$-spin model under inhomogeneous transverse field driving
• Quantum annealing with longitudinal bias fields
• Experimental demonstration of perturbative anticrossing mitigation using non-uniform driver Hamiltonians
• Degeneracy, degree, and heavy tails in quantum annealing
• An Integrated Programming and Development Environment for Adiabatic Quantum Optimization
• Advantages of Unfair Quantum Ground-State Sampling
• Robust Classification with Adiabatic Quantum Optimization
• Variationally Scheduled Quantum Simulation
• Continuous-Time Quantum Algorithms for Unstructured Problems
• Hamiltonian sparsification and gap-simulations
• Fluctuation guided search in quantum annealing
• VanQver: The Variational and Adiabatically Navigated Quantum Eigensolver
• Phase transitions in the frustrated Ising ladder with stoquastic and nonstoquastic catalysts
• The quantum annealing gap and quench dynamics in the exact cover problem
• Counterdiabatic Driving with Performance Guarantees
• Unraveling Reverse Annealing: A Study of D-Wave Quantum Annealers
• Eigenvalue-invariant transformation of Ising problem for anti-crossing mitigation in quantum annealing
• Improving nonstoquastic quantum annealing with spin-reversal transformations
• Quantum annealing sampling with a bias field
• The effect of quantum fluctuations on the coloring of random graphs
• Adiabatic Quantum Programming: Minor Embedding With Hard Faults
• Iterative classical superadiabatic algorithm for combinatorial optimization
• The anomalously slow dynamics of inhomogeneous quantum annealing