Quantum combinatorial optimization beyond the variational paradigm: simple schedules for hard problems

Abstract

Advances in quantum algorithms suggest a tentative scaling advantage on certain combinatorial optimization problems. Recent work, however, has also reinforced the idea that barren plateaus render variational algorithms ineffective on large Hilbert spaces. Hence, finding annealing protocols by variation ultimately appears to be difficult. Similarly, the adiabatic theorem fails on hard problem instances with first-order quantum phase transitions. Here, we show how to use the spin coherent-state path integral to shape the geometry of quantum adiabatic evolution, leading to annealing protocols at polynomial overhead that provide orders-of-magnitude improvements in the probability to measure optimal solutions, relative to linear protocols. These improvements are not obtained on a controllable toy problem but on randomly generated hard instances (Sherrington-Kirkpatrick and Maximum 2-Satisfiability), making them generic and robust. Our method works for large systems and may thus be used to improve the performance of state-of-the-art quantum devices.

12 pages, 11 figures

References in corpus (20)

• Adiabatic Quantum Computing
• Quantum computing for finance: overview and prospects
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
• Geometry and non-adiabatic response in quantum and classical systems
• Quantum critical dynamics in a 5000-qubit programmable spin glass
• Challenges and Opportunities in Quantum Optimization
• Benchmarking the Quantum Approximate Optimization Algorithm
• Optimal Protocols in Quantum Annealing and QAOA Problems
• Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
• First Order Quantum Phase Transition in Adiabatic Quantum Computation
• Intrinsic geometry of quantum adiabatic evolution and quantum phase transitions
• NP-hard but no longer hard to solve? Using quantum computing to tackle optimization problems
• Designing Quantum Annealing Schedules using Bayesian Optimization
• Quantum annealing speedup over simulated annealing on random Ising chains
• Comparing Three Generations of D-Wave Quantum Annealers for Minor Embedded Combinatorial Optimization Problems
• Bounds on approximating Max $k$XOR with quantum and classical local algorithms
• Mean-Field Approximate Optimization Algorithm
• Comparing the hardness of MAX 2-SAT problem instances for quantum and classical algorithms
• Anomalous distribution of magnetization in an Ising spin glass with correlated disorder
• Adiabatic Bottlenecks in Quantum Annealing and Nonequilibrium Dynamics of Paramagnons