The Quantum Approximate Optimization Algorithm (QAOA) applied to a binary combinatorial optimization problem. Nodes represent binary variables and edges represent weighted couplings (dark for positive and light for negative couplings). Across successive layers, QAOA drives the state from a uniform superposition (purple) toward a near‑optimal binary assignment (red and blue). Image: Abid Khan and Minzhao Liu, JPMorgan Chase
This project is developing numerical techniques on ALCF supercomputers to predict the performance and optimal parameters of the Quantum Approximate Optimization Algorithm (QAOA) for large combinatorial problems, providing insights into its potential for achieving quantum advantage in optimization.
Strong theoretical evidence exists for the power of quantum computers to tackle a wide range of problems out of the reach of classical techniques. Among the many applications of quantum computing, a particularly promising domain is optimization due to the ubiquity and high impact of optimization problems. The Quantum Approximate Optimization Algorithm (QAOA) has emerged as a promising approach for solving combinatorial optimization problems with some evidence suggesting it may offer a quantum advantage on early fault-tolerant quantum computers. However, QAOA is challenging to study analytically, motivating the use of numerical methods that require supercomputers, as it involves exponentially expensive simulations of quantum systems.
In this project, researchers will develop numerical techniques to predict QAOA performance for arbitrarily large problems. The team’s techniques can compute finite-size corrections to the infinite-size-limit QAOA performance, where the infinite-size performance was computed in prior work. The outcome of this research will be two-fold. First, the computed quantities would enable accurate QAOA performance estimation at large problem sizes beyond classical simulability, which would, in turn, allow resource estimation, concrete comparisons with classical solvers, and clarification of the requirements for quantum advantage in optimization. Second, the resulting values would allow the calculation of optimal QAOA hyperparameters without actually performing QAOA optimization via classical simulation or quantum execution. Together, these findings would provide evidence for the potential for QAOA to serve as a credible candidate for achieving quantum advantage.
