Quantum annealing inspired algorithms for the NISQ Era

Authors per arXiv listing · arXiv:2604.25573 · new submission, quant-ph · score 8/10

Abstract

We study algorithms inspired by quantum annealing that are suited for the NISQ era. First, we analyze approximate quantum annealing (AQA), which employs a discretized annealing ansatz in which the time step and the number of layers are allowed to deviate from a faithful implementation of quantum annealing. Parameter scans identify regimes that reproduce annealing-like behavior with reduced resources, making them more suitable for NISQ devices. The resulting parameters can then be used as an effective warm start for the quantum approximate optimization algorithm (QAOA), improving its performance compared to random initializations. We also introduce evolving Hamiltonian quantum optimization (EHQO), a multistep variational scheme that guides the optimization process through intermediate Hamiltonians derived from the standard annealing Hamiltonian. Numerical simulations on sets of hard 2-SAT instances suggest that quantum annealing-inspired algorithms provide practical strategies for enhancing variational quantum optimization.

Executive summary

Three quantum-annealing-inspired algorithms for NISQ optimisation: (1) Approximate Quantum Annealing (AQA) — a discretised annealing ansatz where (tau, p) are tuned away from a faithful Trotter approximation of QA; (2) AQA-warm-started QAOA — using AQA-optimal parameters as the QAOA initialisation; (3) Evolving Hamiltonian Quantum Optimisation (EHQO) — a multi-step variational scheme that traverses N_s intermediate Hamiltonians H(s_j), each warm-started from the previous step's optimum. Tested on hard 2-SAT instances at 8, 12, and 8-18 qubits. The paper places AQA in a parameter regime (small tau, moderate p) that retains annealing-like dynamics while being implementable as a shallow circuit; EHQO formalises the layerwise/step-wise warm-starting Y3 used.

Main contribution

The framing innovation is to treat quantum annealing not as the gold standard to faithfully reproduce, but as a parameter source. AQA's parameter scans (tau, p) identify regimes that reproduce annealing-like behaviour with much smaller p than a Trotter approximation would require — practical for NISQ. The transferred parameters then serve as a structured warm-start for QAOA, beating random initialisation. EHQO generalises this further: rather than warm-starting QAOA once from AQA, EHQO performs N_s sequential variational optimisations on a chain of intermediate Hamiltonians H(s_j), each starting from the previous step's optimum. This is the layerwise / iterative / warm-start template at the cost-Hamiltonian level rather than the parameter level.

Key theorems / results / algorithms

AQA ansatz (Eq. 7 in Sec. III): a Trotterised annealing schedule |Psi(t)> approx prod_{j=1}^p exp(-i tau A(j/p) H_I) exp(-i tau B(j/p) H_P) |+>^{\otimes N}, with tau and p as free hyperparameters rather than dictated by adiabatic theorem.
Empirical regime identification: parameter scans (Fig. aqa-1) show that for tau in [0.05, 0.9] and moderate p, AQA reproduces annealing-like ground-state success probability with substantially fewer layers than a faithful Trotter; for tau > 0.9 the dynamics degrade to random Hilbert-space jumps.
AQA-warm-start QAOA (Sec. IV): initialise QAOA's (gamma, beta) angles to the optimal (tau A(j/p), tau B(j/p)) from AQA, then refine variationally; success probability dominates random-initialisation QAOA at matched layer count.
EHQO algorithm (Sec. V): define N_s intermediate Hamiltonians H(s_j) = (1-s_j) H_I + s_j H_P with s_j = j/N_s; at step j, optimise theta_j on cost C_j = initialising from theta_{j-1}^f. Continues until j = N_s. Cost is N_s × (single-step variational cost) but each step's optimisation is much easier because consecutive Hamiltonians are close.
Scaling result (Fig. aqa-qaoa-scaling): on 100 instances of 8-18 qubit 2-SAT problems, EHQO's mean success probability scales more favourably with system size than AQA alone.

Detailed walkthrough

The introduction (Sec. I) walks through the gap between quantum annealing as an idealised continuous evolution and the discretised, noisy implementations that fit on NISQ devices. The authors' thesis: rather than try to faithfully approximate the QA trajectory (which requires p large enough that Trotter error is small), accept a discretisation that is annealing-like at NISQ-feasible depth and use it as either a standalone solver (AQA) or a warm-start source for QAOA. EHQO then closes the loop: traverse the QA trajectory step-by-step in cost-Hamiltonian space, with a variational solve at each step.

AQA (Sec. II) is the simplest of the three. The ansatz is the first-order Trotter discretisation of the linear annealing schedule with (tau, p) treated as free parameters. The success probability scan (Fig. aqa-1) is the key diagnostic: the contour plot of success probability over (tau, p) with red constant-(tau×p) lines identifies an "AQA sweet spot" at small tau and moderate p where annealing-like dynamics are preserved with much smaller circuit depth than a faithful Trotterisation would need. The instantaneous overlap analysis (Fig. aqa_instoverlap) confirms that within this regime the AQA state tracks the instantaneous QA ground state.

