First Order Quantum Phase Transition in Adiabatic Quantum Computation

Abstract

We investigate the connection between local minima in the problem Hamiltonian and first order quantum phase transitions during an adiabatic quantum computation. We demonstrate how some properties of the local minima can lead to an extremely small gap that is exponentially sensitive to the Hamiltonian parameters. Using perturbation expansion, we derive an analytical formula that can not only predict the behavior of the gap, but also provide insight on how to controllably vary the gap size by changing the parameters. We show agreement with numerical calculations for a weighted maximum independent set problem instance.

4 pages, 3 figures, published final version

References in corpus (9)

• Rare region effects at classical, quantum, and non-equilibrium phase transitions
• Adiabatic quantum dynamics of a random Ising chain across its quantum critical point
• Adiabatic approximation with exponential accuracy for many-body systems and quantum computation
• Size dependence of the minimum excitation gap in the Quantum Adiabatic Algorithm
• Noise resistance of adiabatic quantum computation using random matrix theory
• Decoherence in a scalable adiabatic quantum computer
• Effect of Local Minima on Adiabatic Quantum Optimization
• Adiabatic preparation without Quantum Phase Transitions
• Dynamical quantum phase transitions

Cited by in corpus (77)

• Adiabatic Quantum Computing
• Quantum annealing with more than one hundred qubits
• Simulating chemistry using quantum computers
• Experimental Investigation of an Eight Qubit Unit Cell in a Superconducting Optimization Processor
• Anderson localization casts clouds over adiabatic quantum optimization
• Quantum phase transitions in transverse field spin models: from statistical physics to quantum information
• First order phase transition in the Quantum Adiabatic Algorithm
• Glassy Chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• 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
• First-order transitions and the performance of quantum algorithms in random optimization problems
• Coherent and dissipative dynamics at quantum phase transitions
• Intrinsic geometry of quantum adiabatic evolution and quantum phase transitions
• Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly
• A 16-bit Coherent Ising Machine for One-Dimensional Ring and Cubic Graph Problems
• Speeding up critical system dynamics through optimized evolution
• The quantum adiabatic algorithm and scaling of gaps at first order quantum phase transitions
• Accuracy vs run time in adiabatic quantum search
• Does Adiabatic Quantum Optimization Truly Fail for NP-complete problems?
• Training a Large Scale Classifier with the Quantum Adiabatic Algorithm
• Quantum transitions driven by one-bond defects in quantum Ising rings
• Quantum annealing: the fastest route to quantum computation?
• Role of Non-stoquastic Catalysts in Quantum Adiabatic Optimization
• An introduction to quantum annealing
• Quantum annealing with longitudinal bias fields
• Controllable exchange coupling between two singlet-triplet qubits
• Algorithmic approach to adiabatic quantum optimization
• Experimental demonstration of perturbative anticrossing mitigation using non-uniform driver Hamiltonians
• Adiabatic optimization versus diffusion Monte Carlo
• Different Adiabatic Quantum Optimization Algorithms for the NP-Complete Exact Cover and 3SAT Problems
• Finite-size scaling at the first-order quantum transitions of quantum Potts chains
• High Fidelity Adiabatic Quantum Computation via Dynamical Decoupling
• Schedule path optimization for quantum annealing and adiabatic quantum computing
• A quantum phase transition in the one-dimensional water chain
• Out-of-equilibrium dynamics driven by localized time-dependent perturbations at quantum phase transitions
• Designing Quantum Annealing Schedules using Bayesian Optimization
• Comparing relaxation mechanisms in quantum and classical transverse-field annealing
• Degeneracy, degree, and heavy tails in quantum annealing
• A solvable model of quantum random optimization problems
• Engineering First-Order Quantum Phase Transitions for Weak Signal Detection
• De-Signing Hamiltonians for Quantum Adiabatic Optimization
• Mean-Field Approximate Optimization Algorithm
• Circumventing superexponential runtimes for hard instances of quantum adiabatic optimization
• Off-equilibrium scaling behaviors across first-order transitions
• Elimination of Perturbative Crossings in Adiabatic Quantum Optimization
• Many-body localization enables iterative quantum optimization
• The Effects of the Problem Hamiltonian Parameters on the Minimum Spectral Gap in Adiabatic Quantum Optimization
• A hybrid classical-quantum approach to solve the heat equation using quantum annealers
• Adiabatic Quantum Optimization Fails to Solve the Knapsack Problem
• Diabatic Quantum Annealing for the Frustrated Ring Model
• Quantum state engineering by steering in the presence of errors
• Deep recurrent networks predicting the gap evolution in adiabatic quantum computing
• Diagonal Catalysts in Quantum Adiabatic Optimization
• Quantum adiabatic optimization with Rydberg arrays: localization phenomena and encoding strategies
• Classical and Quantum Annealing in the Median of Three Satisfiability
• Locally Suppressed Transverse-Field Protocol for Diabatic Quantum Annealing
• 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
• Eigenvalue-invariant transformation of Ising problem for anti-crossing mitigation in quantum annealing
• Out-of-equilibrium dynamics across the first-order quantum transitions of one-dimensional quantum Ising models
• Improving nonstoquastic quantum annealing with spin-reversal transformations
• The effect of quantum fluctuations on the coloring of random graphs
• Adiabatic Bottlenecks in Quantum Annealing and Nonequilibrium Dynamics of Paramagnons
• Quantum Hopfield Model with Dilute Memories
• Fighting Exponentially Small Gaps by Counterdiabatic Driving
• Learning-Driven Annealing with Adaptive Hamiltonian Modification for Solving Large-Scale Problems on Quantum Devices
• Asymptotic Exceptional Steady States in Dissipative Dynamics
• A scalable 2-local architecture for quantum annealing of Ising models with arbitrary dimensions
• Effect of Quantum Statistics on Computational Power of Atomic Quantum Annealers
• Energy Spectrum and Exact Cover in an Extended Quantum Ising Model
• Quantum quenches across continuous and first-order quantum transitions in one-dimensional quantum Ising models
• Anti-crossings occurrence as exponentially closing gaps in Quantum Annealing
• Quantum combinatorial optimization beyond the variational paradigm: simple schedules for hard problems
• Adiabatic Dynamics of Entanglement