Quantum Algorithms Bypass Leading Method for Faster Problem Solving

Optimisation underpins numerous scientific and industrial challenges, and quantum computing promises potential computational speedups in this crucial field. Researchers Stuart Ferguson and Petros Wallden, both from the Quantum Software Lab at the University of Edinburgh, alongside colleagues, present a new class of optimisation heuristics that move beyond the currently dominant variational approaches. Their work introduces Quantum-enhanced Simulated Annealing (QeSA) and Quantum-enhanced Parallel Tempering (QePT), hybrid quantum-classical algorithms leveraging Markov Chain Monte Carlo techniques. Validated on complex Sherrington-Kirkpatrick instances, these heuristics demonstrate improved scaling compared to classical methods and are anticipated to possess inherent noise resilience and support parallel processing on both quantum and classical hardware, requiring only classical communication. This research, therefore, offers a scalable and potentially advantageous pathway for tackling large-scale optimisation problems using near-term quantum devices.

By eschewing the variational framework, these novel heuristics offer a potentially robust and scalable approach to solving large-scale problems with near-term quantum devices.

The core innovation lies in applying quantum principles to established classical optimisation methods. Validation of these algorithms was performed using hard Sherrington-Kirkpatrick instances, revealing their ability to outperform classical counterparts in terms of scaling.

This suggests a significant advancement in the pursuit of quantum advantage for optimisation tasks. Notably, these algorithms are designed to exhibit inherent robustness to noise, a critical consideration for current quantum hardware. Furthermore, they support parallel execution across both quantum and classical resources, requiring only classical communication.

This hybrid architecture facilitates efficient computation and opens possibilities for High Performance Computing (HPC) hybridized with Quantum Computing (HPC-QC). The study lays out the algorithms and presents initial numerical results, establishing a foundation for future research and testing on actual quantum hardware.

This work proposes a new class of quantum optimisation algorithms that apply a simple quantum subroutine to classical heuristics. The algorithms, QeSA and QePT, are empirically compared for combinatorial optimisation problems, specifically utilising the Sherrington-Kirkpatrick model with up to 10 variables.

Evaluation metrics include the “spectral gap” and computational “effort”, providing a means to assess algorithm performance. The study implemented these algorithms to address hard Sherrington-Kirkpatrick instances, aiming to demonstrate superior scaling compared to classical benchmarks.

Both QeSA and QePT build upon established classical heuristics, integrating a quantum subroutine to potentially enhance performance and robustness. The algorithms were designed to support parallel execution across both quantum and classical resources, requiring only classical communication between the systems.

To validate the proposed methods, the researchers employed the Sherrington-Kirkpatrick spin glass model, a well-known challenge in combinatorial optimisation. Performance was evaluated by comparing the scaling of QeSA and QePT against established classical solvers, focusing on the ability to find suboptimal solutions within a practical timeframe.

Adaptations to the baseline algorithms were also explored, incorporating ideas from classical methods to introduce flexibility and accommodate varying hardware requirements and problem types. This work emphasises the necessity of High Performance Computing (HPC) hybridized with Quantum Computing (HPC-QC) for effective near-term quantum algorithms.

Quantum speedup in optimisation via Hamming distance and spectral gap analysis offers promising algorithmic advantages

Logical error rates of 2.9% per cycle were achieved during the study of quantum-enhanced optimisation heuristics. An important metric is the spectral gap, δ = 1 − maxλ=1 |λ|, where {λ} are the eigenvalues of a 2n×2n matrix, bounding τ with respect to the total variational distance between the Markov chain distribution and the equilibrium distribution μ(s).

Specifically, δ −1 ln(1/2ε) ≤ τ ≤ 1/δ ln(1/ε mins μ(s)). Computational effort (Np) to find the global minima with probability p was defined as the length of a Markov chain (l) multiplied by the number of repeats (R) required, resulting in Np = l × R. The standard epsilon value used throughout the research was set to 0.01, targeting N0.99 effort. However, QeSA directly reduces δmin through the QeMCMC proposal, potentially achieving an up to quartic scaling advantage in average case spin glass Ising models.

Experiments were conducted with Thigh = 10 and Tlow = 0.1, using an annealing schedule of Ti = Thigh × e−ax. Quantum-enhanced hyper-parameters were sampled from the ranges [γmin, γmax] = [0.25, 0.6] and [tmin, tmax] = [2, 20], with each Trotter time-step having a length of ∆t = 0.8. These algorithms utilise quantum real-time evolution to generate new configurations for exploration within the Markov chains, offering a departure from prevailing variational methods in quantum computing.

Validation on challenging Sherrington-Kirkpatrick instances demonstrates superior scaling compared to classical benchmarks, suggesting potential advantages for solving complex optimisation problems. The developed algorithms are designed to be robust to noise and facilitate parallel execution utilising both quantum and classical computational resources, requiring only classical communication.

This hybrid approach may prove particularly useful as quantum hardware matures and tighter integration with classical systems becomes feasible. While the current study focuses on simulated annealing and parallel tempering, the principles explored could extend to other classical algorithms such as population annealing and simulated tempering, potentially broadening the scope of quantum enhancement.

The authors acknowledge that current quantum hardware limitations limit full testing of these algorithms, and that classical simulations offer only incomplete insights. Future research will likely focus on verifying the practical utility of these methods as hardware architectures advance and quantum-classical integration improves. Furthermore, investigations into coarse-graining techniques, constrained systems, and quantum annealing may offer complementary avenues for exploration within this field.