Methods for non-variational heuristic quantum optimisation

This paper introduces and validates a novel class of non-variational, noise-resilient quantum optimization heuristics—Quantum-enhanced Simulated Annealing (QeSA) and Quantum-enhanced Parallel Tempering (QePT)—that utilize Markov Chain Monte Carlo techniques to achieve superior scaling over classical benchmarks on hard Sherrington-Kirkpatrick instances.

The Gist

Imagine you are trying to find the lowest point in a vast, foggy mountain range filled with deep valleys and hidden pits. This is what computer scientists call an optimization problem: finding the absolute best solution among billions of possibilities.

For decades, the main strategy to solve these problems on quantum computers has been "Variational" methods. Think of this like a student trying to learn a song by constantly asking a teacher for feedback, adjusting their pitch, and trying again. It works, but it's slow and requires a lot of back-and-forth.

This paper introduces a different approach. Instead of constantly asking for feedback, the authors propose a method that uses Quantum Computers as a "Super-Proposer." They call this a "non-variational" approach because it doesn't rely on that slow teacher-student loop. Instead, it uses a hybrid system where a classical computer runs the main race, but occasionally asks the quantum computer for a "magic jump" to a new location.

Here is a breakdown of their ideas using simple analogies:

1. The Problem: Getting Stuck in Local Pits

Imagine you are a hiker (the algorithm) trying to find the deepest valley (the best solution).

• Classical Simulated Annealing (SA): You start at the top of a mountain and slowly walk downhill. If you hit a small dip (a local minimum), you might get stuck there because you don't have the energy to climb out and find the real bottom.
• Parallel Tempering (PT): To fix this, you send out a whole team of hikers. Some walk on hot, sunny days (high temperature) where they can easily jump over small hills. Others walk on cold, icy days (low temperature) where they are very careful. Every so often, the hikers swap places. The "hot" hiker who just jumped over a hill swaps with the "cold" hiker who is stuck, helping the whole team escape traps.

2. The Innovation: The Quantum "Magic Jump"

The authors realized that while the "hot" hikers are good at jumping, they are still limited by how far they can physically leap. They proposed replacing the standard "local jump" (flipping one switch) with a Quantum Proposal.

Think of the quantum computer as a teleporter. Instead of taking small, cautious steps, the quantum computer looks at the map and suggests a "teleport" to a completely different part of the mountain range that is likely to be a good spot.

• How it works: The classical computer says, "Okay, I'm at this spot." The quantum computer runs a quick calculation (a "real-time evolution") and says, "I think you should teleport to this specific spot over there." The classical computer then checks if it's a good spot and decides whether to accept the jump.

3. The Two New Methods

The paper introduces two specific ways to use this quantum teleporter:

• QeSA (Quantum-enhanced Simulated Annealing): This is like the single hiker, but now they have a teleporter. As they slowly cool down (get more careful), the teleporter helps them escape deep pits that a normal hiker would get stuck in.
• QePT (Quantum-enhanced Parallel Tempering): This is the team of hikers. The authors found something very interesting: You don't need to give every hiker a teleporter.
  • If you give only the hikers at the bottom (the coldest, most careful ones) a teleporter, the whole team performs much better.
  • This is a huge deal because quantum computers are expensive and scarce. You can keep the "hot" hikers on regular classical computers and only use the expensive quantum teleporter for the few hikers who are most likely to get stuck.

4. What They Found (The Results)

The authors ran simulations (computer models) to test these ideas on very difficult, "glassy" problems (mountains with thousands of confusing pits).

• The Finding: The quantum-enhanced methods found the best solutions much faster than the classical methods.
• The Efficiency: They showed that you can get a massive speed boost even if you only use the quantum computer for a small part of the work (like the bottom few hikers in the team).

5. Why This Matters for the Future

The paper argues that this is a perfect match for the technology we have right now (or will have very soon).

• Noise Resilience: Quantum computers today are "noisy" (they make mistakes). The authors suggest this method is naturally tough against noise. Even if the quantum teleporter gets a bit fuzzy, it still suggests a random spot, which is better than nothing.
• Hybrid Power: It doesn't require a perfect, error-free quantum computer. It just needs a quantum computer to do one specific job (suggesting jumps) while a powerful classical supercomputer does the rest of the heavy lifting.

Summary

In short, the paper says: "Stop trying to make the whole quantum computer do the whole job. Instead, use a classical computer to run the race, and use a quantum computer just to give the runners a occasional, powerful 'super-jump' to help them escape traps. We proved that even a few of these super-jumps make the whole team win much faster."

Note: The paper explicitly states these are "proof of principle" results based on simulations. They have not yet run these on real quantum hardware, nor do they claim these methods will solve specific real-world industrial problems immediately. They are proposing a new way to think about how to use quantum computers for optimization.

Technical Summary

Technical Summary: Methods for Non-Variational Heuristic Quantum Optimisation

