QAOA Performance Rivals Goemans-Williamson Algorithm

Evgenii Dolzhkov and colleagues at University of Tartu investigate the performance of the Quantum Approximate Optimisation Algorithm (QAOA) when applied to the Max-Cut problem, offering a realistic assessment of its capabilities on contemporary quantum hardware. They present a unique evaluation methodology, treating QAOA as a ‘black-box’ optimiser with default settings, mirroring how an end-user would typically interact with the algorithm. By employing benchmark graphs that reflect real-world structures and utilising a per-shot statistical framework, the team compare QAOA’s outputs with the established classical Goemans-Williamson algorithm. The study moves beyond assessing QAOA’s theoretical potential and instead focuses on its practical applicability, providing valuable insight into its current limitations and establishing a key framework for evaluating future advancements in quantum optimisation.

Default QAOA settings fail to match classical performance on benchmark network graphs

QAOA surpassed a Goemans-Williamson (GW) expectation in fewer than 10% of runs, a stark contrast to the classical Goemans-Williamson algorithm which consistently exceeded its own expectation with minimal sampling. The Max-Cut problem, a classic NP-hard combinatorial optimisation challenge, seeks to partition the vertices of a graph into two disjoint sets such that the number of edges crossing the partition is maximised. The Goemans-Williamson algorithm, a semi-definite programming relaxation approach, provides a well-established and effective classical solution to this problem, often serving as a benchmark for quantum algorithms. Previously, assessing QAOA’s viability necessitated extensive parameter tuning, a process involving optimising the angles within the quantum circuit to achieve peak performance. This current work, however, observed performance without such optimisation, mirroring a typical user experience and revealing a substantial performance gap under realistic conditions. The black-box approach, utilising benchmark graphs resembling real-world networks, including those found in social networks, transportation systems, and logistical challenges, establishes a new baseline for evaluating quantum optimisation algorithms and highlights the significant hurdles to demonstrating a practical quantum speed-up. Researchers evaluated specific, off-the-shelf Quantum Approximate Optimisation Algorithm (QAOA) implementations without any parameter tuning, an important distinction from studies focusing on theoretical potential, which often assume idealised conditions and extensive optimisation routines.

Benchmark graphs, constructed to represent practical networks and avoid artificially simple instances designed to favour quantum algorithms, revealed a consistent trend in performance comparisons. The Goemans-Williamson algorithm typically required fewer than three random hyperplane samples to exceed its own expectation, indicating its efficiency and robustness. This efficiency stems from its ability to provide a provable approximation guarantee, ensuring a solution within a certain factor of the optimal solution. Per-shot analysis, tracking output quality with varying circuit executions, essentially measuring the algorithm’s performance with increasing computational resources, showed that current QAOA implementations, evaluated under default settings, do not surpass classical techniques, even with limited computational effort. The number of ‘shots’ refers to the number of times the quantum circuit is executed to obtain a statistical sample of the output. Treating QAOA as a black-box optimizer, the evaluation relied solely on default parameter settings without manual adjustment, reflecting a realistic user experience and acknowledging the limitations of current quantum hardware and software. Further investigation examined the statistical basis of these results, employing rigorous statistical analysis to confirm the observed performance difference and rule out the possibility of random fluctuations. This included calculating confidence intervals and performing hypothesis testing to ensure the reliability of the findings.

Practical performance limitations of initial quantum optimisation implementations

Combinatorial optimisation problems underpin many real-world challenges, from logistics and finance to materials science and machine learning; finding the best solution from a vast number of possibilities is computationally expensive for classical computers, often scaling exponentially with the problem size. The difficulty arises from the sheer number of potential solutions that must be evaluated, making brute-force approaches impractical for even moderately sized problems. This work deliberately sidesteps optimising the Quantum Approximate Optimisation Algorithm (QAOA) to its theoretical limits, instead focusing on how it performs ‘out of the box’ for end-users, a crucial step towards assessing its real-world viability. Current implementations struggle to consistently outperform the established Goemans-Williamson algorithm, even with relatively modest computational effort, highlighting a key tension between theoretical potential and practical realisation. This discrepancy suggests that while QAOA possesses promising theoretical foundations, significant advancements are needed in hardware and algorithm design to unlock its full potential.

This evaluation establishes a new method for assessing quantum optimisation algorithms, moving beyond theoretical potential to reflect practical user experience. Researchers at gained insight into current limitations when tackling the Max-Cut problem, which involves dividing a network to maximise efficiency, a problem with applications in circuit design, network partitioning, and data clustering, by treating QAOA as a ‘black-box’ tool with default settings. The resulting framework allows for meaningful comparisons against the established classical Goemans-Williamson algorithm, revealing a performance gap under realistic conditions and highlighting areas for future development. Specifically, this framework can be used to assess the impact of different quantum hardware architectures, noise levels, and circuit designs on the performance of QAOA. This pragmatic evaluation framework, using standard graph structures and statistical analysis, offers a valuable benchmark for future quantum algorithm development and assessment, enabling more focused research efforts and accelerating the progress towards practical quantum optimisation. The ability to reliably benchmark algorithms in this manner is essential for guiding investment and prioritising research directions within the field of quantum computing, ensuring that resources are allocated effectively to address the most pressing challenges.

The research demonstrated that current implementations of the Quantum Approximate Optimisation Algorithm (QAOA) do not consistently outperform the classical Goemans-Williamson algorithm when applied to the Max-Cut problem. This matters because it provides a realistic assessment of QAOA’s performance for end-users who lack the expertise to fine-tune parameters. Researchers evaluated QAOA as a ‘black-box’ tool, using default settings and standard graph structures to establish a fair comparison with classical methods. The study’s framework allows for assessing the impact of hardware and circuit design on QAOA performance, and can be used to guide future development efforts.