Quantum Computing Beats Best Classical Method for Complex Graph Problems

Integer graph problems present a significant challenge in optimisation, yet quantum algorithms addressing these remain largely under-investigated. Anuj Apte, Sami Boulebnane, and Yuwei Jin, all from Global Technology Applied Research at JPMorganChase, alongside Sivaprasad Omanakuttan, Michael A. Perlin, Ziqi Wang, and Ruslan Shaydulin, demonstrate the potential of the Quantum Approximate Optimisation Algorithm (QAOA) when applied to integer problems encoded using qudits. Their research derives a novel iterative formula for depth-expectation on high-girth regular graphs, revealing parameter regimes where QAOA surpasses the performance of the established Frieze-Jerrum semi-definite programming (SDP) algorithm for the Max-k-Cut problem. Furthermore, the team introduces a new degree-of-saturation heuristic which, while currently competitive, may be overtaken by QAOA at greater depths, suggesting a pathway towards demonstrable quantum advantage in integer optimisation.

This work focuses on applying QAOA to integer problems represented on graphs, where each variable is encoded using a qudit, a quantum digit with more than two levels.

A key accomplishment of the study is the derivation of a general iterative formula for calculating the expected performance of QAOA at a given depth on high-girth regular graphs of any size. Critically, the computational cost of this formula scales exponentially with the QAOA depth but remains independent of the graph’s size, offering a pathway to efficient analysis.
Evaluating this formula specifically for the Max-k-Cut problem, with a QAOA depth of four, reveals parameter regimes where the quantum algorithm outperforms the Frieze-Jerrum semi-definite programming (SDP) algorithm. This SDP algorithm currently provides the best-known worst-case guarantee for approximating solutions to this type of problem.

Specifically, QAOA demonstrates superior performance for k = 3 with graph degrees up to 10, and for k = 4 with degrees up to 40. To establish a robust classical benchmark, the researchers also developed a new heuristic algorithm, inspired by the degree-of-saturation method, which empirically surpasses both the Frieze-Jerrum algorithm and shallow-depth QAOA implementations.

However, numerical evidence suggests that QAOA may ultimately overtake this new heuristic at depths of up to 20, indicating a potential trajectory towards quantum advantage. The derived iterative formula enables optimization of QAOA parameters across various graph configurations, facilitating performance analysis independent of specific graph instances.

This generalization to integer variables substantially broadens the applicability of QAOA, opening new possibilities for tackling complex optimization challenges in fields ranging from portfolio optimization to resource allocation. Each integer variable is encoded within a qudit, extending beyond traditional binary optimization approaches. Researchers derived a general iterative formula to calculate depth-p expectation values on high-girth regular graphs, a crucial step for analysing performance without dependence on graph size.

The computational cost of this formula scales exponentially with depth, specifically O(p k^(4p+4)), but remains independent of the graph’s dimensions. To assess performance on the Max-k-Cut problem, the team evaluated the formula for k = 3 and k = 4, identifying parameter regimes where QAOA outperforms the Frieze-Jerrum semi-definite programming (SDP) algorithm.

Specifically, QAOA at depth p = 4 surpasses the Frieze, Jerrum SDP algorithm for k = 3 with degree d ≤ 10, and for k = 4 with d ≤ 40. A new heuristic algorithm, inspired by the degree-of-saturation method, was introduced as a stronger classical baseline, demonstrating empirically superior performance to both the Frieze-Jerrum algorithm and shallow-depth QAOA.

This work leverages a framework for evaluating QAOA performance on the Sherrington, Kirkpatrick (SK) model and the Max-Cut problem on regular graphs. By focusing on tree tensor network contraction, the team minimized the computational burden associated with evaluating QAOA expectations, achieving a runtime of O(p^2 k^(2p+2) log k) through simplification based on the Hadamard transform.

The iterative formula enables optimization of QAOA parameters across all graphs with a given degree, facilitating the exploration of quantum advantage in integer optimization. This formula, applicable to k-level qudits, covers arbitrary values of k, degree d, and depth p for graphs exhibiting a girth of at least 2p + 2.

The computational cost of evaluating this formula is exponential in depth p, specifically O(p 4 k 4p+4 ), but crucially remains independent of the graph size. Analysis focused on the Max-k-Cut problem with k = 4, identifying parameter regimes where QAOA outperforms the Frieze-Jerrum semi-definite programming (SDP) algorithm.

These superior results were observed for graphs with degree d ≤ 10 and k = 4, coupled with d ≤ 40. A new heuristic algorithm, based on the degree-of-saturation, was also introduced as a classical baseline, demonstrating empirical outperformance against both the Frieze-Jerrum algorithm and shallow-depth QAOA implementations.

However, numerical evidence suggests that QAOA may surpass this heuristic at depths p ≤ 20. Simplification of the iterative formula, leveraging the Hadamard transform for edge costs dependent on label differences, reduces the runtime to O(p 2 k 2p+2 log k). This work establishes a framework for applying QAOA to optimization problems featuring integer-valued variables, substantially broadening the scope of potential applications. The work focuses on the Max-k-Cut problem, deriving a formula to efficiently evaluate the performance of QAOA at a given depth on high-girth graphs, irrespective of the graph’s size.

This evaluation allows for optimization of QAOA parameters and comparison with established classical algorithms. Analysis reveals that QAOA surpasses the Frieze-Jerrum semi-definite programming algorithm for specific parameter ranges, namely for Max-k-Cut with k=3 and graph degree up to 10, and for k=4 with degree up to 40.

A newly introduced classical heuristic algorithm, based on the degree-of-saturation method, initially outperforms both the Frieze-Jerrum algorithm and QAOA, but numerical evidence suggests QAOA may exceed this heuristic at greater depths. These findings represent a significant step towards demonstrating quantum advantage in solving integer combinatorial optimization problems, providing the strongest evidence to date of a quantum algorithm exceeding the performance of the best known classical worst-case guarantees for such problems at scale.

The authors acknowledge that the computational cost of their iterative formula grows exponentially with the depth of the QAOA circuit. Furthermore, the current analysis is limited to high-girth graphs and specific values of k. Future research could explore extending the analysis to more general graph structures and investigating the performance of QAOA with different mixer circuits, potentially leading to further improvements in solution quality and demonstrating a more substantial quantum advantage.