Iterative classical superadiabatic algorithm for combinatorial optimization

Abstract

We consider a classical and superadiabatic version of an iterative quantum adiabatic algorithm to solve combinatorial optimization problems. This algorithm is deterministic because it is based on purely classical dynamics, that is, it does not rely on any stochastic approach to mimic quantum dynamics. Moreover, use of shortcuts to adiabaticity makes the algorithm independent of the annealing time. We apply this algorithm to a certain class of hard instances of the 3-SAT problem. We find that more than 90\% of such 64-bits hard instances can be resolved by a few iteration. Our approach can also be used to analyze properties of instances themselves apart from stochastic uncertainty and shortage of adiabaticity.

arXiv commenthyperref is not available because of version mismatch of texlive

References in corpus (21)

• 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
• Shortcuts to adiabaticity: concepts, methods, and applications
• Theory of Quantum Annealing of an Ising Spin Glass
• Quantum Annealing and Analog Quantum Computation
• Assisted finite-rate adiabatic passage across a quantum critical point: Exact solution for the quantum Ising model
• Exponential Speedup of Quantum Annealing by Inhomogeneous Driving of the Transverse Field
• Does Adiabatic Quantum Optimization Truly Fail for NP-complete problems?
• Shortcuts to adiabaticity for quantum annealing
• Quantum annealing of the $p$-spin model under inhomogeneous transverse field driving
• Rapid counter-diabatic sweeps in lattice gauge adiabatic quantum computing
• Experimental demonstration of perturbative anticrossing mitigation using non-uniform driver Hamiltonians
• Algorithmic approach to adiabatic quantum optimization
• Quantum Annealing in a Kinetically Constrained System
• Steering random spin systems to speed up the quantum adiabatic algorithm
• Shortcuts to Adiabatic Classical Spin Dynamics Mimicking Quantum Annealing
• Shortcuts to adiabaticity in the infinite-range Ising model by mean-field counter-diabatic driving
• Quantum phase transition with inhomogeneous driving in the Lechner-Hauke-Zoller model
• Engineering non-equilibrium quantum phase transitions via causally gapped Hamiltonians
• Approaching the Ground State of a Quantum Spin Glass using a Zero-Temperature Quantum Monte Carlo