Size dependence of the minimum excitation gap in the Quantum Adiabatic Algorithm
arXiv:0803.3971 · doi:10.1103/PhysRevLett.101.170503
Abstract
We study the typical (median) value of the minimum gap in the quantum version of the Exact Cover problem using Quantum Monte Carlo simulations, in order to understand the complexity of the quantum adiabatic algorithm (QAA) for much larger sizes than before. For a range of sizes, N <= 128, where the classical Davis-Putnam algorithm shows exponential median complexity, the QAA shows polynomial median complexity. The bottleneck of the algorithm is an isolated avoided crossing point of a Landau-Zener type (collision between the two lowest energy levels only).
4 pages, 5 figures
References in corpus (4)
Cited by in corpus (88)
- Adiabatic Quantum Computing
- Quantum annealing with more than one hundred qubits
- Quantum machine learning: a classical perspective
- Experimental Investigation of an Eight Qubit Unit Cell in a Superconducting Optimization Processor
- Anderson localization casts clouds over adiabatic quantum optimization
- Error corrected quantum annealing with hundreds of qubits
- First order phase transition in the Quantum Adiabatic Algorithm
- 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
- Energy gaps in quantum first-order mean-field-like transitions: The problems that quantum annealing cannot solve
- Quantum adiabatic machine learning
- First Order Quantum Phase Transition in Adiabatic Quantum Computation
- The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
- Adiabatic quantum algorithm for search engine ranking
- First-order transitions and the performance of quantum algorithms in random optimization problems
- Quantum Annealing for Constrained Optimization
- Exponential Complexity of the Quantum Adiabatic Algorithm for certain Satisfiability Problems
- The quantum adiabatic algorithm and scaling of gaps at first order quantum phase transitions
- Many-body transverse interactions in the quantum annealing of the p-spin ferromagnet
- Temperature scaling law for quantum annealing optimizers
- MAX 2-SAT with up to 108 qubits
- Training a Large Scale Classifier with the Quantum Adiabatic Algorithm
- Driver Hamiltonians for constrained optimization in quantum annealing
- Digital Quantum Simulation of the Statistical Mechanics of a Frustrated Magnet
- Quantum versus classical annealing: insights from scaling theory and results for spin glasses on 3-regular graphs
- Quantum annealing: the fastest route to quantum computation?
- Introduction to Quantum Algorithms for Physics and Chemistry
- Quantum pattern recognition with liquid-state nuclear magnetic resonance
- Observation of the ground-state-geometric phase in a Heisenberg XY model
- An introduction to quantum annealing
- Quiet Planting in the Locked Constraint Satisfaction Problems
- Adiabatic Quantum Algorithms for the NP-Complete Maximum-Weight Independent Set, Exact Cover and 3SAT Problems
- Solving the Graph Isomorphism Problem with a Quantum Annealer
- Practical engineering of hard spin-glass instances
- Analog Nature of Quantum Adiabatic Unstructured Search
- Off-Diagonal Expansion Quantum Monte Carlo
- An Integrated Programming and Development Environment for Adiabatic Quantum Optimization
- Complexity of several constraint satisfaction problems using the heuristic, classical, algorithm, WalkSAT
- Faster than Classical Quantum Algorithm for dense Formulas of Exact Satisfiability and Occupation Problems
- De-Signing Hamiltonians for Quantum Adiabatic Optimization
- Excitation Gap from Optimized Correlation Functions in Quantum Monte Carlo Simulations
- Adiabatic Quantum Optimization for Associative Memory Recall
- Robust Parameter Selection for Parallel Tempering
- Density functional theory and quantum computation
- Fermionic Quantum Approximate Optimization Algorithm
- High-Performance Physics Simulations Using Multi-Core CPUs and GPGPUs in a Volunteer Computing Context
- Many-body localization enables iterative quantum optimization
- Local Hamiltonians in Quantum Computation
- Adiabatic quantum optimization in presence of discrete noise: Reducing the problem dimensionality
- 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
- Quantum Computing by Cooling
- Macroscopic character of composite high temperature superconducting wires
- Guided quantum walk
- Quantum state engineering by steering in the presence of errors
- Speedup of the Quantum Adiabatic Algorithm using Delocalization Catalysis
- Mediator assisted cooling in quantum annealing
- Deep recurrent networks predicting the gap evolution in adiabatic quantum computing
- How Fast Can Quantum Annealers Count?
- On the quantum spin glass transition on the Bethe lattice
- Tunneling in projective quantum Monte Carlo simulations with guiding wave functions
- Non-Hermitian Quantum Annealing in the Ferromagnetic Ising Model
- Quantum search using non-Hermitian adiabatic evolution
- Non-Adiabatic Quantum Optimization for Crossing Quantum Phase Transitions
- Why the Quantitative Condition Fails to Reveal Quantum Adiabaticity
- Quantum annealing in spin-boson model: from a perturbative to a ultrastrong mediated coupling
- Classical and Quantum Annealing in the Median of Three Satisfiability
- Non-Hermitian Quantum Annealing in the Antiferromagnetic Ising Chain
- How Quantum is the Speedup in Adiabatic Unstructured Search?
- Realizable Quantum Adiabatic Search
- Probing nonlinear adiabatic paths with a universal integrator
- Why adiabatic quantum annealing is unlikely to yield speed-up
- Infinite-range transverse field Ising models and quantum computation
- Avoid First Order Quantum Phase Transition by Changing Problem Hamiltonians
- Effects of low-lying excitations on ground-state energy and energy gap of Sherrington-Kirkpatrick model in transverse field
- The effect of quantum fluctuations on the coloring of random graphs
- Quantum Integer Programming (QuIP) 47-779: Lecture Notes
- Investigating the potential for a limited quantum speedup on protein lattice problems
- Diabatic quantum and classical annealing of the Sherrington-Kirkpatrick model
- Non-Hermitian Adiabatic Quantum Optimization
- Investigating the Performance of an Adiabatic Quantum Optimization Processor
- Statistical mechanics of classical and quantum computational complexity
- Classical Simulation of Quantum Adiabatic Algorithms using Mathematica on GPUs
- Effects of dynamical paths on the energy gap and the corrections to free energy in path integrals of mean-field quantum spin systems
- Energy Spectrum and Exact Cover in an Extended Quantum Ising Model
- Energy gap of quantum spin glasses: a projection quantum Monte Carlo study
- Proof of avoidability of the quantum first-order transition in transverse magnetization in quantum annealing of finite-dimensional spin glasses