Physics colloquium-“Exponential Quantum Advantage in Approximate Optimization of Hard Constraint Satisfaction Problems”

Eliot Kapit

Colorado School of Mines, Department of Physics

Abstract: A huge range of important problems in computer science–including task optimization, formal logic, encryption, and machine learning–can be solved by finding the sequence of binary variables that optimizes a cost function defined by a series of few-variable constraint relationships. Many of these problems are in the complexity class NP, and are in the worst case, and often the typical case, exponentially hard in the number of variables for all known methods. This hardness applies both to exact and approximate optimization, e.g. finding configurations with a value within a defined fraction of the global optimum. Fundamentally, the lack of any guided local minimum escape method ensures the hardness of both exact and approximate optimization classically, but the intuitive mechanism for approximation hardness in quantum algorithms based on Hamiltonian time evolution is not well understood. In this work, using the prototypically hard MAX-3-XORSAT problem class, we explore this question. We conclude that the mechanisms for quantum exact and approximation hardness are fundamentally distinct. We qualitatively identify why traditional methods such as high depth quantum adiabatic optimization algorithms are not reliably good approximation algorithms. We propose a new spectral folding optimization method that does not suffer from these issues and study it analytically and numerically. We consider random rank-3 hypergraphs including extremal planted solution instances, where the ground state satisfies an anomalously high fraction of constraints compared to truly random problems. We show that, if we define the energy to be $E = N_{\mathrm{unsat}}-N_{\mathrm{sat}}$, then spectrally folded quantum optimization will return states with energy $E \leq A E_{\mathrm{GS}}$ (where $E_{\rm GS}$ is the ground state energy) in polynomial time, where conservatively, $A \simeq 0.6$. We thoroughly benchmark variations of spectrally folded quantum optimization for random classically approximation-hard (planted solution) instances in simulation, and find performance consistent with this prediction. We do not claim that this approximation guarantee holds for all possible hypergraphs, though our algorithm’s mechanism can likely generalize widely. These results suggest that quantum computers are more powerful for approximate optimization than had been previously assumed.

The preprint on this is on arxiv: https://arxiv.org/abs/2312.06104

Pre-seminar snacks will be served in CoorsTek 150 from 3:30-4:00pm; lecture will take place in CTLM102.