Source-linked AI summary
Training the Quantum Approximate Optimization Algorithm without access to a Quantum Processing Unit
Michael Streif, Martin Leib
TL;DR
QAOA parameter training requires repeated QPU calls, a bottleneck for variational algorithms on NISQ devices. This paper infers parameters without QPU updates and reports comparable-or-better QAOA performance, as well as improved quantum-annealing schedules.
Problem
QAOA parameter updates require repeated QPU calls to estimate output-state energy, while efficient training or bypassing training remains important to whether variational algorithms can achieve quantum advantage.
Source: §1 · p. 2Method
The method infers QAOA parameters without using the QPU for parameter updates, reserving it for sampling from the output state.
Source: §1 · p. 2Results
Across the studied instances, inferred-parameter QAOA was comparable to or better than trained vanilla QAOA, and its annealing schedule performed better than a trivial schedule.
Source: §6 · pp. 16–17Takeaways & Limitations
Resilience to a reasonable amount of control-parameter disorder supports the method’s suitability for NISQ devices.
Source: §6 · p. 17The study focused on randomly generated instances, and performance on the hardest instances of a problem class remains an open question.
Source: §6 · p. 17
Abstract
from arXiv · showhide
In this paper, we eliminate the classical outer learning loop of the Quantum Approximate Optimization Algorithm (QAOA) and present a strategy to find good parameters for QAOA based on topological arguments of the problem graph and tensor network techniques. Starting from the observation of the concentration of control parameters of QAOA, we find a way to classically infer parameters which scales polynomially in the number of qubits and exponentially with the depth of the circuit. Using this strategy, the quantum processing unit (QPU) is only needed to infer the final state of QAOA. This method paves the way for a variation-free version of QAOA and makes QAOA more practical for applications on NISQ devices. Moreover, we show the applicability of our method beyond the scope of QAOA, in improving schedules for quantum annealing.
1. Introduction
QAOA offers a variational approach to combinatorial optimization, but its parameter-training loop requires repeated QPU calls. The paper proposes inferring parameters without QPU updates and reports performance comparable to or better than trained vanilla QAOA.
1. Introduction
- NISQ devices have up to tens of qubits, motivating algorithms that use them without relying on error correction.Variational quantum algorithms use parameterized circuits updated in classical learning loops and are viewed as promising candidates.Source: §1 · p. 2
- QAOA targets combinatorial optimization and has been applied to problems including Max-Cut and Max-3-Lin-2, but its variational nature leaves performance and scaling less understood.Prior work also showed that classical hardware cannot efficiently sample its output state and that QAOA can achieve a Grover-type speed-up.Source: §1 · p. 2
- Finding QAOA parameters requires repeated QPU calls to estimate output-state energy, making training a major bottleneck.The introduction notes that whether variational algorithms can deliver quantum advantage depends on finding efficient ways to train them or bypass training.Source: §1 · p. 2
- The proposed parameter-inference method avoids QPU calls for updates and performs comparably to or better than trained vanilla QAOA.The QPU is used only to sample from QAOA’s output state.Source: §1 · p. 2
2. Theory
The theory uses concentration of optimal QAOA parameters across related graph instances to motivate classical parameter inference, then evaluates the needed correlations through reverse causal cones and tensor networks.
2.1. The Quantum Approximate Optimization Algorithm
- QAOA maps a combinatorial problem to a spin-glass Hamiltonian, then applies p alternating problem and mixing unitaries to minimize expected problem energy.The circuit starts in an equal superposition; its parameters are β_i and γ_i.Source: §2.1 · pp. 3–4
2.2. Concentration of parameters
- Optimal parameters concentrate around values tied to qubit interaction degree, and their distributions narrow as system size increases.This motivates reusing average optimal parameters across instances and finding them without QPU calls.Source: §2.2 · pp. 4–5, Figure 1 · p. 5
- A reverse causal cone identifies the gates influencing a correlation between interacting qubits, allowing its evaluation on a subgraph rather than the full problem graph.For sufficiently large random fixed-degree graphs, the most likely relevant subgraph is a tree, enabling an infinite-size-instance approximation.Source: §2.2 · pp. 5–7
2.3. Tree-QAOA
- Tree-QAOA infers parameters without QPU calls, reserving the QPU for preparing and sampling from the final state.Its tensor-network calculation evaluates the energy for an infinite-size instance.Source: §2.1 · p. 4, §2.3 · p. 7
- For the tree correlation functions, tensor-network contraction scales exponentially with QAOA block count, not qubit count; this is an upper bound.The generated subgraph has treewidth 1, and the paper uses a heuristic contraction ordering that does not exhaust the bound.Source: §2.3 · pp. 9–10
3. Numerical results
Tree-QAOA performs comparably to or better than instance-trained QAOA in the reported benchmark settings, including spin glasses whose graph degrees do not match its assumptions. The section evaluates it on 3-regular Max-Cut and 2D spin-glass instances.
3.2. Spin glasses on 2D lattices
- The 2D-grid tests benchmark tree-QAOA where graph degrees do not perfectly satisfy its assumptions; the studied grids contain 9 and 16 spins.The authors note that the average degree approaches 4 for large grids, but only 1 vertex in the 3 × 3 grid and 4 in the 4 × 4 grid have degree 4.Source: §3 · p. 10, §3.2 · p. 13
3. Numerical results
- The benchmarks compare tree-QAOA with per-instance BFGS-QAOA and Adam-QAOA using residual energy, which measures how close output-state energy is to ground-state energy.The authors report that other metrics, including overlap with ground states, yield qualitatively similar results; residual energy suits cases where any good solution is useful.Source: §3 · p. 11
3.1. Max-Cut on 3-regular graphs
- For 12-spin 3-regular Max-Cut instances, tree-QAOA is comparable to or better than both competitors; it is superior for p > 5, while BFGS-QAOA performs poorly overall.Adam-QAOA is slightly better for a small number of QAOA blocks.Source: Figure 4 · p. 12, §3.1 · p. 13
- For 3-regular graphs, tree-QAOA derives parameters by simulating the degree-3 tree subgraph; at p = 8, its circuit contains 1022 qubits.The method uses tensor-network contraction and L-BFGS-B parameter updates; the authors note that improved contraction ordering or optimization could speed calculation.Source: §3.1 · p. 12
3.2. Spin glasses on 2D lattices
- On 3 × 3 and 4 × 4 spin-glass grids, tree-QAOA performs worse than Adam-QAOA on smaller instances but comparably on larger ones.Even on the smaller grid, where the degree-4 assumption is inaccurate, its residual energy is much better than random guessing and decreases monotonically.Source: Figure 5 · p. 13, §3.2 · p. 14
4. Performance under the influence of disorder
The paper tests tree-QAOA under analog control errors modeled as random over- or under-rotations. Even at 20% disorder, its result remains much better than random guessing.
4. Performance under the influence of disorder
- The study reuses 3-regular Max-Cut instances with N = 16 qubits to test the effect of analog control errors.The supplied passage identifies the instances but does not specify their number.Source: §4 · p. 14
- Analog control errors are modeled as random over- or under-rotations of parameterized gates, with disorder set by the standard deviation σ.The circuit is evaluated against the undisturbed Max-Cut Hamiltonian, matching the stated experimental situation where the disturbed Hamiltonian is unknown.Source: §4 · p. 15
- At 20% of the interaction-strength magnitude, tree-QAOA still performs much better than random guessing.The result is reported for residual energy under the modeled control disorder.Source: §4 · p. 15
5. Translating tree-QAOA parameters into a quantum annealing schedule
The paper tests whether tree-QAOA parameters can provide useful quantum annealing schedules. For 10-spin Max-Cut instances on 3-regular graphs, the induced schedule performs significantly better than a linear schedule.
5. Translating tree-QAOA parameters into a quantum annealing schedule
- The comparison asks whether good QAOA parameters can also produce good annealing schedules.Quantum annealing steadily transforms the mixing Hamiltonian into the problem Hamiltonian; avoiding transitions may require slowing near avoided crossings, whose locations require knowledge of the time-dependent spectrum.Source: §5 · pp. 15–16
- The tree-QAOA-induced schedule performs significantly better than a linear schedule on 100 randomly drawn 10-spin Max-Cut instances.Ground-state population is averaged over the instances as a function of total annealing time T; both schedules use energy scales normalized to [0, 1].Source: §5 · p. 16
- A degree-6 polynomial fitted to the absolute tree-QAOA parameters is used to construct the annealing schedule.The schedule is compared with a trivial ramp whose mixing and problem Hamiltonian functions are linear.Source: §5 · p. 16
6. Conclusion and outlook
The paper introduces a tensor-network strategy for inferring QAOA parameters without repetitive QPU calls for parameter updates. Across the studied instances, its results are comparable to or better than trained vanilla QAOA, while its performance on the hardest instances remains open.
6. Conclusion and outlook
- Across problem classes and instances up to N = 20 qubits, tree-QAOA results are comparable to or better than vanilla QAOA trained with classical outer loops.The method simulates parameter inference efficiently on classical hardware using Tensor Networks, without repetitive QPU calls for parameter updates.Source: §6 · p. 16
- The method is reported as resilient to a reasonable amount of control-parameter disorder, and its annealing schedule performs better than a trivial schedule.The conclusion also says the expected larger-instance advantage remains an open question requiring experimental proof.Source: §6 · p. 17
- The evaluation focuses on randomly generated instances; performance on the hardest instances of a problem class remains open.For larger p, the paper suggests approximate tensor-network contraction or more sophisticated contraction orderings as future directions.Source: §6 · p. 17