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.

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

References in corpus (39)

• Ising formulations of many NP problems
• Quantum Annealing in the Transverse Ising Model
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Quantum annealing with more than one hundred qubits
• Theory of Quantum Annealing of an Ising Spin Glass
• Quantum Annealing and Analog Quantum Computation
• Defining and detecting quantum speedup
• Mathematical Foundation of Quantum Annealing
• Bounds for the adiabatic approximation with applications to quantum computation
• What is the Computational Value of Finite Range Tunneling?
• Quantum Optimization of Fully-Connected Spin Glasses
• Quantum versus Classical Annealing of Ising Spin Glasses
• Realizable Hamiltonians for Universal Adiabatic Quantum Computers
• First order phase transition in the Quantum Adiabatic Algorithm
• Adiabatic approximation with exponential accuracy for many-body systems and quantum computation
• Glassy Chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines
• Quantum annealing with antiferromagnetic fluctuations
• Energy gaps in quantum first-order mean-field-like transitions: The problems that quantum annealing cannot solve
• Strengths and weaknesses of weak-strong cluster problems: A detailed overview of state-of-the-art classical heuristics vs quantum approaches
• 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
• Exponential Complexity of the Quantum Adiabatic Algorithm for certain Satisfiability Problems
• Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly
• A Quantum Approach to Classical Statistical Mechanics
• Tunneling and speedup in quantum optimization for permutation-symmetric problems
• Simulated Quantum Annealing Can Be Exponentially Faster than Classical Simulated Annealing
• Many-body transverse interactions in the quantum annealing of the p-spin ferromagnet
• Unraveling Quantum Annealers using Classical Hardness
• Convergence theorems for quantum annealing
• Scaling analysis and instantons for thermally-assisted tunneling and Quantum Monte Carlo simulations
• A note on the switching adiabatic theorem
• Quantum Effects in Neural Networks
• Convergence of Quantum Annealing with Real-Time Schrodinger Dynamics
• Heavy tails in the distribution of time-to-solution for classical and quantum annealing
• Adiabatic optimization versus diffusion Monte Carlo
• Practical engineering of hard spin-glass instances
• Open system quantum annealing in mean field models with exponential degeneracy
• 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 (63)

• Perspectives of quantum annealing: Methods and implementations
• Quantum Annealing for Industry Applications: Introduction and Review
• Observation of topological phenomena in a programmable lattice of 1,800 qubits
• Quantum annealing with a network of all-to-all connected, two-photon driven Kerr nonlinear oscillators
• Counterdiabaticity and the quantum approximate optimization algorithm
• Reverse annealing for the fully connected $p$-spin model
• Nonstoquastic Hamiltonians and Quantum Annealing of an Ising Spin Glass
• A Coherent Quantum Annealer with Rydberg Atoms
• Exponential Speedup of Quantum Annealing by Inhomogeneous Driving of the Transverse Field
• Demonstration of nonstoquastic Hamiltonian in coupled superconducting flux qubits
• Quantum annealing of the $p$-spin model under inhomogeneous transverse field driving
• Fidelity witnesses for fermionic quantum simulations
• Improving quantum annealing of the ferromagnetic $p$-spin model through pausing
• Role of Non-stoquastic Catalysts in Quantum Adiabatic Optimization
• Non-Stoquastic Interactions in Quantum Annealing via the Aharonov-Anandan Phase
• Digitized-Counterdiabatic Quantum Optimization
• Floquet quantum simulation with superconducting qubits
• Readiness of Quantum Optimization Machines for Industrial Applications
• Two-parameter counter-diabatic driving in quantum annealing
• Mean field analysis of reverse annealing for code-division multiple-access multiuser detection
• Relation between quantum fluctuations and the performance enhancement of quantum annealing in a nonstoquastic Hamiltonian
• Digitized Adiabatic Quantum Factorization
• The Wishart planted ensemble: A tunably-rugged pairwise Ising model with a first-order phase transition
• Constrained quantum annealing of graph coloring
• Direct comparison of quantum and simulated annealing on a fully-connected Ising ferromagnet
• Designing Quantum Annealing Schedules using Bayesian Optimization
• Variationally Scheduled Quantum Simulation
• Robust Quantum Control for Adiabatic Quantum Computation
• Effective Hamiltonians for interacting superconducting qubits -- local basis reduction and the Schrieffer-Wolff transformation
• Circumventing superexponential runtimes for hard instances of quantum adiabatic optimization
• Greedy parameter optimization for diabatic quantum annealing
• Understanding Quantum Tunneling using Diffusion Monte Carlo Simulations
• Standard quantum annealing outperforms adiabatic reverse annealing with decoherence
• Quantum phase transition with inhomogeneous driving in the Lechner-Hauke-Zoller model
• Quantum Speed-Up at Zero Temperature via Coherent Catalysis
• Viewing Vanilla Quantum Annealing Through Spin Glasses
• Counterdiabatic Reverse Annealing
• Quantum Annealing with Trigger Hamiltonians: Application to 2-SAT and Nonstoquastic Problems
• Permutation Matrix Representation Quantum Monte Carlo
• Exponentially-enhanced quantum sensing with many-body phase transitions
• Statistical-mechanical analysis of compressed sensing for Hamiltonian estimation of Ising spin glass
• Mean-Field Solution of the Weak-Strong Cluster Problem for Quantum Annealing with Stoquastic and Non-Stoquastic Catalysts
• Superconducting qubit circuit emulation of a vector spin-1/2
• Quantum accelerated approach to the thermal state of classical spin systems with applications to pattern-retrieval in the Hopfield neural network
• Effective spin models of Kerr-nonlinear parametric oscillators for quantum annealing
• Stoquasticity in circuit QED
• Dynamics of Order Parameters of Non-stoquastic Hamiltonians in the Adaptive Quantum Monte Carlo Method
• Theoretical survey of unconventional quantum annealing methods applied to adifficult trial problem
• Locally Suppressed Transverse-Field Protocol for Diabatic Quantum Annealing
• Phase transitions in the frustrated Ising ladder with stoquastic and nonstoquastic catalysts
• Localization in the constrained quantum annealing of graph coloring
• Eigenvalue-invariant transformation of Ising problem for anti-crossing mitigation in quantum annealing
• Dynamics of open quantum systems by interpolation of von Neumann and classical master equations, and its application to quantum annealing
• Exact expression of the energy gap at first-order quantum phase transitions of a non-stoquastic Hamiltonian
• Improving nonstoquastic quantum annealing with spin-reversal transformations
• 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
• Validating a Two Qubit Non-Stoquastic Hamiltonian in Quantum Annealing
• 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