Problem Statement
Optimisation is central to scientific and industrial applications, yet classical exact methods often require exponential time for combinatorial problems, necessitating the use of heuristic solvers. While Variational Quantum Algorithms (VQAs) and Quantum Annealing (QA) dominate current research into noise-resilient quantum optimisation, they face challenges regarding convergence, circuit depth, and hardware requirements. Furthermore, many existing quantum approaches rely on fault-tolerant techniques or specific hardware architectures that are not yet available. There is a need for alternative, non-variational quantum heuristics that can leverage near-term quantum devices (NISQ) through hybrid quantum-classical frameworks, specifically addressing the "glassy" nature of cost functions (e.g., Sherrington-Kirkpatrick models) where classical Markov Chain Monte Carlo (MCMC) methods suffer from slow thermalisation due to energy barriers.

Methodology
The authors propose a novel class of quantum optimisation heuristics that replace the local proposal steps in classical MCMC-based algorithms with a quantum subroutine based on real-time evolution. This approach avoids the variational framework entirely.

1. Core Mechanism (QeMCMC): The foundation is Quantum-enhanced Markov Chain Monte Carlo (QeMCMC). Instead of a classical local proposal (e.g., flipping a single spin), the algorithm initializes a quantum computer in a computational basis state $|s\rangle$, applies a unitary evolution $U = e^{-iHt}$, and measures the result to obtain a new configuration $s'$.

   • The Hamiltonian $H$ is constructed as a sum of a driving term (related to adiabatic quantum computing, forcing spread among energy levels) and the problem-specific Ising Hamiltonian.
   • Hyperparameters $\gamma$ (mixing) and $t$ (evolution time) are sampled from specific ranges.
   • This design aims to generate proposals with small energy differences ($\Delta f$) and large Hamming distances ($\Delta H$), facilitating non-local moves that escape local minima more effectively than classical local proposals.

2. Proposed Algorithms:

   • Quantum-enhanced Simulated Annealing (QeSA): Extends classical Simulated Annealing (SA) by substituting the classical local proposal with the Quantum Proposal mechanism while following a logarithmic cooling schedule.
   • Quantum-enhanced Parallel Tempering (QePT): Extends Parallel Tempering (PT), which runs multiple Markov chains at different temperatures in parallel with periodic configuration swaps. In QePT, the authors propose a hybrid approach where only a subset of the chains (specifically those at lower temperatures where thermalisation is most difficult) are quantum-enhanced, while higher-temperature chains remain classical.

Key Contributions

• Algorithmic Proposal: The introduction of QeSA and QePT as non-variational, hybrid quantum-classical optimisation heuristics.
• Hybrid Architecture: A demonstration that full quantum enhancement is not strictly necessary; enhancing only the "bottleneck" low-temperature chains in a Parallel Tempering setup can yield significant advantages, making the approach more feasible for near-term HPC-QC (High Performance Computing - Quantum Computing) integration.
• Proof of Principle Numerics: The authors provide simulated numerical results on Sherrington-Kirkpatrick (SK) spin glass instances ($n \leq 10$) to validate the convergence properties of these algorithms against classical benchmarks.

Results

• Convergence Behavior: In simulations, classical SA frequently gets trapped in local minima, showing high variance in success probability. In contrast, QeSA demonstrates a more consistent ability to reach the global minimum, with success probability increasing steadily with the number of steps.
• Computational Effort: The authors define "computational effort" ($N_p$) as the product of the chain length and the number of repeats required to find the ground state with a specific probability.
  • For QeSA, optimising the chain length reveals that the quantum approach can achieve the target success probability with significantly lower total effort compared to classical SA for the tested problem sizes.
  • For QePT, the results indicate that quantum-enhancing only the lowest temperature chains (e.g., 2 out of 4 replicas) provides a tangible improvement over fully classical PT, approaching the performance of fully quantum-enhanced systems. This suggests a favorable resource-to-performance trade-off.
• Scaling: The authors observe a potential scaling advantage (hypothesised up to quartic) for average-case spin glass instances, though they explicitly state they do not quantify a definitive quantum speedup due to the limitations of classical simulation and the lack of real hardware testing.

Significance and Claims
The paper positions these methods as a scalable and potentially competitive route for solving large-scale optimisation problems using near-term quantum devices.

• Robustness: The algorithms are claimed to possess inherent robustness to noise. In the limit of fully depolarising noise, the quantum proposals revert to uniform sampling, which remains a valid MCMC step, unlike variational methods which may fail to converge.
• Parallelism: The approach supports parallel execution across quantum and classical resources, requiring only classical communication for replica exchanges, which aligns well with current HPC architectures.
• Modesty of Claims: The authors are explicit that these are heuristic methods without analytical guarantees of speedup for worst-case scenarios. They acknowledge that the performance of the quantum proposal is not well understood analytically and that the observed advantages are currently based on proof-of-principle numerics on simulated hardware. They state that the true potential and scaling of these methods can only be verified once tested on real quantum hardware with tighter quantum-classical integration. The work serves as a motivation for future research and experimental validation rather than a definitive solution to quantum advantage.