Circumventing superexponential runtimes for hard instances of quantum adiabatic optimization

Abstract

Classical optimization problems can be solved by adiabatically preparing the ground state of a quantum Hamiltonian that encodes the problem. The performance of this approach is determined by the smallest gap encountered during the evolution. Here, we consider the maximum independent set problem, which can be efficiently encoded in the Hamiltonian describing a Rydberg atom array. We present a general construction of instances of the problem for which the minimum gap decays superexponentially with system size, implying a superexponentially large time to solution via adiabatic evolution. The small gap arises from locally independent choices, which cause the system to initially evolve and localize into a configuration far from the solution in terms of Hamming distance. We investigate remedies to this problem. Specifically, we show that quantum quenches in these models can exhibit signatures of quantum many-body scars, which in turn, can circumvent the superexponential gaps. By quenching from a suboptimal configuration, states with a larger ground state overlap can be prepared, illustrating the utility of quantum quenches as an algorithmic tool.

12+3 pages, 8+4 figures, comments welcome

References in corpus (21)

• The density-matrix renormalization group in the age of matrix product states
• Probing many-body dynamics on a 51-atom quantum simulator
• Quantum Phases of Matter on a 256-Atom Programmable Quantum Simulator
• Programmable quantum simulation of 2D antiferromagnets with hundreds of Rydberg atoms
• Quantum Many-Body Scars and Weak Breaking of Ergodicity
• Quantum computing with neutral atoms
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
• Controlling many-body dynamics with driven quantum scars in Rydberg atom arrays
• Bounds for the adiabatic approximation with applications to quantum computation
• Emergent SU(2) dynamics and perfect quantum many-body scars
• Competing density-wave orders in a one-dimensional hard-boson model
• Designing Frustrated Quantum Magnets with Laser-Dressed Rydberg Atoms
• Microwave-engineering of programmable XXZ Hamiltonians in arrays of Rydberg atoms
• Quantum annealing with antiferromagnetic fluctuations
• Quantum optimization with arbitrary connectivity using Rydberg atom arrays
• Noise resistance of adiabatic quantum computation using random matrix theory
• 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
• Spatially tunable spin interactions in neutral atom arrays
• Experimental demonstration of perturbative anticrossing mitigation using non-uniform driver Hamiltonians
• The quantum adiabatic search with decoherence in the instantaneous energy eigenbasis

Cited by in corpus (11)

• Demonstration of weighted graph optimization on a Rydberg atom array using local light-shifts
• Trimer quantum spin liquid in a honeycomb array of Rydberg atoms
• Quantum adiabatic optimization with Rydberg arrays: localization phenomena and encoding strategies
• Counterdiabatic Driving with Performance Guarantees
• Learning topological states from randomized measurements using variational tensor network tomography
• Approximating maximum independent set on Rydberg atom arrays using local detunings
• Approximate combinatorial optimization with Rydberg atoms: the barrier of interpretability
• Generation of quantum phases of matter and finding a maximum-weight independent set of unit-disk graphs using Rydberg atoms
• Hardness-dependent quantum adiabatic schedules for the maximum-independent-set problem
• Topological order in symmetric blockade structures
• Quantum Hamiltonian Algorithms for Maximum Independent Sets