Anderson localization casts clouds over adiabatic quantum optimization
arXiv:0912.0746 · doi:10.1073/pnas.1002116107
Abstract
Understanding NP-complete problems is a central topic in computer science. This is why adiabatic quantum optimization has attracted so much attention, as it provided a new approach to tackle NP-complete problems using a quantum computer. The efficiency of this approach is limited by small spectral gaps between the ground and excited states of the quantum computer's Hamiltonian. We show that the statistics of the gaps can be analyzed in a novel way, borrowed from the study of quantum disordered systems in statistical mechanics. It turns out that due to a phenomenon similar to Anderson localization, exponentially small gaps appear close to the end of the adiabatic algorithm for large random instances of NP-complete problems. This implies that unfortunately, adiabatic quantum optimization fails: the system gets trapped in one of the numerous local minima.
14 pages, 4 figures
References in corpus (4)
Cited by in corpus (161)
- Ising formulations of many NP problems
- Adiabatic Quantum Computing
- Quantum annealing with more than one hundred qubits
- Perspectives of quantum annealing: Methods and implementations
- Diffusive and subdiffusive spin transport in the ergodic phase of a many-body localizable system
- What is the Computational Value of Finite Range Tunneling?
- Minimizing irreversible losses in quantum systems by local counter-diabatic driving
- Review: Local Integrals of Motion in Many-Body Localized systems
- Error corrected quantum annealing with hundreds of qubits
- Localization and adiabatic pumping in a generalized Aubry-André-Harper model
- Prospects for Quantum Enhancement with Diabatic Quantum Annealing
- 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
- Dynamical phase transitions in quantum reservoir computing
- The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
- Completely positive master equation for arbitrary driving and small level spacing
- Understanding Quantum Tunneling through Quantum Monte Carlo Simulations
- Fixed points of Wegner-Wilson flows and many-body localization
- Non-local Adiabatic Response of a Localized System to Local Manipulations
- How "Quantum" is the D-Wave Machine?
- Training A Quantum Optimizer
- Applying the Quantum Approximate Optimization Algorithm to the Tail Assignment Problem
- Scaling and diabatic effects in quantum annealing with a D-Wave device
- Speeding up critical system dynamics through optimized evolution
- Multivariable Optimization: Quantum Annealing & Computation
- The quantum adiabatic algorithm and scaling of gaps at first order quantum phase transitions
- Efficiency of quantum versus classical annealing in non-convex learning problems
- Temperature scaling law for quantum annealing optimizers
- Does Adiabatic Quantum Optimization Truly Fail for NP-complete problems?
- The many-body localized phase of the quantum random energy model
- Digital Quantum Simulation of the Statistical Mechanics of a Frustrated Magnet
- Ground State Spin Logic
- From ergodic to non-ergodic chaos in Rosenzweig-Porter model
- Quantum annealing: the fastest route to quantum computation?
- Introduction to Quantum Algorithms for Physics and Chemistry
- Scaling analysis and instantons for thermally-assisted tunneling and Quantum Monte Carlo simulations
- On the structure of typical states of a disordered Richardson model and many-body localization
- Non-ergodic delocalized states for efficient population transfer within a narrow band of the energy landscape
- An introduction to quantum annealing
- Quantum annealing with longitudinal bias fields
- Programmable Quantum Annealing Architectures with Ising Quantum Wires
- Quantum algorithm for energy matching in hard optimization problems
- Algorithmic approach to adiabatic quantum optimization
- Energy transport in a disordered spin chain with broken U(1) symmetry: Diffusion, subdiffusion, and many-body localization
- Probing Entanglement in Adiabatic Quantum Optimization with Trapped Ions
- The Power of Adiabatic Quantum Computation with No Sign Problem
- Adiabatic optimization versus diffusion Monte Carlo
- Diagnosing non-Hermitian Many-Body Localization and Quantum Chaos via Singular Value Decomposition
- Why and when is pausing beneficial in quantum annealing?
- Computing solution space properties of combinatorial optimization problems via generic tensor networks
- Different Adiabatic Quantum Optimization Algorithms for the NP-Complete Exact Cover and 3SAT Problems
- A quantum-walk-inspired adiabatic algorithm for graph isomorphism
- Observing the two-dimensional Bose glass in an optical quasicrystal
- Quantum integrability in the multistate Landau-Zener problem
- Constrained quantum annealing of graph coloring
- Anderson Localization on the Bethe Lattice using Cages and the Wegner Flow
- Schedule path optimization for quantum annealing and adiabatic quantum computing
- Quenched vs Annealed: Glassiness from SK to SYK
- Degeneracy, degree, and heavy tails in quantum annealing
- Scaling up the Anderson transition in random-regular graphs
- Anderson localization in dissipative lattices
- Entanglement critical length at the many-body localization transition
- Fragmented imaginary-time evolution for early-stage quantum signal processors
- Mean-Field Approximate Optimization Algorithm
- Spectral Form Factor of a Quantum Spin Glass
- Dominant Reaction Pathways by Quantum Computing
- Circumventing superexponential runtimes for hard instances of quantum adiabatic optimization
- The Large Connectivity Limit of the Anderson Model on Tree Graphs
- Stable Unitary Integrators for the Numerical Implementation of Continuous Unitary Transformations
- Interface dynamics in the two-dimensional quantum Ising model
- Elimination of Perturbative Crossings in Adiabatic Quantum Optimization
- Quantum Annealing - Foundations and Frontiers
- Lower Bounds on Quantum Annealing Times
- Many-body localization enables iterative quantum optimization
- Adiabatic quantum optimization in presence of discrete noise: Reducing the problem dimensionality
- The Effects of the Problem Hamiltonian Parameters on the Minimum Spectral Gap in Adiabatic Quantum Optimization
- Adiabatic Quantum Optimization Fails to Solve the Knapsack Problem
- Eigenstate localization in a many-body quantum system
- Quantum state engineering by steering in the presence of errors
- Quantum annealing of pure and random Ising chains coupled to a bosonic environment
- Speedup of the Quantum Adiabatic Algorithm using Delocalization Catalysis
- Exploring Quantum Annealing Architectures: A Spin Glass Perspective
- Ergodic and localized regions in quantum spin glasses on the Bethe lattice
- Quantum Jamming: Critical Properties of a Quantum Mechanical Perceptron
- Counterdiabatic route for preparation of state with long-range topological order
- Mediator assisted cooling in quantum annealing
- Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end
- Deep recurrent networks predicting the gap evolution in adiabatic quantum computing
- Optimization by a quantum reinforcement algorithm
- A comparison between D-wave and a classical approximation algorithm and a heuristic for computing the ground state of an Ising spin glass
- Noise amplification at spin-glass bottlenecks of quantum annealing: a solvable model
- From Ansätze to Z-gates: a NASA View of Quantum Computing
- Hybrid annealing using a quantum simulator coupled to a classical computer
- On the quantum spin glass transition on the Bethe lattice
- Theory of metastable states in many-body quantum systems
- Quantum ground state isoperimetric inequalities for the energy spectrum of local Hamiltonians
- New Developments in Quantum Algorithms
- Duality in Quantum Quenches and Classical Approximation Algorithms: Pretty Good or Very Bad
- Quantum annealing in spin-boson model: from a perturbative to a ultrastrong mediated coupling
- Classical and Quantum Annealing in the Median of Three Satisfiability
- Locally Suppressed Transverse-Field Protocol for Diabatic Quantum Annealing
- Enhancing the efficiency of quantum annealing via reinforcement: A path-integral Monte Carlo simulation of the quantum reinforcement algorithm
- Ion native variational ansatz for quantum approximate optimization
- Anderson localization of composite particles
- Clustering in Hilbert space of a quantum optimization problem
- Quantum Monte Carlo Annealing with Multi-Spin Dynamics
- Quantum Chaos in Random Ising Networks
- Dissipative failure of adiabatic quantum transport as a dynamical phase transition
- The quantum annealing gap and quench dynamics in the exact cover problem
- Obstacles to quantum annealing in a planar embedding of XORSAT
- Localization in the constrained quantum annealing of graph coloring
- Genuine Multipartite Entanglement in Quantum Optimization
- Probing nonlinear adiabatic paths with a universal integrator
- Parameter Setting Heuristics Make the Quantum Approximate Optimization Algorithm Suitable for the Early Fault-Tolerant Era
- Bounding first-order quantum phase transitions in adiabatic quantum computing
- Noise-tolerant quantum speedups in quantum annealing without fine tuning
- Path-Integral Quantum Monte Carlo simulation with Open-Boundary Conditions
- Avoid First Order Quantum Phase Transition by Changing Problem Hamiltonians
- Adiabatic time evolution of highly excited states
- Mapping NP-hard and NP-complete optimisation problems to Quadratic Unconstrained Binary Optimisation problems
- Optimized QUBO formulation methods for quantum computing
- On the efficiency of Hamiltonian-based quantum computation for low-rank matrices
- Entropic barriers as a reason for hardness in both classical and quantum algorithms
- Quantum annealing sampling with a bias field
- Probing localization properties of many-body Hamiltonians via an imaginary vector potential
- Quantum algorithm of a set of quantum 2-sat problem
- The effect of quantum fluctuations on the coloring of random graphs
- Physical consequences of PNP and the DMRG-annealing conjecture
- Quantum annealing of Cayley-tree Ising spins at small scales
- Local Information Flow in Quantum Quench Dynamics
- Supersymmetrically bounding of asymmetric states and quantum phase transitions by anti-crossing of symmetric states
- Local Density of States Correlations in the Lévy-Rosenzweig-Porter random matrix ensemble
- Quantum walk in a reinforced free-energy landscape: Quantum annealing with reinforcement
- Boosting quantum annealing performance through direct polynomial unconstrained binary optimization
- Computational Bottlenecks of Quantum Annealing
- Impact of Fixing Spins in a Quantum Annealer with Energy Rescaling
- Improving the efficiency of quantum annealing with controlled diagonal catalysts
- Quantum annealing showing an exponentially small success probability despite a constant energy gap with polynomial energy
- Adiabatic Quantum Programming: Minor Embedding With Hard Faults
- Diabatic quantum and classical annealing of the Sherrington-Kirkpatrick model
- The Short Path Algorithm Applied to a Toy Model
- A scalable 2-local architecture for quantum annealing of Ising models with arbitrary dimensions
- Absence of disordered Thouless pumps at finite frequency
- Unstructured Adiabatic Quantum Optimization: Optimality with Limitations
- Learning-Driven Annealing with Adaptive Hamiltonian Modification for Solving Large-Scale Problems on Quantum Devices
- Asymptotic Exceptional Steady States in Dissipative Dynamics
- Development of research network on Quantum Annealing Computation and Information using Google Scholar data
- Quantum Searches in a Hard 2SAT Ensemble
- Quantum Hopfield Model with Dilute Memories
- Optimized adiabatic-impulse protocol preserving Kibble-Zurek scaling with attenuated anti-Kibble-Zurek behavior
- Anti-crossings occurrence as exponentially closing gaps in Quantum Annealing
- Learning adiabatic quantum algorithms for solving optimization problems
- Effect of Quantum Statistics on Computational Power of Atomic Quantum Annealers
- Hard combinatorial problems and minor embeddings on lattice graphs
- Energy Spectrum and Exact Cover in an Extended Quantum Ising Model
- A journey into localization, integrability and thermalization
- The anomalously slow dynamics of inhomogeneous quantum annealing
- Exploring exotic configurations with anomalous features using deep learning: Application of classical and quantum-classical hybrid anomaly detection
- Essentiality of the Non-stoquastic Hamiltonians and Driver Graph Design in Quantum Optimization Annealing
- Finite temperature quantum condensations in the space of states: a new perspective for quantum annealing
- Frustration-enhanced quantum annealing correction models with additional inter-replica interactions