Exponential complexity of an adiabatic algorithm for an NP-complete problem

Abstract

We prove an analytical expression for the size of the gap between the ground and the first excited state of quantum adiabatic algorithm for the 3-satisfiability, where the initial Hamiltonian is a projector on the subspace complementary to the ground state. For large problem sizes the gap decreases exponentially and as a consequence the required running time is also exponential.

5 pages, 2 figures; v3. published version

References in corpus (10)

• Quantum Mechanics helps in searching for a needle in a haystack
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Quantum Search by Local Adiabatic Evolution
• The Entropy of the K-Satisfiability Problem
• Quantum search without entanglement
• Adiabatic Quantum Computing for Random Satisfiability Problems
• Scaling of running time of quantum adiabatic algorithm for propositional satisfiability
• Quantum Register Physics
• A Random Matrix Model of Adiabatic Quantum Computing
• Eigenlevel statistics of the quantum adiabatic algorithm

Cited by in corpus (42)

• Adiabatic Quantum Computing
• Anderson localization casts clouds over adiabatic quantum optimization
• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• First Order Quantum Phase Transition in Adiabatic Quantum Computation
• Decoherence in a scalable adiabatic quantum computer
• Exponential Complexity of the Quantum Adiabatic Algorithm for certain Satisfiability Problems
• Adiabatic quantum algorithms as quantum phase transitions: first versus second order
• General error estimate for adiabatic quantum computing
• Does Adiabatic Quantum Optimization Truly Fail for NP-complete problems?
• Quantum annealing: the fastest route to quantum computation?
• QUARK: A Framework for Quantum Computing Application Benchmarking
• An introduction to quantum annealing
• Algorithmic approach to adiabatic quantum optimization
• Effect of Local Minima on Adiabatic Quantum Optimization
• Designing Quantum Annealing Schedules using Bayesian Optimization
• Analog Nature of Quantum Adiabatic Unstructured Search
• Adiabatic preparation without Quantum Phase Transitions
• Quasienergy anholonomy and its application to adiabatic quantum state manipulation
• Adiabatic Quantum Computation with a 1D projector Hamiltonian
• Dynamical properties across a quantum phase transition in the Lipkin-Meshkov-Glick model
• Asymptotic expansion for inverse moments of binomial and Poisson distributions
• Quantum heuristic algorithm for traveling salesman problem
• New anatomy of quantum holonomy
• Elimination of Perturbative Crossings in Adiabatic Quantum Optimization
• Local Hamiltonians in Quantum Computation
• Adiabatic quantum optimization in presence of discrete noise: Reducing the problem dimensionality
• Deep recurrent networks predicting the gap evolution in adiabatic quantum computing
• A comparison between D-wave and a classical approximation algorithm and a heuristic for computing the ground state of an Ising spin glass
• Enhancing quantum annealing performance by a degenerate two-level system
• Adiabatic quantum computation along quasienergies
• Decoherence in a dynamical quantum phase transition
• Why adiabatic quantum annealing is unlikely to yield speed-up
• Probing nonlinear adiabatic paths with a universal integrator
• Adiabatic Computation - A Toy Model
• Limitations of some simple adiabatic quantum algorithms
• Inverse moments of univariate discrete distributions via the Poisson expansion
• Discriminating Non-Isomorphic Graphs with an Experimental Quantum Annealer
• Quantum Phase Transition in Fully-Connected Quantum Wajnflasz-Pick Model
• Unstructured Adiabatic Quantum Optimization: Optimality with Limitations
• Majorization in Quantum Adiabatic Algorithms
• Bounding Run-Times of Local Adiabatic Algorithms
• Entanglement Trajectory and its Boundary