Quantum annealing inspired algorithms for the NISQ Era

This paper proposes and analyzes quantum annealing-inspired algorithms, specifically Approximate Quantum Annealing (AQA) and Evolving Hamiltonian Quantum Optimization (EHQO), demonstrating through numerical simulations that they offer resource-efficient strategies and effective warm-start capabilities to enhance variational quantum optimization on NISQ devices.

The Gist

Imagine you are trying to find the lowest point in a vast, foggy mountain range. This is what computers do when they try to solve complex optimization problems: they are looking for the "best" solution among millions of possibilities.

In the world of quantum computing, there is a famous strategy called Quantum Annealing (QA). Think of this like a hiker who starts at the top of a mountain and slowly, very slowly, walks down. If they walk slowly enough, they are guaranteed to find the absolute lowest valley (the perfect solution). However, in today's "NISQ era" (Noisy Intermediate-Scale Quantum), our quantum computers are like hikers with shaky legs and limited energy. They can't walk the long, slow path without getting tired, making mistakes, or getting lost in the fog.

This paper explores three new ways to help these "shaky" quantum hikers find the bottom of the valley without needing a perfect, long journey.

1. The "Shortcut" Hiker: Approximate Quantum Annealing (AQA)

The first method, AQA, is like telling the hiker: "You don't have to take the slow, perfect path. Take bigger steps, but try to stay on the general trail."

• The Idea: In a perfect simulation, you take tiny steps. In AQA, the researchers let the computer take larger, "approximate" steps.
• The Discovery: They found a "Goldilocks zone." If the steps are too small, the computer takes too long and crashes. If the steps are too big, the hiker jumps off the trail entirely. But in the middle, the hiker can take bigger steps, finish faster, and still end up in the right valley.
• The Result: This allows the computer to solve problems with fewer resources (less "energy" and time) while still getting a good answer.

2. The "Smart Start" for the GPS: Quantum Approximate Optimization Algorithm (QAOA)

The second method, QAOA, is a popular algorithm that acts like a GPS trying to find the best route. However, a GPS is only as good as its starting point. If you tell it to start from a random spot in the forest, it might get stuck in a small dip (a local minimum) and think it's found the bottom, even though a deeper valley exists nearby.

• The Problem: Usually, QAOA starts with random guesses, which is like starting a hike in the middle of a random bush.
• The Fix: The researchers realized they could use the "shortcut" from AQA to give QAOA a warm start. Instead of starting randomly, they use the AQA "shortcut" to get the hiker close to the right area first.
• The Result: Once the hiker is already near the right valley, the GPS (QAOA) can easily fine-tune the path to find the absolute bottom. This works much better than starting from scratch.

3. The "Staircase" Guide: Evolving Hamiltonian Quantum Optimization (EHQO)

The third method, EHQO, is the most structured approach. Imagine the mountain is so steep that walking straight down is impossible. Instead, EHQO builds a staircase.

• How it works: Instead of trying to jump from the top of the mountain to the bottom in one go, the algorithm breaks the journey into many small steps.
  1. It finds the bottom of the first small hill.
  2. It uses that spot as the starting point to find the bottom of the next small hill.
  3. It repeats this, step-by-step, until it reaches the final destination.
• The Benefit: This prevents the hiker from getting lost. By solving a series of easy, small problems, the computer builds up a "map" that guides it to the final, difficult solution.
• The Catch: It takes more time to climb all the stairs, but it is much more reliable than trying to jump straight down.

The Big Picture: What They Found

The researchers tested these ideas on difficult puzzles (called 2-SAT problems) with different numbers of variables (like 8, 12, or up to 18).

• The "Shortcut" (AQA) works well but has limits; if the problem gets too big, the success rate drops quickly.
• The "Smart Start" (QAOA) is better than random guessing, but it still struggles as problems get huge.
• The "Staircase" (EHQO) was the winner. By taking the journey in small, guided steps, it kept the success rate higher even as the problems got bigger. It didn't just find a solution; it found a better solution more consistently than the other methods.

In summary: The paper suggests that while we can't yet build perfect, slow-motion quantum computers, we can use clever tricks—taking smart shortcuts, starting with a good map, and climbing a staircase of small problems—to make our current, imperfect quantum computers much better at solving hard puzzles.

Technical Summary

1. Problem Statement

Optimization problems are central to science and engineering but often become computationally intractable as they scale. Quantum Annealing (QA) is a promising approach based on the adiabatic theorem, where a system evolves from a simple initial Hamiltonian ($H_I$) to a problem Hamiltonian ($H_P$) to find the ground state (optimal solution).

However, the current Noisy Intermediate-Scale Quantum (NISQ) era presents significant challenges:

• Hardware Limitations: Current quantum processors suffer from noise, limited coherence times, and connectivity constraints.
• Circuit Depth: A faithful implementation of QA requires long evolution times and deep quantum circuits (via the Suzuki-Trotter decomposition), which are currently infeasible on NISQ devices due to error accumulation.
• Variational Challenges: Algorithms like the Quantum Approximate Optimization Algorithm (QAOA) are variational but suffer from "barren plateaus," vanishing gradients, and sensitivity to initial parameter choices, often leading to suboptimal local minima.

The paper aims to bridge this gap by developing QA-inspired hybrid algorithms that approximate the benefits of quantum annealing while reducing circuit depth and increasing robustness for NISQ hardware.

