Exponential Enhancement of the Efficiency of Quantum Annealing by Non-Stochastic Hamiltonians

Abstract

Non-stoquastic Hamiltonians have both positive and negative signs in off-diagonal elements in their matrix representation in the standard computational basis and thus cannot be simulated efficiently by the standard quantum Monte Carlo method due to the sign problem. We describe our analytical studies of this type of Hamiltonians with infinite-range non-random as well as random interactions from the perspective of possible enhancement of the efficiency of quantum annealing or adiabatic quantum computing. It is shown that multi-body transverse interactions like $XX$ and $XXXXX$ with positive coefficients appended to a stoquastic transverse-field Ising model render the Hamiltonian non-stoquastic and reduce a first-order quantum phase transition in the simple transverse-field case to a second-order transition. This implies that the efficiency of quantum annealing is exponentially enhanced, because a first-order transition has an exponentially small energy gap (and therefore exponentially long computation time) whereas a second-order transition has a polynomially decaying gap (polynomial computation time). The examples presented here represent rare instances where strong quantum effects, in the sense that they cannot be efficiently simulated in the standard quantum Monte Carlo, have analytically been shown to exponentially enhance the efficiency of quantum annealing for combinatorial optimization problems.

14 pages, 8 figures. v2: additional section; v3: minor revision

References in corpus (15)

• Mathematical Foundation of Quantum Annealing
• Bounds for the adiabatic approximation with applications to quantum computation
• Realizable Hamiltonians for Universal Adiabatic Quantum Computers
• Adiabatic approximation with exponential accuracy for many-body systems and quantum computation
• Quantum annealing with antiferromagnetic fluctuations
• 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
• Reexamining classical and quantum models for the D-Wave One processor
• A Quantum Approach to Classical Statistical Mechanics
• Many-body transverse interactions in the quantum annealing of the p-spin ferromagnet
• Convergence theorems for quantum annealing
• Convergence of Quantum Annealing with Real-Time Schrodinger Dynamics
• Adiabatic optimization versus diffusion Monte Carlo
• Macroscopic quantum tunneling and quantum-classical phase transitions of the escape rate in large spin systems
• Modelling of trends in Twitter using retweet graph dynamics

Cited by in corpus (34)

• Quantum Annealing for Industry Applications: Introduction and Review
• Counterdiabaticity and the quantum approximate optimization algorithm
• Exponential Speedup of Quantum Annealing by Inhomogeneous Driving of the Transverse Field
• Improving quantum annealing of the ferromagnetic $p$-spin model through pausing
• Digitized-Counterdiabatic Quantum Optimization
• Two-parameter counter-diabatic driving in quantum annealing
• Mean field analysis of reverse annealing for code-division multiple-access multiuser detection
• Digitized Adiabatic Quantum Factorization
• Designing Quantum Annealing Schedules using Bayesian Optimization
• Direct comparison of quantum and simulated annealing on a fully-connected Ising ferromagnet
• Variationally Scheduled Quantum Simulation
• Circumventing superexponential runtimes for hard instances of quantum adiabatic optimization
• Effective Hamiltonians for interacting superconducting qubits -- local basis reduction and the Schrieffer-Wolff transformation
• Greedy parameter optimization for diabatic quantum annealing
• Standard quantum annealing outperforms adiabatic reverse annealing with decoherence
• Quantum Annealing with Trigger Hamiltonians: Application to 2-SAT and Nonstoquastic Problems
• Counterdiabatic Reverse Annealing
• Exponentially-enhanced quantum sensing with many-body phase transitions
• Mean-Field Solution of the Weak-Strong Cluster Problem for Quantum Annealing with Stoquastic and Non-Stoquastic Catalysts
• Effective spin models of Kerr-nonlinear parametric oscillators for quantum annealing
• Stoquasticity in circuit QED
• Theoretical survey of unconventional quantum annealing methods applied to adifficult trial problem
• Phase transitions in the frustrated Ising ladder with stoquastic and nonstoquastic catalysts
• Locally Suppressed Transverse-Field Protocol for Diabatic Quantum Annealing
• Eigenvalue-invariant transformation of Ising problem for anti-crossing mitigation in quantum annealing
• Improving nonstoquastic quantum annealing with spin-reversal transformations
• Exact expression of the energy gap at first-order quantum phase transitions of a non-stoquastic Hamiltonian
• Nonstoquastic catalyst for bifurcation-based quantum annealing of ferromagnetic $p$-spin model
• Quantum annealing showing an exponentially small success probability despite a constant energy gap with polynomial energy
• Quantum Annealing with chaotic driver Hamiltonians
• Time-resolved tomography of a driven adiabatic quantum simulation
• Reduction of the energy-gap scaling by coherent catalysis in models of quantum annealing
• Convergence condition of simulated quantum annealing with a non-stoquastic catalyst
• The anomalously slow dynamics of inhomogeneous quantum annealing