Quantum annealing: the fastest route to quantum computation?

Abstract

In this review we consider the performance of the quantum adiabatic algorithm for the solution of decision problems. We divide the possible failure mechanisms into two sets: small gaps due to quantum phase transitions and small gaps due to avoided crossings inside a phase. We argue that the thermodynamic order of the phase transitions is not predictive of the scaling of the gap with the system size. On the contrary, we also argue that, if the phase surrounding the problem Hamiltonian is a Many-Body Localized (MBL) phase, the gaps are going to be typically exponentially small and that this follows naturally from the existence of local integrals of motion in the MBL phase.

arXiv comment16 pages, 1 figure

References in corpus (46)

• Quantum Annealing in the Transverse Ising Model
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Metal-insulator transition in a weakly interacting many-electron system with localized single-particle states
• The many-body localization phase transition
• Unbounded growth of entanglement in models of many-body localization
• Many body localization in Heisenberg XXZ magnet in a random field
• Phenomenology of fully many-body-localized systems
• A phenomenology of certain many-body-localized systems
• Local conservation laws and the structure of the many-body localized states
• Quantum annealing with more than one hundred qubits
• On Many-Body Localization for Quantum Spin Chains
• Universal slow growth of entanglement in interacting strongly disordered systems
• Quantum Computation by Adiabatic Evolution
• Integrals of motion in the Many-Body localized phase
• Localization protected quantum order
• Experimental signature of programmable quantum annealing
• Ergodicity breaking in a model showing many-body localization
• Many-body Localization with Dipoles
• Anderson localization casts clouds over adiabatic quantum optimization
• First order phase transition in the Quantum Adiabatic Algorithm
• Many-body mobility edge in a mean-field quantum spin glass
• A variational description of the ground state structure in random satisfiability problems
• Size dependence of the minimum excitation gap in the Quantum Adiabatic Algorithm
• 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
• First Order Quantum Phase Transition in Adiabatic Quantum Computation
• Energy transport in disordered classical spin chains
• Simple Glass Models and their Quantum Annealing
• The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
• First-order transitions and the performance of quantum algorithms in random optimization problems
• Non-local Adiabatic Response of a Localized System to Local Manipulations
• How "Quantum" is the D-Wave Machine?
• The quantum adiabatic algorithm and scaling of gaps at first order quantum phase transitions
• Cavity method for quantum spin glasses on the Bethe lattice
• On quantum mean-field models and their quantum annealing
• Exponential complexity of an adiabatic algorithm for an NP-complete problem
• On the structure of typical states of a disordered Richardson model and many-body localization
• On product, generic and random generic quantum satisfiability
• A solvable model of quantum random optimization problems
• On the relevance of avoided crossings away from quantum critical point to the complexity of quantum adiabatic algorithm
• Energy gap at first-order quantum phase transitions: An anomalous case
• Quantum adiabatic optimization and combinatorial landscapes
• Approximating random quantum optimization problems
• Statistical Mechanics of the Quantum K-Satisfiability problem
• Limitations of some simple adiabatic quantum algorithms
• Quantum Adiabatic Evolution Algorithm and Quantum Phase Transition in 3-Satisfiability Problem

Cited by in corpus (36)

• Adiabatic Quantum Computing
• Review: Local Integrals of Motion in Many-Body Localized systems
• Observing the space- and time-dependent growth of correlations in dynamically tuned synthetic Ising antiferromagnets
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Dynamical phase transitions in quantum reservoir computing
• Understanding Quantum Tunneling through Quantum Monte Carlo Simulations
• Fixed points of Wegner-Wilson flows and many-body localization
• Experimental probes of Stark many-body localization
• The many-body localized phase of the quantum random energy model
• Quantum annealing of the $p$-spin model under inhomogeneous transverse field driving
• Nested Quantum Annealing Correction
• Scaling analysis and instantons for thermally-assisted tunneling and Quantum Monte Carlo simulations
• Complex Quantum Networks: a Topical Review
• Energy transport in a disordered spin chain with broken U(1) symmetry: Diffusion, subdiffusion, and many-body localization
• Diagnosing non-Hermitian Many-Body Localization and Quantum Chaos via Singular Value Decomposition
• Scaling up the Anderson transition in random-regular graphs
• Adiabatic Quantum Search in Open Systems
• Entanglement critical length at the many-body localization transition
• Interface dynamics in the two-dimensional quantum Ising model
• Thermalization of noninteracting quantum systems coupled to blackbody radiation: A Lindblad-based analysis
• Quantum Jamming: Critical Properties of a Quantum Mechanical Perceptron
• Ergodic and localized regions in quantum spin glasses on the Bethe lattice
• On the quantum spin glass transition on the Bethe lattice
• Quantum ground state isoperimetric inequalities for the energy spectrum of local Hamiltonians
• Tunneling in projective quantum Monte Carlo simulations with guiding wave functions
• Dissipative failure of adiabatic quantum transport as a dynamical phase transition
• Anti-crossings and spectral gap during quantum adiabatic evolution
• Probing localization properties of many-body Hamiltonians via an imaginary vector potential
• Implementing transferable annealing protocols for combinatorial optimisation on neutral atom quantum processors: a case study on smart-charging of electric vehicles
• Entropic barriers as a reason for hardness in both classical and quantum algorithms
• The Short Path Algorithm Applied to a Toy Model
• Diabatic quantum and classical annealing of the Sherrington-Kirkpatrick model
• Choco-Q: Commute Hamiltonian-based QAOA for Constrained Binary Optimization
• Fighting Exponentially Small Gaps by Counterdiabatic Driving
• Simulating dynamics of the two-dimensional transverse-field Ising model: a comparative study of large-scale classical numerics
• Duality approach to quantum annealing of the 3-XORSAT problem