Nonstoquastic Hamiltonians and Quantum Annealing of an Ising Spin Glass

Abstract

We study the role of Hamiltonian complexity in the performance of quantum annealers. We consider two general classes of annealing Hamiltonians: stoquastic ones, which can be simulated efficiently using the quantum Monte Carlo algorithm, and nonstoquastic ones, which cannot be treated efficiently. We implement the latter by adding antiferromagnetically coupled two-spin driver terms to the traditionally studied transverse-field Ising model, and compare their performance to that of similar stoquastic Hamiltonians with ferromagnetically coupled additional terms. We focus on a model of long-range Ising spin glass as our problem Hamiltonian and carry out the comparison between the annealers by numerically calculating their success probabilities in solving random instances of the problem Hamiltonian in systems of up to 17 spins. We find that, for a small percentage of mostly harder instances, nonstoquastic Hamiltonians greatly outperform their stoquastic counterparts and their superiority persists as the system size grows. We conjecture that the observed improved performance is closely related to the frustrated nature of nonstoquastic Hamiltonians.

9 pages, 4 figures; v2: published version

References in corpus (5)

• Computational complexity and fundamental limitations to fermionic quantum Monte Carlo simulations
• Realizable Hamiltonians for Universal Adiabatic Quantum Computers
• Quantum annealing with antiferromagnetic fluctuations
• Exponential Enhancement of the Efficiency of Quantum Annealing by Non-Stochastic Hamiltonians
• Many-body transverse interactions in the quantum annealing of the p-spin ferromagnet

Cited by in corpus (75)

• Adiabatic Quantum Computing
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Perspectives of quantum annealing: Methods and implementations
• Quantum annealing with a network of all-to-all connected, two-photon driven Kerr nonlinear oscillators
• Exponential Speedup of Quantum Annealing by Inhomogeneous Driving of the Transverse Field
• Benchmarking Quantum Annealing Controls with Portfolio Optimization
• Demonstration of nonstoquastic Hamiltonian in coupled superconducting flux qubits
• Shortcuts to adiabaticity for quantum annealing
• Role of Non-stoquastic Catalysts in Quantum Adiabatic Optimization
• Noise-Assisted Quantum Autoencoder
• Non-Stoquastic Interactions in Quantum Annealing via the Aharonov-Anandan Phase
• Quantum annealing with longitudinal bias fields
• Digitized-Counterdiabatic Quantum Optimization
• Readiness of Quantum Optimization Machines for Industrial Applications
• Quantum Monte Carlo tunneling from quantum chemistry to quantum annealing
• Digitized Adiabatic Quantum Factorization
• Constrained quantum annealing of graph coloring
• Steering random spin systems to speed up the quantum adiabatic algorithm
• Variationally Scheduled Quantum Simulation
• Two-local qubit Hamiltonians: when are they stoquastic?
• De-Signing Hamiltonians for Quantum Adiabatic Optimization
• Robust Quantum Control for Adiabatic Quantum Computation
• Lower Bounds on Quantum Annealing Times
• Understanding Quantum Tunneling using Diffusion Monte Carlo Simulations
• The Effects of the Problem Hamiltonian Parameters on the Minimum Spectral Gap in Adiabatic Quantum Optimization
• A Quantum N-Queens Solver
• Quantum Speed-Up at Zero Temperature via Coherent Catalysis
• Quantum Annealing with Trigger Hamiltonians: Application to 2-SAT and Nonstoquastic Problems
• Bias-Field Digitized Counterdiabatic Quantum Algorithm for Higher-Order Binary Optimization
• Parity-Engineered Light-Matter Interaction
• Permutation Matrix Representation Quantum Monte Carlo
• Parity Quantum Optimization: Encoding Constraints
• Speedup of the Quantum Adiabatic Algorithm using Delocalization Catalysis
• Superconducting qubit circuit emulation of a vector spin-1/2
• Quantum annealing for hard 2-SAT problems : Distribution and scaling of minimum energy gap and success probability
• Mean-Field Solution of the Weak-Strong Cluster Problem for Quantum Annealing with Stoquastic and Non-Stoquastic Catalysts
• On the dynamics of Simulated Quantum Annealing in random Ising chains
• Quantum annealing with twisted fields
• Optimization by a quantum reinforcement algorithm
• A theory of non-equilibrium local search on random satisfaction problems
• Effective spin models of Kerr-nonlinear parametric oscillators for quantum annealing
• Dynamics of Order Parameters of Non-stoquastic Hamiltonians in the Adaptive Quantum Monte Carlo Method
• Rapid mixing of path integral Monte Carlo for 1D stoquastic Hamiltonians
• Stoquasticity in circuit QED
• Quantum ground state isoperimetric inequalities for the energy spectrum of local Hamiltonians
• Theoretical survey of unconventional quantum annealing methods applied to adifficult trial problem
• Phase transitions in the frustrated Ising ladder with stoquastic and nonstoquastic catalysts
• Localization in the constrained quantum annealing of graph coloring
• The quantum annealing gap and quench dynamics in the exact cover problem
• Dynamics of open quantum systems by interpolation of von Neumann and classical master equations, and its application to quantum annealing
• Noise-tolerant quantum speedups in quantum annealing without fine tuning
• Eigenvalue-invariant transformation of Ising problem for anti-crossing mitigation in quantum annealing
• Exact expression of the energy gap at first-order quantum phase transitions of a non-stoquastic Hamiltonian
• Excited state search using quantum annealing
• Improving nonstoquastic quantum annealing with spin-reversal transformations
• Quantum annealing sampling with a bias field
• How to experimentally evaluate the adiabatic condition for quantum annealing
• Nonstoquastic catalyst for bifurcation-based quantum annealing of ferromagnetic $p$-spin model
• Investigating the potential for a limited quantum speedup on protein lattice problems
• Quantum Annealing with chaotic driver Hamiltonians
• Quantum walk in a reinforced free-energy landscape: Quantum annealing with reinforcement
• Mapping State Transition Susceptibility in Quantum Annealing
• Validating a Two Qubit Non-Stoquastic Hamiltonian in Quantum Annealing
• Fighting Exponentially Small Gaps by Counterdiabatic Driving
• Effect of Quantum Statistics on Computational Power of Atomic Quantum Annealers
• The anomalously slow dynamics of inhomogeneous quantum annealing
• Noise Effects on Diabatic Quantum Annealing Protocols
• Hardware-efficient quantum annealing with error mitigation via classical shadow
• Flux-modulated tunable interaction regimes in two strongly nonlinear oscillators
• Ultrastrong capacitive coupling of flux qubits
• Sampling and the complexity of nature
• Three-Josephson Junctions Flux Qubit Couplings
• Improving adiabatic quantum factorization via chopped random-basis optimization
• Programming tools for Analogue Quantum Computing in the High-Performance Computing Context -- A Review
• Finding Hadamard matrices by a quantum annealing machine