Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem

The quantum approximate optimization algorithm (QAOA) is a leading candidate algorithm for solving optimization problems on quantum computers. However, the potential of QAOA to tackle classically intractable problems remains unclear. In this paper, we perform an extensive numerical investigation of QAOA on the Low Autocorrelation Binary Sequences (LABS) problem. The rapid growth of the problem's complexity with the number of spins N makes it classically intractable even for moderately sized instances, with the best-known heuristics observed to fail to find a good solution for problems with N⪆200. We perform noiseless simulations with up to 40 qubits and observe that out to this system size, the runtime of QAOA with fixed parameters and a constant number of layers scales better than branch-and-bound solvers, which are the state-of-the-art exact solvers for LABS. The combination of QAOA with quantum minimum-finding on an idealized quantum computer gives the best empirical scaling of any algorithm for the LABS problem. We demonstrate experimental progress in compiling and executing QAOA for the LABS problem using an algorithm-specific error detection scheme on Quantinuum trapped-ion processors.

Ruslan Shaydulin is a quantum algorithms researcher at the Global Technology Applied Research center at JPMorgan Chase. Ruslan's research centers on applying quantum algorithms to classical problems, with a focus on optimization and machine learning. Prior to joining JPMorgan Chase, Ruslan was a Maria Goeppert Mayer fellow at Argonne National Laboratory.