Qiskit Quantum Seminar

Currently Playing: What ensures approximation hardness for quantum algorithms? | Qiskit Seminar Series w/ Eliot Kapit

Episode 165 Constraint satisfaction problems are an important area of computer science. Many of these problems are in the complexity class NP which is exponentially hard for all known methods, both for worst cases and often typical. Fundamentally, the lack of any guided local minimum escape method ensures both exact and approximate classical optimization are hard, but the intuitive mechanism(s) for approximation hardness in quantum algorithms are poorly understood. For algorithms simulating Hamiltonian time evolution, we explore this question using the prototypically hard MAX-3-XORSAT problem class. We conclude that the mechanisms for quantum exact and approximation hardness are fundamentally distinct. We qualitatively identify why traditional methods such as quantum adiabatic optimization are not good approximation algorithms. We propose new spectral filtering optimization methods to escape these issues, and study them analytically and numerically. We consider random rank-3 hypergraphs including extremal planted solution instances, where the ground state satisfies a much higher fraction of constraints than truly random problems. We show that, if we define the energy to be $E = N_{\mathrm{unsat}}-N_{\mathrm{sat}}$, spectrally filtered quantum optimization will return states with $E \leq q_m E_{\mathrm{GS}}$ (where $E_{\rm GS}$ is the ground state energy) in low-order polynomial time, where conservatively, $q_m \simeq 0.6$. This is in contrast to $q_m \to 0$ for the hardest instances with classical searches. We thus conjecture that random hypergraph instances, including extremal instances with planted partial solutions, are efficiently approximable with high probability. We do not claim that this approximation guarantee holds for all possible hypergraphs, but at present do not know what hypergraph properties would break spectrally filtered quantum optimization. These results suggest that quantum computers are more powerful for approximate optimization than had been previously assumed. Eliot Kapit is an Associate Professor of Physics at Colorado School of Mines and director of its interdisciplinary Quantum Engineering programs. He received his PhD in Physics from Cornell University, and did postdoctoral work at Oxford and the City University of New York before starting a faculty position at Tulane University. From there he moved to Mines where he has worked ever since. His research focuses on novel quantum algorithms and speedup mechanisms for hard optimization problems, many-body dynamics, error correction, and device and protocol design for near-term quantum computers.