Exponential Complexity of the Quantum Adiabatic Algorithm for certain Satisfiability Problems

Abstract

We determine the complexity of several constraint satisfaction problems using the quantum adiabatic algorithm in its simplest implementation. We do so by studying the size dependence of the gap to the first excited state of "typical" instances. We find that at large sizes N, the complexity increases exponentially for all models that we study. We also compare our results against the complexity of the analogous classical algorithm WalkSAT and show that the harder the problem is for the classical algorithm the harder it is also for the quantum adiabatic algorithm.

9 pages, 7 figures

References in corpus (7)

• Stochastic series expansion method for quantum Ising models with arbitrary interactions
• Size dependence of the minimum excitation gap in the Quantum Adiabatic Algorithm
• Energy gaps in quantum first-order mean-field-like transitions: The problems that quantum annealing cannot solve
• Simple Glass Models and their Quantum Annealing
• On the path integral representation for quantum spin models and its application to the quantum cavity method and to Monte Carlo simulations
• Locked constraint satisfaction problems
• Constraint satisfaction problems with isolated solutions are hard

Cited by in corpus (56)

• Ising formulations of many NP problems
• Adiabatic Quantum Computing
• Quantum annealing with more than one hundred qubits
• Quantum machine learning: a classical perspective
• Statistical physics of inference: Thresholds and algorithms
• Glassy Chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines
• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
• Quantum Annealing for Constrained Optimization
• Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly
• Training A Quantum Optimizer
• Exponential Enhancement of the Efficiency of Quantum Annealing by Non-Stochastic Hamiltonians
• Multivariable Optimization: Quantum Annealing & Computation
• Many-body transverse interactions in the quantum annealing of the p-spin ferromagnet
• Temperature scaling law for quantum annealing optimizers
• Unraveling Quantum Annealers using Classical Hardness
• Driver Hamiltonians for constrained optimization in quantum annealing
• Scaling analysis and instantons for thermally-assisted tunneling and Quantum Monte Carlo simulations
• Introduction to Quantum Algorithms for Physics and Chemistry
• The Quantum Transition of the Two-Dimensional Ising Spin Glass: A Tale of Two Gaps
• Solving the Graph Isomorphism Problem with a Quantum Annealer
• Practical engineering of hard spin-glass instances
• Stability of the quantum Sherrington-Kirkpatrick spin glass model
• Direct comparison of quantum and simulated annealing on a fully-connected Ising ferromagnet
• Analog Nature of Quantum Adiabatic Unstructured Search
• Off-Diagonal Expansion Quantum Monte Carlo
• Period Finding with Adiabatic Quantum Computation
• De-Signing Hamiltonians for Quantum Adiabatic Optimization
• Faster than Classical Quantum Algorithm for dense Formulas of Exact Satisfiability and Occupation Problems
• Excitation Gap from Optimized Correlation Functions in Quantum Monte Carlo Simulations
• Dominant Reaction Pathways by Quantum Computing
• Continuous-Time Quantum Algorithms for Unstructured Problems
• Inhomogeneous quenches as state preparation in two-dimensional conformal field theories
• Cooling arbitrary near-critical systems using hyperbolic quenches
• Permutation Matrix Representation Quantum Monte Carlo
• Parity Quantum Optimization: Encoding Constraints
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end
• Solving SAT and MaxSAT with a Quantum Annealer: Foundations, Encodings, and Preliminary Results
• How Fast Can Quantum Annealers Count?
• Leveraging Analog Quantum Computing with Neutral Atoms for Solvent Configuration Prediction in Drug Discovery
• Enhancing the efficiency of quantum annealing via reinforcement: A path-integral Monte Carlo simulation of the quantum reinforcement algorithm
• How Quantum is the Speedup in Adiabatic Unstructured Search?
• Realizable Quantum Adiabatic Search
• Exact Solution for the Transverse Field Sherrington-Kirkpatrick Spin Glass Model with Continuous-Time Quantum Monte Carlo Method
• Tensor network method for reversible classical computation
• Why adiabatic quantum annealing is unlikely to yield speed-up
• Path-Integral Quantum Monte Carlo simulation with Open-Boundary Conditions
• The effect of quantum fluctuations on the coloring of random graphs
• Adiabatic Bottlenecks in Quantum Annealing and Nonequilibrium Dynamics of Paramagnons
• Diabatic quantum and classical annealing of the Sherrington-Kirkpatrick model
• Quantum walk in a reinforced free-energy landscape: Quantum annealing with reinforcement
• The anomalously slow dynamics of inhomogeneous quantum annealing
• Continuous-time limit of topological quantum walks
• Realistic cost for the model of coherent computing
• Multi-step quantum algorithm for solving the 3-bit exact cover problem
• An exact algorithm for 1-in-3 SAT