Scaling of running time of quantum adiabatic algorithm for propositional satisfiability
arXiv:quant-ph/0502077 · doi:10.1103/PhysRevA.71.062305
Abstract
We numerically study quantum adiabatic algorithm for the propositional satisfiability. A new class of previously unknown hard instances is identified among random problems. We numerically find that the running time for such instances grows exponentially with their size. Worst case complexity of quantum adiabatic algorithm therefore seems to be exponential.
7 pages
References in corpus (4)
Cited by in corpus (20)
- First Order Quantum Phase Transition in Adiabatic Quantum Computation
- 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
- Exponential complexity of an adiabatic algorithm for an NP-complete problem
- Adiabatic Quantum Algorithms for the NP-Complete Maximum-Weight Independent Set, Exact Cover and 3SAT Problems
- Effect of Local Minima on Adiabatic Quantum Optimization
- Adiabatic preparation without Quantum Phase Transitions
- Assessment of Quantum Annealing for the Construction of Satisfiability Filters
- Classical and Quantum Annealing in the Median of Three Satisfiability
- Adiabatic quantum computation along quasienergies
- Solution to Satisfiability problem by a complete Grover search with trapped ions
- Probing nonlinear adiabatic paths with a universal integrator
- Avoid First Order Quantum Phase Transition by Changing Problem Hamiltonians
- The speed of Markovian relaxation towards the ground state
- Boosting quantum annealing performance through direct polynomial unconstrained binary optimization
- A Monte Carlo Tree Search approach to QAOA: finding a needle in the haystack
- Eigenlevel statistics of the quantum adiabatic algorithm
- Single-solution Random 3-SAT Instances
- Realistic cost for the model of coherent computing