Scaling advantage of QAOA on large quantum optimization problems

Quantum computing has the potential to speed up the solution of optimization problems dramatically. Since such problems are important in applications ranging from finance to energy, researchers have expended considerable effort in developing algorithms that can demonstrate quantum optimization speedups. One such algorithm is the quantum approximate optimization algorithm (QAOA). 

But despite extensive study of QAOA, an important gap remains: proof that it can scale better than classical solvers on large problems. To close this gap, researchers at JPMorgan Chase, Quantinuum and the U.S. Department of Energy’s (DOE) Argonne National Laboratory investigated QAOA on the low autocorrelation binary sequences (LABS) problem. The work appeared in the journal Science Advances.

The problem is important in signal processing applications, but classical solvers for the LABS problem typically fail to obtain high-quality solutions even at moderate sizes.

“We decided to use LABS with QAOA for several reasons,” said Jeffrey Larson, a computational scientist in Argonne’s Mathematics and Computer Science Division and a co-author of the study. ​“We were intrigued by the possibility of using QAOA for large problems where classical methods prove intractable. And we were motivated by the fact that LABS has only one instance per problem size, enabling us to study the scaling where classical methods become infeasible.”

For the study, the researchers augmented QAOA with a quantum minimum-finding procedure that identifies states with small values until the minimum is found. Using constant-depth QAOA with this extension, they obtained a significant speedup over exhaustive search for the LABS problem and better scaling than with the best-known classical heuristics (see Fig. 1). 

The team also implemented an algorithm-specific error detection scheme that relies on symmetry verification to improve the fidelity of the QAOA state under local noise. Using the scheme, the researchers executed QAOA for the LABS problem on Quantinuum trapped-ion quantum processors, reducing the impact of noise on solution quality by up to 65%. 

The researchers emphasize that this work was done in an idealized setting and that other algorithms may be well suited for the LABS problem. But they see the work as evidence for the utility of QAOA as an algorithmic component that enables quantum speedups.

For the paper reporting the study, see Ruslan Shaydulin et al., ​“Evidence of scaling advantage for the quantum approximate optimization algorithm on a classically intractable problem,” Science Advances 10(22), DOI: 10.1126/sciadv.adm67.