---

2. Methodology

The authors propose and analyze three distinct algorithms, all utilizing a discretized annealing ansatz but with different strategies for parameterization and optimization:

A. Approximate Quantum Annealing (AQA)

• Concept: AQA relaxes the strict requirement of a faithful QA trajectory. It treats the time step ($\tau$) and the number of layers ($p$) as tunable parameters rather than fixed physical constants.
• Mechanism: Instead of strictly following the adiabatic path with infinitesimal steps, AQA searches for a regime where a larger $\tau$ (fewer steps) combined with a specific $p$ still yields high success probabilities.
• Goal: To identify "effective" annealing parameters that reproduce QA-like behavior with significantly reduced circuit depth.

B. Quantum Approximate Optimization Algorithm (QAOA) with Warm Starts

• Concept: QAOA uses a layered circuit ansatz with variational parameters ($\beta_j, \gamma_j$) optimized classically.
• Innovation: The paper investigates using the optimal parameters found in AQA as a "warm start" (initialization) for QAOA.
• Hypothesis: Initializing QAOA with parameters derived from a QA-like trajectory confines the search space to a low-energy subspace, simplifying the optimization landscape compared to random initialization.

C. Evolving Hamiltonian Quantum Optimization (EHQO)

• Concept: A multistep variational scheme that explicitly guides the optimization through a sequence of intermediate Hamiltonians.
• Mechanism:
  1. Define $N_s$ intermediate Hamiltonians: $H(s_j) = (1-s_j)H_I + s_j H_P$.
  2. Perform variational optimization for $H(s_1)$ to find optimal parameters.
  3. Use the resulting parameters as the initialization for the optimization of $H(s_2)$, and so on, until $H_P$ is reached.
• Goal: To create a "smooth" pathway toward the solution, preventing the optimizer from getting stuck in local minima by leveraging the continuity of the Hamiltonian evolution.

---

3. Key Contributions

1. Identification of AQA Regimes: The authors demonstrate that AQA operates in distinct regimes. They identify an intermediate regime (where $\tau$ is neither too small nor too large) where the circuit deviates from strict QA dynamics but still achieves high success probabilities with shallower circuits, making it ideal for NISQ devices.
2. AQA as a Warm Start for QAOA: The study proves that parameters derived from AQA serve as a superior initialization for QAOA. This "informed" initialization significantly outperforms random initialization, particularly for larger problem sizes, by guiding the optimizer toward the low-energy subspace.
3. Development of EHQO: The introduction of EHQO provides a structured, step-by-step variational framework. It effectively mitigates the difficulty of direct optimization by breaking the problem into smaller, manageable steps, acting as a systematic search for optimal initial parameters.
4. Benchmarking on Hard Instances: The algorithms are rigorously tested on ensembles of hard 2-SAT instances (8 to 18 variables), a class of problems known to be challenging for classical solvers and variational quantum algorithms.

---

4. Results

• AQA Performance:
  • Parameter scans revealed that for $\tau < 0.4$, the circuit faithfully reproduces QA dynamics.
  • For $0.4 \leq \tau \leq 0.9$, the circuit implements an "effective" QA Hamiltonian, achieving high success probabilities with reduced depth (fewer layers).
  • For $\tau > 0.9$, the connection to QA breaks down, and performance degrades.
• QAOA with AQA Initialization:
  • When initialized with AQA parameters, QAOA achieved success probabilities close to 1 for 8-variable problems and significantly higher rates for 12-variable problems compared to random initialization.
  • This confirms that the AQA-derived state is confined to a low-energy subspace, simplifying the classical optimizer's task.
• EHQO Performance:
  • EHQO consistently outperformed both AQA and QAOA (with random starts) in terms of mean success probability.
  • Scaling Analysis: On 8–18 qubit 2-SAT instances:
    • AQA: Success probability decayed exponentially with a scaling exponent of -0.319.
    • QAOA (AQA-initialized): Showed similar exponential decay to AQA.
    • EHQO: Showed the best scaling with an exponent of -0.283, indicating a slower decay of success probability as problem size increases.
  • Bottleneck: The analysis identified the "anticrossing" region (near the critical point of the QA Hamiltonian) as a potential bottleneck where the ground state changes abruptly, causing temporary deviations in the EHQO trajectory. However, the stepwise approach allowed the algorithm to recover in subsequent steps.

---

5. Significance and Conclusion

The paper establishes that incorporating annealing-inspired structures into variational quantum algorithms is a viable strategy for the NISQ era.

• Practicality: By relaxing the strict adiabatic requirements (AQA) and using stepwise evolution (EHQO), these methods reduce circuit depth and noise sensitivity, making them more practical for current hardware.
• Optimization Landscape: The results highlight that the choice of initial parameters is critical. "Warm starts" derived from physical principles (like QA trajectories) can drastically improve the convergence of variational algorithms.
• Future Outlook: While the study is heuristic and limited to small problem sizes, it provides a roadmap for integrating quantum annealing concepts into hybrid quantum-classical workflows. The EHQO framework, in particular, offers a flexible, ansatz-independent approach that could be adapted to various hardware constraints and problem types.

In summary, the authors demonstrate that one does not need to wait for fault-tolerant quantum computers to leverage the power of quantum annealing; instead, by adapting its principles to variational algorithms, significant performance gains can be achieved on near-term devices.