Circumventing superexponential runtimes for hard instances of quantum adiabatic optimization
arXiv:2306.13131 · doi:10.1103/PhysRevResearch.6.013271
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.
arXiv comment12+3 pages, 8+4 figures, comments welcome
References in corpus (40)
- The density-matrix renormalization group in the age of matrix product states
- Probing many-body dynamics on a 51-atom quantum simulator
- Quantum Annealing in the Transverse Ising Model
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Fast quantum gates for neutral atoms
- The ITensor Software Library for Tensor Network Calculations
- Quantum many-body scars
- 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
- Optimal Control at the Quantum Speed Limit
- Quantum computing with neutral atoms
- Robustness of adiabatic quantum computation
- 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
- Periodic orbits, entanglement and quantum many-body scars in constrained models: matrix product state approach
- Competing density-wave orders in a one-dimensional hard-boson model
- Anderson localization casts clouds over adiabatic quantum optimization
- Adiabatic Quantum Computation in Open Systems
- Designing Frustrated Quantum Magnets with Laser-Dressed Rydberg Atoms
- Microwave-engineering of programmable XXZ Hamiltonians in arrays of Rydberg atoms
- Interacting Fibonacci anyons in a Rydberg gas
- Prospects for Quantum Enhancement with Diabatic Quantum Annealing
- Quantum annealing with antiferromagnetic fluctuations
- Quantum optimization with arbitrary connectivity using Rydberg atom arrays
- A quantum magnetic analogue to the critical point of water
- First Order Quantum Phase Transition in Adiabatic Quantum Computation
- Complex density wave orders and quantum phase transitions in a model of square-lattice 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
- Role of Non-stoquastic Catalysts in Quantum Adiabatic Optimization
- Experimental demonstration of perturbative anticrossing mitigation using non-uniform driver Hamiltonians
- The quantum adiabatic search with decoherence in the instantaneous energy eigenbasis
- The Effects of the Problem Hamiltonian Parameters on the Minimum Spectral Gap in Adiabatic Quantum Optimization
- Quantum Speed-Up at Zero Temperature via Coherent Catalysis
- Noise amplification at spin-glass bottlenecks of quantum annealing: a solvable model
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