Theoretical survey of unconventional quantum annealing methods applied to adifficult trial problem

Abstract

We consider a range of unconventional modifications to Quantum Annealing (QA), applied to an artificial trial problem with continuously tunable difficulty. In this problem, inspired by "transverse field chaos" in larger systems, classical and quantum methods are steered toward a false local minimum. To go from this local minimum to the global minimum, all N spins must flip, making this problem exponentially difficult to solve. We numerically study this problem by using a variety of new methods from the literature: inhomogeneous driving, adding transverse couplers, and other types of coherent oscillations in the transverse field terms (collectively known as RFQA). We show that all of these methods improve the scaling of the time to solution (relative to the standard uniform sweep evolution) in at least some regimes. Comparison of these methods could help identify promising paths towards a demonstrable quantum speedup over classical algorithms in solving some realistic problems with near-term quantum annealing hardware.

References in corpus (55)

• Ising formulations of many NP problems
• Quantum Annealing in the Transverse Ising Model
• Adiabatic Quantum Computing
• Quantum annealing with more than one hundred qubits
• Dynamics of a Quantum Phase Transition and Relaxation to a Steady State
• Quantum Annealing and Analog Quantum Computation
• Quantum Annealing: A New Method for Minimizing Multidimensional Functions
• Quantum Search by Local Adiabatic Evolution
• Perspectives of quantum annealing: Methods and implementations
• Observation of topological phenomena in a programmable lattice of 1,800 qubits
• Minimizing irreversible losses in quantum systems by local counter-diabatic driving
• What is the Computational Value of Finite Range Tunneling?
• Reverse Quantum Annealing Approach to Portfolio Optimization Problems
• Demonstration of a scaling advantage for a quantum annealer over simulated annealing
• Quantum Speedup by Quantum Annealing
• Solving the Optimal Trading Trajectory Problem Using a Quantum Annealer
• Scaling advantage in quantum simulation of geometrically frustrated magnets
• Compiling quantum circuits to realistic hardware architectures using temporal planners
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Quantum annealing with antiferromagnetic fluctuations
• Energy gaps in quantum first-order mean-field-like transitions: The problems that quantum annealing cannot solve
• Power of Pausing: Advancing Understanding of Thermalization in Experimental Quantum Annealers
• Reverse annealing for the fully connected $p$-spin model
• Understanding Quantum Tunneling through Quantum Monte Carlo Simulations
• Modernizing Quantum Annealing using Local Searches
• Nonstoquastic Hamiltonians and Quantum Annealing of an Ising Spin Glass
• The forward approximation as a mean field approximation for the Anderson and Many Body Localization transitions
• Quantum Adiabatic Evolution Algorithms versus Simulated Annealing
• Exponential Enhancement of the Efficiency of Quantum Annealing by Non-Stochastic Hamiltonians
• Exponential Speedup of Quantum Annealing by Inhomogeneous Driving of the Transverse Field
• The quantum adiabatic algorithm and scaling of gaps at first order quantum phase transitions
• Quantum Adiabatic Evolution Algorithms with Different Paths
• Different Strategies for Optimization Using the Quantum Adiabatic Algorithm
• The many-body localized phase of the quantum random energy model
• Dissipation in adiabatic quantum computers: Lessons from an exactly solvable model
• Quantum annealing of the $p$-spin model under inhomogeneous transverse field driving
• Clustering of non-ergodic eigenstates in quantum spin glasses
• Scaling analysis and instantons for thermally-assisted tunneling and Quantum Monte Carlo simulations
• Non-Stoquastic Interactions in Quantum Annealing via the Aharonov-Anandan Phase
• Quantum annealing with longitudinal bias fields
• Quantum algorithm for energy matching in hard optimization problems
• Quantum annealing via environment-mediated quantum diffusion
• Quantum Monte Carlo tunneling from quantum chemistry to quantum annealing
• Relation between quantum fluctuations and the performance enhancement of quantum annealing in a nonstoquastic Hamiltonian
• Relaxation vs. adiabatic quantum steady state preparation: which wins?
• On the optimal working point in dissipative quantum annealing
• Quantum-Assisted Genetic Algorithm
• Experimental and Theoretical Study of Thermodynamic Effects in a Quantum Annealer
• The Complexity of Stoquastic Local Hamiltonian Problems
• Quantum annealing of pure and random Ising chains coupled to a bosonic environment
• Thermalization in the Quantum Ising Model - Approximations, Limits, and Beyond
• Can quantum Monte Carlo simulate quantum annealing?
• Noise amplification at spin-glass bottlenecks of quantum annealing: a solvable model
• Perturbation theory approaches to Anderson and Many-Body Localization: some lecture notes
• The performance of the quantum adiabatic algorithm on spike Hamiltonians

Cited by in corpus (3)

• The quantum annealing gap and quench dynamics in the exact cover problem
• The equation of state of neutron stars and the role of nuclear experiments
• Quantum annealing sampling with a bias field