First order phase transition in the Quantum Adiabatic Algorithm
arXiv:0910.1378 · doi:10.1103/PhysRevLett.104.020502
Abstract
We simulate the quantum adiabatic algorithm (QAA) for the exact cover problem for sizes up to N=256 using quantum Monte Carlo simulations incorporating parallel tempering. At large N we find that some instances have a discontinuous (first order) quantum phase transition during the evolution of the QAA. This fraction increases with increasing N and may tend to 1 for N -> infinity.
5 pages, 3 figures. Replaced with published version; two figures slightly changed and some small changes to the text
References in corpus (4)
Cited by in corpus (120)
- Adiabatic Quantum Computing
- Quantum machine learning: a classical perspective
- Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
- Experimental Investigation of an Eight Qubit Unit Cell in a Superconducting Optimization Processor
- Ergodicity breaking in a model showing many-body localization
- Quantum Annealing: An Overview
- Glassy Chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines
- Prospects for Quantum Enhancement with Diabatic Quantum Annealing
- Quantum annealing with antiferromagnetic fluctuations
- The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
- Shortcuts to Adiabaticity in Digitized Adiabatic Quantum Computing
- Energy gaps in quantum first-order mean-field-like transitions: The problems that quantum annealing cannot solve
- 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
- Quantum Annealing for Constrained Optimization
- Coherent and dissipative dynamics at quantum phase transitions
- Exponential Complexity of the Quantum Adiabatic Algorithm for certain Satisfiability Problems
- Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly
- Training A Quantum Optimizer
- Applying the Quantum Approximate Optimization Algorithm to the Tail Assignment Problem
- A 16-bit Coherent Ising Machine for One-Dimensional Ring and Cubic Graph Problems
- Exponential Enhancement of the Efficiency of Quantum Annealing by Non-Stochastic Hamiltonians
- Speeding up critical system dynamics through optimized evolution
- The quantum adiabatic algorithm and scaling of gaps at first order quantum phase transitions
- NISQ Computers: A Path to Quantum Supremacy
- Many-body transverse interactions in the quantum annealing of the p-spin ferromagnet
- On quantum mean-field models and their quantum annealing
- Temperature scaling law for quantum annealing optimizers
- Does Adiabatic Quantum Optimization Truly Fail for NP-complete problems?
- Driver Hamiltonians for constrained optimization in quantum annealing
- Training a Large Scale Classifier with the Quantum Adiabatic Algorithm
- Portfolio Optimization with Digitized-Counterdiabatic Quantum Algorithms
- Quantum versus classical annealing: insights from scaling theory and results for spin glasses on 3-regular graphs
- Quantum transitions driven by one-bond defects in quantum Ising rings
- 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
- Quantum annealing with longitudinal bias fields
- Quantum algorithm for energy matching in hard optimization problems
- Algorithmic approach to adiabatic quantum optimization
- Ground-state fidelity at first-order quantum transitions
- Adiabatic Quantum Algorithms for the NP-Complete Maximum-Weight Independent Set, Exact Cover and 3SAT Problems
- Quantum annealing with Jarzynski equality
- Mean field analysis of reverse annealing for code-division multiple-access multiuser detection
- Finite-size scaling at the first-order quantum transitions of quantum Potts chains
- Solving the Graph Isomorphism Problem with a Quantum Annealer
- Quantum Computational Phase Transition in Combinatorial Problems
- Schedule path optimization for quantum annealing and adiabatic quantum computing
- Out-of-equilibrium dynamics driven by localized time-dependent perturbations at quantum phase transitions
- First-order quantum phase transitions: test ground for emergent chaoticity, regularity and persisting symmetries
- Direct comparison of quantum and simulated annealing on a fully-connected Ising ferromagnet
- Benchmarking digital quantum simulations above hundreds of qubits using quantum critical dynamics
- Analog Nature of Quantum Adiabatic Unstructured Search
- Degeneracy, degree, and heavy tails in quantum annealing
- Period Finding with Adiabatic Quantum Computation
- Adiabatic Quantum Search in Open Systems
- Complexity of several constraint satisfaction problems using the heuristic, classical, algorithm, WalkSAT
- On the relevance of avoided crossings away from quantum critical point to the complexity of quantum adiabatic algorithm
- De-Signing Hamiltonians for Quantum Adiabatic Optimization
- Binary phase oscillation of two mutually coupled semiconductor lasers
- Excitation Gap from Optimized Correlation Functions in Quantum Monte Carlo Simulations
- Comparing parallel and simulated tempering enhanced sampling algorithms at phase transition regimes
- Dissipative dynamics at first-order quantum transitions
- Greedy parameter optimization for diabatic quantum annealing
- Elimination of Perturbative Crossings in Adiabatic Quantum Optimization
- Off-equilibrium scaling behaviors across first-order transitions
- Continuous-Time Quantum Algorithms for Unstructured Problems
- Anomalous behavior of the energy gap in the one-dimensional quantum XY model
- Circuit-based digital adiabatic quantum simulation and pseudoquantum simulation as new approaches to lattice gauge theory
- Quantum Annealing with Trigger Hamiltonians: Application to 2-SAT and Nonstoquastic Problems
- Quantum annealing of pure and random Ising chains coupled to a bosonic environment
- Evolution of order and chaos across a first-order quantum phase transition
- Guided quantum walk
- Nonequilibrium work on spin glasses in longitudinal and transverse fields
- Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end
- How Fast Can Quantum Annealers Count?
- Noise amplification at spin-glass bottlenecks of quantum annealing: a solvable model
- Leveraging Analog Quantum Computing with Neutral Atoms for Solvent Configuration Prediction in Drug Discovery
- Cyclic Quantum Annealing: Searching for Deep Low-Energy States in 5000-Qubit Spin Glass
- A simple protocol for the probability weights of the simulated tempering algorithm: applications to first-order phase transitions
- Universal scaling in quenches across a discontinuity critical point
- Non-Adiabatic Quantum Optimization for Crossing Quantum Phase Transitions
- Classical and Quantum Annealing in the Median of Three Satisfiability
- Realizable Quantum Adiabatic Search
- Nonequilibrium work performed in quantum annealing
- Non-Hermitian Quantum Annealing in the Antiferromagnetic Ising Chain
- How Quantum is the Speedup in Adiabatic Unstructured Search?
- Why adiabatic quantum annealing is unlikely to yield speed-up
- Tensor network method for reversible classical computation
- Bounding first-order quantum phase transitions in adiabatic quantum computing
- The quantum annealing gap and quench dynamics in the exact cover problem
- Localization in the constrained quantum annealing of graph coloring
- Probing nonlinear adiabatic paths with a universal integrator
- Quantum Chaos in Random Ising Networks
- Avoid First Order Quantum Phase Transition by Changing Problem Hamiltonians
- Out-of-equilibrium dynamics across the first-order quantum transitions of one-dimensional quantum Ising models
- Path-Integral Quantum Monte Carlo simulation with Open-Boundary Conditions
- Effects of low-lying excitations on ground-state energy and energy gap of Sherrington-Kirkpatrick model in transverse field
- Entropic barriers as a reason for hardness in both classical and quantum algorithms
- Quantum annealing sampling with a bias field
- An approximate diagonalization method for large scale Hamiltonians
- Adiabatic Bottlenecks in Quantum Annealing and Nonequilibrium Dynamics of Paramagnons
- Investigating the potential for a limited quantum speedup on protein lattice problems
- Experimental Determination of Electronic States via Digitized Shortcut-to-Adiabaticity and Sequential Digitized Adiabaticity
- The effect of quantum fluctuations on the coloring of random graphs
- Quantum annealing showing an exponentially small success probability despite a constant energy gap with polynomial energy
- Computational Bottlenecks of Quantum Annealing
- Superposition of Macroscopically Distinct States in Adiabatic Quantum Computation
- Statistical mechanics of classical and quantum computational complexity
- Fighting Exponentially Small Gaps by Counterdiabatic Driving
- Asymptotic Exceptional Steady States in Dissipative Dynamics
- The anomalously slow dynamics of inhomogeneous quantum annealing
- Quantum quenches across continuous and first-order quantum transitions in one-dimensional quantum Ising models
- Energy Spectrum and Exact Cover in an Extended Quantum Ising Model
- Effects of dynamical paths on the energy gap and the corrections to free energy in path integrals of mean-field quantum spin systems
- A journey into localization, integrability and thermalization
- Adiabatic Dynamics of Entanglement
- Proof of avoidability of the quantum first-order transition in transverse magnetization in quantum annealing of finite-dimensional spin glasses
- Weyl's Relations, Integrable Matrix Models and Quantum Computation
- Statistical mechanical models of integer factorization problem