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.

Validating Scaling Through Spin Glass Benchmarks

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.

👉 More information
🗞 Methods for non-variational heuristic quantum optimisation
🧠 ArXiv: https://arxiv.org/abs/2602.01353

More like this