De-Signing Hamiltonians for Quantum Adiabatic Optimization
arXiv:2004.07681 · doi:10.22331/q-2020-09-24-334
Abstract
Quantum fluctuations driven by non-stoquastic Hamiltonians have been conjectured to be an important and perhaps essential missing ingredient for achieving a quantum advantage with adiabatic optimization. We introduce a transformation that maps every non-stoquastic adiabatic path ending in a classical Hamiltonian to a corresponding stoquastic adiabatic path by appropriately adjusting the phase of each matrix entry in the computational basis. We compare the spectral gaps of these adiabatic paths and find both theoretically and numerically that the paths based on non-stoquastic Hamiltonians have generically smaller spectral gaps between the ground and first excited states, suggesting they are less useful than stoquastic Hamiltonians for quantum adiabatic optimization. These results apply to any adiabatic algorithm which interpolates to a final Hamiltonian that is diagonal in the computational basis.
16 pages, 9 figures. v2: 19 pages, 9 figures; updated to published version
References in corpus (45)
- Quantum Annealing in the Transverse Ising Model
- Computational complexity and fundamental limitations to fermionic quantum Monte Carlo simulations
- Theory of Quantum Annealing of an Ising Spin Glass
- Quantum Annealing: A New Method for Minimizing Multidimensional Functions
- Quantum Search by Local Adiabatic Evolution
- Defining and detecting quantum speedup
- Quantum Computation by Adiabatic Evolution
- Bounds for the adiabatic approximation with applications to quantum computation
- Computational Role of Multiqubit Tunneling in a Quantum Annealer
- The largest eigenvalue of rank one deformation of large Wigner matrices
- Realizable Hamiltonians for Universal Adiabatic Quantum Computers
- First order phase transition in the Quantum Adiabatic Algorithm
- Quantum annealing with antiferromagnetic fluctuations
- Size dependence of the minimum excitation gap in the Quantum Adiabatic Algorithm
- 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
- Understanding Quantum Tunneling through Quantum Monte Carlo Simulations
- Nonstoquastic Hamiltonians and Quantum Annealing of an Ising Spin Glass
- Exponential Complexity of the Quantum Adiabatic Algorithm for certain Satisfiability Problems
- Quantum Adiabatic Evolution Algorithms versus Simulated Annealing
- Many-body transverse interactions in the quantum annealing of the p-spin ferromagnet
- Different Strategies for Optimization Using the Quantum Adiabatic Algorithm
- Driver Hamiltonians for constrained optimization in quantum annealing
- On the Computational Complexity of Curing the Sign Problem
- Quantum versus classical annealing: insights from scaling theory and results for spin glasses on 3-regular graphs
- Role of Non-stoquastic Catalysts in Quantum Adiabatic Optimization
- Non-Stoquastic Interactions in Quantum Annealing via the Aharonov-Anandan Phase
- Merlin-Arthur Games and Stoquastic Complexity
- Adiabatic optimization versus diffusion Monte Carlo
- Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems
- Relation between quantum fluctuations and the performance enhancement of quantum annealing in a nonstoquastic Hamiltonian
- Polynomial-time classical simulation of quantum ferromagnets
- Steering random spin systems to speed up the quantum adiabatic algorithm
- Off-Diagonal Expansion Quantum Monte Carlo
- Excitation Gap from Optimized Correlation Functions in Quantum Monte Carlo Simulations
- Cheeger constants, structural balance, and spectral clustering analysis for signed graphs
- Ground-state Energies of Spinless Free Fermions and Hard-core Bosons
- Quantum Speed-Up at Zero Temperature via Coherent Catalysis
- Can quantum Monte Carlo simulate quantum annealing?
- Quantum ground state isoperimetric inequalities for the energy spectrum of local Hamiltonians
- Particle Statistics, Frustration, and Ground-State Energy
- Hamiltonian surgery: Cheeger-type gap inequalities for nonpositive (stoquastic), real, and Hermitian matrices
- Energy gaps of Hamiltonians from graph Laplacians
- Quantum adiabatic optimization without heuristics
- An isoperimetric constant for signed graphs
Cited by in corpus (18)
- Quantum Annealing for Industry Applications: Introduction and Review
- Prospects for Quantum Enhancement with Diabatic Quantum Annealing
- Digitized-Counterdiabatic Quantum Optimization
- Low depth mechanisms for quantum optimization
- Standard quantum annealing outperforms adiabatic reverse annealing with decoherence
- Lower Bounds on Quantum Annealing Times
- Determining QMC simulability with geometric phases
- Quantum Annealing with Trigger Hamiltonians: Application to 2-SAT and Nonstoquastic Problems
- Counterdiabatic Reverse Annealing
- Quantum annealing with twisted fields
- Phase transitions in the frustrated Ising ladder with stoquastic and nonstoquastic catalysts
- Bounding first-order quantum phase transitions in adiabatic quantum computing
- Improving nonstoquastic quantum annealing with spin-reversal transformations
- Investigating the potential for a limited quantum speedup on protein lattice problems
- Nonstoquastic catalyst for bifurcation-based quantum annealing of ferromagnetic -spin model
- Diabatic quantum and classical annealing of the Sherrington-Kirkpatrick model
- Effect of Quantum Statistics on Computational Power of Atomic Quantum Annealers
- Essentiality of the Non-stoquastic Hamiltonians and Driver Graph Design in Quantum Optimization Annealing