Does Adiabatic Quantum Optimization Truly Fail for NP-complete problems?

Abstract

It has been recently argued that adiabatic quantum optimization would fail in solving NP-complete problems because of the occurrence of exponentially small gaps due to crossing of local minima of the final Hamiltonian with its global minimum near the end of the adiabatic evolution. Using perturbation expansion, we analytically show that for the NP-hard problem of maximum independent set there always exist adiabatic paths along which no such crossings occur. Therefore, in order to prove that adiabatic quantum optimization fails for any NP-complete problem, one must prove that it is impossible to find any such path in polynomial time.

4 pages, version to appear in PRL

References in corpus (2)

• Quantum Adiabatic Brachistochrone
• Intrinsic geometry of quantum adiabatic evolution and quantum phase transitions

Cited by in corpus (36)

• Ising formulations of many NP problems
• Adiabatic Quantum Computing
• Perspectives of quantum annealing: Methods and implementations
• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• Adiabatic quantum algorithm for search engine ranking
• Digital Quantum Simulation of the Statistical Mechanics of a Frustrated Magnet
• Quantum annealing of the $p$-spin model under inhomogeneous transverse field driving
• Ground State Spin Logic
• Programmable Quantum Annealing Architectures with Ising Quantum Wires
• Quantum annealing with longitudinal bias fields
• Algorithmic approach to adiabatic quantum optimization
• An Integrated Programming and Development Environment for Adiabatic Quantum Optimization
• Elimination of Perturbative Crossings in Adiabatic Quantum Optimization
• The Effects of the Problem Hamiltonian Parameters on the Minimum Spectral Gap in Adiabatic Quantum Optimization
• Theorem on the existence of a nonzero energy gap in adiabatic quantum computation
• Quantum Programming of the Satisfiability Problem with Rydberg Atom Graphs
• Minimal Constraints in the Parity Formulation of Optimization Problems
• Disorder-assisted graph coloring on quantum annealers
• Phase transitions in the frustrated Ising ladder with stoquastic and nonstoquastic catalysts
• Bounding first-order quantum phase transitions in adiabatic quantum computing
• The quantum annealing gap and quench dynamics in the exact cover problem
• Optimized QUBO formulation methods for quantum computing
• Mapping NP-hard and NP-complete optimisation problems to Quadratic Unconstrained Binary Optimisation problems
• Quantum annealing sampling with a bias field
• Physical consequences of P$\ne$NP and the DMRG-annealing conjecture
• Adiabatic Quantum Programming: Minor Embedding With Hard Faults
• Iterative classical superadiabatic algorithm for combinatorial optimization
• Asymptotic Exceptional Steady States in Dissipative Dynamics
• Fighting Exponentially Small Gaps by Counterdiabatic Driving
• The anomalously slow dynamics of inhomogeneous quantum annealing
• Energy Spectrum and Exact Cover in an Extended Quantum Ising Model
• Classical Simulation of Quantum Adiabatic Algorithms using Mathematica on GPUs
• Hard combinatorial problems and minor embeddings on lattice graphs
• Entanglement Trajectory and its Boundary
• An Adiabatic Quantum Algorithm for Determining Gracefulness of A Graph
• Improving adiabatic quantum factorization via chopped random-basis optimization