JPMorganChase finds QAOA shows quantum speedups for complex optimization problems

JPMorganChase and Argonne National Laboratory report evidence suggesting quantum algorithms may finally overcome limitations that have plagued complex optimization for decades. The research, accepted in Physical Review Letters, focuses on problems where even slight improvements in one area can negatively impact others, illustrated by scenarios like routing 10,000 packages across 500 trucks. The company states that by establishing a duality with the well-studied Sherrington-Kirkpatrick model, the team was able to assess the Quantum Approximate Optimization Algorithm (QAOA) on problems too large for classical computers, potentially signaling a breakthrough in achieving optimal solutions.

QAOA Performance Benchmarked Against Sherrington-Kirkpatrick Model

A surprising duality between quantum algorithms and vibrating springs has allowed researchers to benchmark the performance of a promising quantum optimization technique on problems mirroring real-world logistical challenges. JPMorganChase, collaborating with Argonne National Laboratory, has presented evidence suggesting the Quantum Approximate Optimization Algorithm (QAOA) may outperform classical methods for complex optimization tasks, a feat elusive for many years. The team’s findings, accepted in Physical Review Letters, center on the Sherrington-Kirkpatrick (SK) model, a notoriously difficult problem used to simulate scenarios like portfolio construction and network design. The challenge lies in the scale of these problems; routing “10,000 packages across 500 trucks” exemplifies how interconnected variables create computational bottlenecks for classical algorithms. Unlike simpler problems, exhaustive searches become impossible as the number of variables increases, forcing organizations to settle for “good enough” solutions rather than the absolute best.

To overcome the limitations of simulating QAOA on classical computers, the researchers established a connection between the algorithm’s performance and a simplified physical system, a single quantum bit coupled to quantum harmonic oscillators. “We discovered a duality between the task of computing QAOA’s performance on large instances of the SK model and the simulation of a simple physical system,” explained the team. This innovative mapping allowed them to replace an exponentially complex calculation with a simulation achievable using matrix product states, enabling analysis of QAOA’s behavior with increasing circuit depth. The results indicate QAOA “efficiently solves the SK model in the average case,” providing the “strongest evidence to date” of its potential advantage. Importantly, this technique allows evaluation of solution quality without requiring a functioning quantum computer; the researchers emphasize that “when such hardware becomes available, there is strong evidence it will outperform classical approaches on this class of problems.” The team’s work extends beyond the SK model, suggesting broader applicability to other optimization challenges faced by businesses daily.

The pursuit of quantum advantage in practical optimization problems has long been hampered by the limitations of classical simulation; accurately modeling the behavior of quantum algorithms on complex instances demands computational resources that quickly become intractable. This approach centers on the Sherrington-Kirkpatrick (SK) model, a disordered system frequently used as a benchmark for optimization algorithms due to its known optimal value, termed the Parisi value, providing a clear standard for comparison. The team established this connection, enabling their breakthrough. “Together, the mapping and the MPS simulation meant that the cost grew only modestly with circuit depth,” allowing for simulations of QAOA circuits with greater depth than previously possible. This spin-boson mapping isn’t merely a computational trick; it offers a method for evaluating the expected solution quality of QAOA without actually running the algorithm on quantum hardware.

JPMorgan Chase’s Global Technology Applied Research team is actively pursuing solutions to combinatorial optimization problems, a class of challenges that have stymied classical computation for decades. Unlike sorting algorithms that efficiently manage large datasets, problems like portfolio construction and logistics routing present interconnected variables where optimizing one element can detrimentally impact others. Organizations routinely accept suboptimal solutions due to the prohibitive cost of finding the absolute best outcome; from factory scheduling to hospital staffing, the true optimum often remains elusive. Recent work, published in Physical Review Letters in collaboration with Argonne National Laboratory, suggests a potential pathway forward using quantum algorithms. Researchers focused on the Quantum Approximate Optimization Algorithm (QAOA), a leading candidate for achieving quantum advantage. A key obstacle to evaluating QAOA’s performance on complex problems is the computational burden of simulating deep quantum circuits; current classical computers and quantum hardware are insufficient for these calculations. This translation allowed them to utilize matrix product states (MPS), a technique from many-body physics, to perform the simulation with a manageable computational cost.