Quantum Computers Demonstrably Outperform Classical Methods in Optimisation Tasks

A degeneracy-weighted shell distribution governed by a single effective parameter, β, quantifies concentration toward near-optimal independent sets. Junwoo Jung and Jaewook Ahn at the KAIST, extracted the genuine concentration effect in quantum data by applying identical postprocessing to both experimental bitstrings and randomly generated bitstrings with matched excitation density, constructing an excitation-matched random baseline.

Experiments on programmable Rydberg-atom arrays with system sizes up to 125 sites show quantum annealing consistently exceeds the random baseline, demonstrating enhanced concentration toward low-energy solution structure beyond what can be attributed solely to excitation density.

Quantum annealing achieves exponential gains in solution sampling efficiency for combinatorial optimisation

Quantum annealing represents a promising paradigm for tackling complex combinatorial optimisation problems, offering the potential to surpass the limitations of classical algorithms. These problems, prevalent in fields such as logistics, finance, and materials science often involve searching for the best solution from a vast number of possibilities. The efficiency of an optimisation algorithm is typically measured by the number of computational attempts required to find a solution within a specified level of accuracy.

This research demonstrates that quantum annealing reduces the number of computational attempts needed to achieve a target approximation ratio by the same exponential level as the growth in attempts with system size for near-exact targets, a feat previously unattainable with classical methods. This signifies a substantial reduction in computational effort; for systems up to 125 sites, classical postprocessing alone can reach relaxed targets in order-unity attempts, indicating a significant speedup.

The team quantified this performance using a new metric, STS(r), which measures attempts to approximate a solution, and found consistent outperformance of random baselines, enhancing concentration toward low-energy structures. The STS(r) metric, where ‘r’ denotes the approximation ratio, provides a standardised way to compare the performance of quantum and classical approaches, accounting for the trade-off between solution accuracy and computational cost.

Outputs were modelled using a shell distribution governed by β, a parameter indicating concentration toward near-optimal independent sets. This shell distribution characterises the probability of finding solutions within a certain energy range, with a lower β value indicating a stronger concentration around the optimal solution. To isolate genuine quantum effects, an excitation-matched random baseline was generated by applying identical postprocessing to randomly generated bitstrings with equivalent excitation density, ensuring observed improvements weren’t due to fewer excited atoms per attempt.

In Rydberg-atom quantum annealers, ‘excitation density’ refers to the number of atoms in a highly energetic state, which can introduce errors and affect the quality of the solution. The Rydberg-atom arrays function by encoding the optimisation problem into the interactions between individual atoms, leveraging the principles of quantum mechanics to explore the solution space. While the number of attempts required increased exponentially with system size for near-exact targets, this increase was offset by a corresponding exponential reduction achieved through quantum annealing.

This work highlights the potential for neutral-atom quantum computers to tackle complex optimisation challenges with improved efficiency, particularly when dealing with large-scale problems where classical algorithms struggle. The ability to achieve exponential speedups, even for near-optimal solutions, opens up new possibilities for applying quantum computing to real-world applications.

Quantifying computational effort reveals performance scaling in quantum optimisation

Progress is being made toward using the power of quantum computers for practical optimisation problems, but a fundamental question remains regarding their ability to consistently find good solutions. Establishing a clear understanding of how quantum algorithms scale with problem size is crucial for determining their potential impact. The team’s work establishes a new way to measure how many attempts, or ‘shots’, a quantum computer needs to approximate an answer, revealing distinct behaviours depending on how close to the ideal solution is required.

This is particularly important because many real-world optimisation problems do not require a perfectly optimal solution, but a ‘good enough’ solution that meets certain criteria. Achieving a true quantum advantage, outperforming the best classical algorithms, remains elusive, particularly when seeking highly accurate results. The difficulty lies in the inherent complexity of quantum systems and the challenges of maintaining quantum coherence, which is essential for performing computations.

Despite not yet demonstrating outright superiority over classical methods for highly precise solutions, this research provides an important metric for evaluating quantum optimisation performance. The STS(r) metric allows for a more nuanced comparison of quantum and classical algorithms, taking into account the trade-off between solution accuracy and computational cost. This insight is valuable because it pinpoints scenarios where current neutral-atom quantum computers excel, specifically for problems where near-optimal, rather than perfect, answers are sufficient. Identifying these niche applications is crucial for driving the development and adoption of quantum computing technology. The team’s work establishes a method for quantifying the performance of quantum optimisation, moving beyond simply observing improvements to identifying specific conditions where neutral-atom systems can offer benefits. STS(r), which measures the number of computational attempts needed to reach a given solution accuracy, was introduced, and analysis of experiments using programmable Rydberg-atom arrays, encoding problems as interactions between atoms, demonstrated enhanced concentration toward low-energy structures compared to random approaches, and provides insight into the scaling of performance with system size. The use of Rydberg-atom arrays allows for precise control over the interactions between atoms, enabling the implementation of complex quantum algorithms. Further research will focus on exploring the limits of this approach and developing new techniques to improve the performance of quantum optimisation algorithms.

The research demonstrated that quantum annealing on neutral-atom arrays consistently outperformed random approaches in finding low-energy solution structures for certain optimisation problems. This means the quantum computer required fewer computational attempts, as quantified by the newly developed STS(r) metric, to reach a given level of accuracy compared to a classical random baseline. Experiments with systems up to 125 sites revealed this enhancement was particularly noticeable when seeking near-optimal solutions rather than perfectly accurate ones. The authors intend to continue exploring the boundaries of this method and refine quantum optimisation techniques.