Scaling QAOA: transferring optimal adiabatic schedules from small-scale to large-scale variational circuits

1. Problem Statement

The Quantum Approximate Optimization Algorithm (QAOA) is a leading variational algorithm for combinatorial optimization on near-term quantum devices. However, its scalability is hindered by two primary challenges:

• Parameter Optimization Complexity: QAOA requires optimizing $2p$ variational parameters (angles $\gamma$ and $\beta$) for a circuit with $p$ layers. As $p$ increases, the classical optimization landscape becomes increasingly difficult to navigate.
• Barren Plateaus: Deep circuits often suffer from "barren plateaus," where gradients vanish exponentially, making the training of circuit angles intractable.
• Adiabatic Limitations: While Adiabatic Quantum Computing (AQC) offers theoretical guarantees, finding the optimal annealing schedule requires knowledge of the instantaneous spectral gap, which is computationally intractable to calculate for large systems due to the exponential size of the Hamiltonian matrix.

Recent empirical studies suggest that optimal QAOA angles exhibit concentration and transferability across problem sizes. This paper aims to leverage this observation to create a scalable optimization strategy.

2. Methodology

The authors propose a Schedule-Learning Framework that transfers spectral-gap-informed adiabatic control strategies from small-scale instances to larger systems. The methodology consists of three main stages:

A. Learning Phase (Small-Scale)

• Target: Small instances (e.g., $n=10$ qubits) where exact diagonalization is feasible.
• Process: The authors compute the instantaneous spectral gap $g(s) = E_1(s) - E_0(s)$ across the annealing path $s \in [0, 1]$.
• Gap Profile: They analyze the distribution of gaps (mean and median) across 1,000 random QUBO instances. These profiles are fitted using Bézier curves to create a continuous, analytical representation of the gap function $g(s)$.

B. Schedule Construction

Instead of optimizing discrete angles, the method constructs a continuous annealing schedule $s(t)$ governed by the spectral gap. Based on adiabatic theory, the optimal evolution speed $ds/dt$ should be proportional to a power of the gap:
$$\frac{ds}{dt} = \kappa g^q(s)$$
Where:

• $g(s)$ is the learned gap profile.
• $\kappa$ is a proportionality constant (related to total runtime).
• $q$ is a power-law exponent (typically $1 \le q \le 2$).

C. Discretization to QAOA

The continuous schedule is mapped to the discrete QAOA circuit via Trotterization:

1. The path $s \in [0, 1]$ is discretized into $p$ steps.
2. The continuous integral of the Hamiltonian evolution is approximated as a product of exponentials.
3. Closed-Form Angles: By matching terms, the variational angles for layer $k$ are derived as:
   $$\gamma_k = \frac{s_k \delta s}{\kappa g^q(s_k)}, \quad \beta_k = \frac{(1-s_k) \delta s}{\kappa g^q(s_k)}$$
   where $s_k$ is the step position and $\delta s = 1/p$.

Key Innovation: This mapping reduces the classical optimization task from finding $2p$ independent parameters to optimizing only 2 global hyperparameters ($\kappa$ and $q$), regardless of the circuit depth $p$.

3. Key Contributions

• Parameter Compression: The framework reduces the dimensionality of the classical optimization problem from $O(p)$ to $O(1)$, effectively eliminating the need to variationally optimize every layer.
• Transferability: It demonstrates that spectral gap profiles learned from small systems ($n=10$) can be successfully extrapolated to larger systems ($n=20$) to generate high-quality schedules.
• Mitigation of Barren Plateaus: By drastically reducing the parameter space, the method reduces sensitivity to barren plateaus, offering a more stable training procedure for deep circuits.
• Generalizability: The approach is applicable to various combinatorial problems, including MaxCut and general QUBO formulations.

4. Experimental Results

The authors validated the method using numerical simulations on Qiskit for $n=20$ qubits across three problem classes:

1. 3-regular unweighted MaxCut.
2. 3-regular weighted MaxCut.
3. Random QUBO problems.

Findings:

• Approximation Ratios: The gap-informed heuristics (both mean-gap and median-gap variants) consistently achieved higher approximation ratios than standard "vanilla" QAOA, particularly for weighted MaxCut and random QUBO instances.
• Depth Scaling: As the number of layers $p$ increased, the performance of the proposed method improved monotonically and approached saturation. In contrast, standard QAOA showed high variance and limited improvement with depth.
• Hyperparameter Stability: The optimal values for $\kappa$ and $q$ stabilized as $p$ increased, whereas standard QAOA angles remained dispersed.
• Performance Gains:
  • Random QUBO: Showed the strongest advantage over standard QAOA.
  • Weighted MaxCut: Showed significant gains that increased with depth.
  • Unweighted MaxCut: Showed modest improvements, suggesting the method is most beneficial for more complex, weighted instances.

5. Significance

This work provides a scalable and parameter-efficient strategy for QAOA that bridges the gap between adiabatic quantum computing and variational algorithms.

• Practicality: It offers a solution to the "training bottleneck" of VQAs, making deep QAOA circuits feasible on near-term hardware by removing the need for complex classical optimizers.
• Theoretical Insight: It validates the hypothesis that structural information (spectral gaps) extracted from small systems serves as a principled inductive scheme for larger quantum systems.
• Future Direction: The method suggests that "learning" the physics of the problem (via gap profiles) is more effective than blindly optimizing circuit parameters, paving the way for more robust quantum optimization algorithms in the NISQ era.