The AQA-warm-started QAOA (Sec. III) sets QAOA's (gamma_j, beta_j) to (tau A(j/p), tau B(j/p)) from the AQA-optimal (tau, p), then runs standard variational optimisation. The success-probability scan (Fig. aqa-qaoa-1) shows this warm-start dominates random-initialisation QAOA at matched layer count over a wide region of (tau, p). The intuition is that AQA-optimal parameters land in a basin already close to the QAOA optimum, so the variational refinement only needs to fine-tune.

EHQO (Sec. IV) is the more substantive algorithm. The construction is: define a chain of N_s−1 intermediate Hamiltonians H(s_j) = (1−s_j) H_I + s_j H_P interpolating between the easy initial Hamiltonian and the problem Hamiltonian. At step j, the algorithm runs a variational optimisation (e.g., QAOA-ansatz) targeting H(s_j), initialising the parameters from the optimum of the previous step's optimisation against H(s_{j−1}). The intuition (similar to adiabatic state preparation): consecutive H(s_j), H(s_{j+1}) are close, so the previous step's optimum is a good warm-start for the next, and the algorithm slides along the QA trajectory in optimisation space rather than time-evolution space. The cost is N_s × (single-step variational cost), but each step is much easier than directly variationally optimising H_P.

The numerical experiments (Sec. VI) use 100 hard 2-SAT instances at 8 and 12 qubits and 8-18 qubits for scaling. EHQO with QAOA ansatz at p=25 and N_s = 10 or 20 (Fig. ehqo_instance) traces the expectation value of H(s_j) at each step j, showing smooth descent. The overlap diagrams (Fig. 8-ehqo-overlaps) show that at each step j, the warm-started initial state already has high overlap with the ground state of H(s_j) — the warm-start is doing real work.

The quartiles plot (Fig. quartiles) compares success-probability quartiles across EHQO variants (BFGS vs. Nelder-Mead optimiser, with/without warm-start). The scaling plot (Fig. aqa-qaoa-scaling) is the headline: across 8-18 qubit 2-SAT instances, EHQO's mean success probability scales more gracefully than AQA alone, with the advantage growing with problem size.

The conclusion situates these methods firmly in Y1's iterative warm-start lineage and Y3's layerwise QAOA lineage. EHQO is essentially a cost-Hamiltonian-traversal version of layerwise optimisation; AQA-warm-started QAOA is the parameter-transfer version of warm-start. Both should be in any serious QAOA-on-NISQ practitioner's toolkit.

Figures

Figure 1. Success probability of AQA with first-order Trotter approximation: variation with time step tau and number of steps p. Red lines mark constant total annealing time tau×p.

Figure 2. Success probability of QAOA initialised with AQA parameters: tau in [0.05, 1.5], p in [10, 1000], capped at 8000 function evaluations.

Figure 3. EHQO trajectory on an 8-qubit 2-SAT instance: expectation value of H(s_j) under the final state at each step j (QAOA ansatz with p=25, N_s=10 and 20).

Figure 4. EHQO trajectory on a 12-qubit 2-SAT instance, same setup as Figure 3.

Figure 5a. Overlap analysis for 8-qubit EHQO: initial wavefunction (using warm-start from previous step) overlap with ground / first-excited state of intermediate H(s_j); also shown is final success probability after optimisation at each point.

Figure 5b. Same overlap analysis for the 12-qubit instance.

Figure 6a. Success-probability quartiles for different EHQO variants on 8-qubit 2-SAT (BFGS vs. Nelder-Mead optimisers).

Figure 6b. Same quartile plot for 12-qubit 2-SAT.

Citations to Yuan's papers

No direct citation to any of Y1–Y6 found in bibliography.

Overlap with Y1–Y6

Y1. Direct method overlap. Y1's iterative quantum warm-starting prepares a high-quality QAOA seed via measurement of a previous QAOA layer. AQA-warm-started QAOA prepares the seed via a structured (tau, p) sweep on the annealing ansatz. EHQO further generalises by warm-starting through a chain of intermediate Hamiltonians. All three are members of the same family — improve QAOA by giving it a better starting point, derived from problem structure.

Y3. Direct method overlap. Y3 found that layerwise QAOA optimisation gave the most robust schedule for the DGMVP portfolio. EHQO is essentially a "Hamiltonian-wise" generalisation: instead of adding QAOA layers one by one, it traverses cost Hamiltonians H(s_j) one by one. The warm-starting principle is identical; the geometry is different (parameter space vs. Hamiltonian space). Worth comparing on portfolio benchmarks.

Y2. Light method overlap. Y2's portfolio QAOA also relies on iterative refinement (CVaR + iterative). The connection to EHQO is via the broader template of "build a sequence of easier problems, solve each warm-starting from the previous".

Recommended action for Yuan

Adapt EHQO for the DGMVP portfolio (Y3). Replace the linear interpolation H(s) = (1−s) H_I + s H_P with a portfolio-specific schedule (e.g., gradually adding asset correlation terms) and compare with Y3's layerwise schedule. Could be the next paper in the Y3 line.
Cite in next QAOA-warm-start draft. EHQO is a clean concrete example of the "warm-start via problem-structure interpolation" idea — pairs nicely with Y1 in a related-work section.
Read deeper, especially Sec. III. The (tau, p) sweep methodology is a useful template for any future Y3-style noise-regime analysis: identify an "AQA sweet spot" before reporting QAOA results.