PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning angles for quantum approximate optimization

Johannes Jakubik, Isabelle Wittmann, Zaheed Gaffoor, Gciniwe Simphiwe Baloyi, Craig Mahlasi, Etienne Vos, Thomas Brunschwiler, Daniel J. Egger

arXiv:2610.23296v1quant-phcs.LG

TL;DR

Finding high-quality QAOA angles requires expensive, instance-specific optimization, and prior direct-prediction evidence has often been limited to small graphs. This paper trains graph-based models to predict angles in one forward pass, with quality close to the solver and inference several orders of magnitude faster. It also reports generalization to unseen graph topologies, while identifying a trade-off between fast regression objectives and accurate energy-based objectives.

  • Problem

    Finding good QAOA angles is an expensive, non-convex instance-specific optimization task, and whether models can directly predict high-quality angles across sizes and topologies without further optimization remained open.

    Source: §I · p. 1

  • Method

    The authors train graph-based models to map weighted MaxCut instances to QAOA angles, rescaling γ per instance to support learning across graph families.

    Source: §I · p. 1, §VI · p. 10

  • Results

    Learned angles recover a large fraction of the solver’s approximation ratio while reducing angle-generation time by several orders of magnitude, and models generalize to unseen topologies.

    Source: §VI · pp. 10–11

  • Takeaways & Limitations

    Graph models sensitive to topology most consistently achieve near-solver performance across multi-topology tests, while plain transformers generalize to larger and unseen graphs more reliably than message-passing networks.

    Source: §VI · pp. 10–11

    MSE-style regression objectives are fast but can impose non-negligible inaccuracies, whereas energy-based objectives are more accurate but substantially slow training, particularly at greater QAOA depth.

    Source: E. Limitations of MSE-style proxy… · p. 9

Abstract

from arXiv · show

The Quantum Approximate Optimization Algorithm (QAOA) and its variants are leading algorithms to help solve challenging combinatorial optimization problems. QAOA maps these problems to Ising Hamiltonians such that their ground state is the desired solution. Candidate solutions are then drawn from a variational quantum circuit. The performance of QAOA hinges on a set of variational angles. However, finding good angles is an instance-specific and computationally expensive non-convex classical optimization task. Here, we learn the mapping from the problem instance to high-quality QAOA angles. Our learned models replace the per-instance optimization, that we call the solver, with a single forward pass that is several orders of magnitude faster than the solver with a near identical quality. Our models further generalize to unseen topologies such as Barab\'asi-Albert and 2D grid graphs. Experiments on quantum hardware confirm that QAOA samples with angles produced by our open-source models are indistinguishable from solver angles. Crucially, models sensitive to the topology of the problem instance increase the quality of the QAOA angles. Our work amortizes a major bottleneck in QAOA by an up-front data generation and training cost. Importantly, this cost can be amortized over time in settings where many similar problems are optimized on a regular basis, as is often the case in applications for industry.

I. INTRODUCTION

QAOA performance depends on finding angles through expensive, non-convex optimization, while prior direct predictors have often been limited to small, classically simulable graphs. This work directly predicts fixed-depth QAOA angles from graphs without instance-specific refinement, evaluating models across graph families and unseen sizes and topologies.

I. INTRODUCTION

  • Prior direct angle predictors have largely been evaluated on classically simulable graphs with at most 20 nodes and up to p = 4.Other approaches reach larger sizes or depths through transfer, extrapolation, or continued instance-specific optimization.Source: §I · p. 1, §II · p. 2
  • Across depths p = 1–5, learned angles achieve approximation ratios close to COBYLA while reducing angle-generation time by several orders of magnitude.A single model also generalizes to graphs up to 200 nodes and unseen Barabási–Albert and 2D-grid topologies without per-instance retraining or fine-tuning.Source: §I · p. 1

II. RELATED WORK

  • The paper frames angle selection as direct prediction from problem graphs, replacing per-instance classical optimization with a single forward pass and no instance-specific refinement.Models are trained across graph families and evaluated at depths up to p = 5 on graphs up to 200 nodes.Source: §I · p. 1, §II · p. 2
  • Related methods include angle transfer, which reuses angles from similar donor instances, and depth extrapolation, which uses lower-depth solutions to initialize optimization at greater depth.Learned optimization methods instead guide iterative searches rather than directly outputting angles.Source: §II · p. 2
  • Evaluation settings differ across existing methods, making direct comparisons challenging; most rely on classical simulation, with some hardware exceptions.The paper benchmarks its predictions against fixed-angle baselines and validates heavy-hex angles on quantum hardware.Source: §II · p. 2

III. QAOA AND FIXED ANGLES

QAOA uses alternating cost and mixer operations, with variational angles chosen to drive its state toward a cost-Hamiltonian ground state. The section defines approximation-ratio evaluation and contrasts instance-specific angle optimization with fixed-angle methods based on local tree structure.

III. QAOA AND FIXED ANGLES

  • QAOA alternates cost-Hamiltonian and mixer operations for p layers, using 2p variational angles to steer the state toward the cost-Hamiltonian ground state.For weighted MaxCut, the problem is encoded in a Hamiltonian by mapping binary decisions to spin variables and then Pauli-Z operators.Source: §III · pp. 2–3
  • The approximation ratio measures the sampled average cut value relative to the minimum and maximum cut values, and lies between 0 and 1.The extrema are obtained with CPLEX, while the average is over candidate solutions sampled from the QAOA state.Source: §III · p. 3
  • The solver uses a grid scan, COBYLA refinement, and depth-by-depth interpolation, achieving high approximation ratios but requiring long runtime.At depths above p = 1, Pauli propagation provides approximate energy evaluations.Source: §III · p. 3
  • For random regular graphs with no loops shorter than 2p + 1, depth-p QAOA sees identical tree neighborhoods, enabling tree-derived fixed angles that lower-bound their approximation ratio.A database provides constant-time angle lookup; non-regular graphs use the nearest average-degree regular entry, while heavy-hex graphs use topology-specific angles up to p = 3.Source: §III · pp. 3–4, Figure 2 · p. 4

IV. DEEP LEARNING FOR QAOA

The paper formulates QAOA angle selection as supervised graph-level regression, motivated by the heterogeneous local structures and weights of general graphs. It trains across graph families and normalizes the cost-dependent γ targets so a single model can learn across them.

IV. DEEP LEARNING FOR QAOA

  • A supervised graph-level model maps a weighted graph to its 2p QAOA angles, aiming to generalize across graph sizes, edge-weight distributions, and seen and unseen topologies.The motivation is that heterogeneous local structures and edge weights collectively shape QAOA energy, unlike the repetitive tree neighborhoods of random regular graphs.Source: §IV · p. 4

A. Data Generation

  • Training labels cover random regular, Erdős–Rényi, and heavy-hex graphs, with solver-derived angles through p = 5; Pauli-propagation labels yield nearly identical approximation ratios to exact state-vector labels on 20-node instances.Out-of-distribution tests include Erdős–Rényi graphs with 150 and 200 nodes, plus Barabási–Albert and 2D-grid topologies.Source: A. Data Generation · p. 4, Table I · p. 4

B. Target normalization

  • Per-instance cost-operator rescaling reduces the weight-dependent variation in γ targets; the model learns rescaled γ while β remains unchanged, then rescales γ back at inference.The rescaled targets have a smaller range, and the authors find this normalization crucial for training one model across graph families.Source: B. Target normalization · pp. 4–5, Figure 3 · p. 5

C. Machine learning models

The models compare prediction from coarse graph statistics with architectures that use graph structure and edge weights. They are trained jointly across graph families and compared under shared data splits and a common training protocol.

C. Machine learning models

  • The MLP uses global graph features alone, while the other models incorporate graph structure and edge weights through edge-token transformers, node-based graph encoders, or message passing.The evaluated architectures are EdgeTF, DiffTF, GraphTF, GCN, GNN, and GIN, alongside the MLP baseline.Source: C. Machine learning models · pp. 5–6, Figure 5 · p. 6

D. Model training

  • For each architecture and circuit depth, models train jointly across all four graph families using fixed training, validation, and test splits shared across architectures, with MSE between predicted and target angle vectors as the objective.Hyperparameters are selected by validation performance from a grid search over learning rates 1e-4, 5e-4, 1e-3, and 1e-2 and batch sizes 8 and 32; Adam is used with a selected learning rate of 1 × 10−3.Source: D. Model training · p. 6
  • Training runs for up to 100 epochs with validation-loss early stopping, and reported results are averaged over five independent random seeds.The schedule uses a five-epoch linear warm-up, cosine annealing, and gradient clipping at 1.0.Source: D. Model training · p. 6

V. RESULTS

Learned models occupy a middle ground between nearly free fixed-angle lookup and the highest-quality but costly solver, with inference several orders faster and generally above 99% of solver accuracy. Graph-sensitive models outperform the global-feature MLP more as circuit depth increases.

A. Pareto fronts

  • Learned models sit between fixed-angle lookup and the solver on the runtime–AR frontier, running several orders faster while generally recovering over 99% of solver accuracy.The fixed-angle lookup is effectively free but has the lowest AR; the solver achieves the highest quality through per-instance optimization.Source: A. Pareto fronts · pp. 6–7, Figure 6 · p. 7

B. Solver-relative performance across instances

  • Because mean Reach is consistently near one across learned models, the analysis also compares the fraction of test instances meeting or exceeding a Reach threshold.The reported threshold fraction is computed for each model and depth; results are averaged across five training seeds.Source: B. Solver-relative performance across… · p. 7
  • At p=3, the GNN reaches 99.9% of solver AR on 86.64% of instances versus 51.02% for the MLP; at p=4, the fractions are 84.39% and 51.48%.The GIN reaches the threshold on 81.40% and 79.38% of instances at p=3 and p=4, respectively.Source: B. Solver-relative performance across… · p. 7, Figure 7 · p. 8, Table II · p. 8
  • GNN and GIN outperform the global-feature MLP more as p increases, suggesting that graph-structure-based prediction is beneficial beyond angle transfer based on concentration.Source: B. Solver-relative performance across… · p. 7
  • Inference results also cover unseen 2D-grid and Barabási–Albert topologies at p=2 across node counts, with median Reach and quartile error bars across five seeds.Source: Figure 8 · p. 8

C. Generalization to unseen graph families

The learned models transfer to unseen graph families and larger graph sizes, but their performance depends on architecture and topology. The MSE training loss is only a reliable energy proxy under limited conditions, creating a trade-off with more costly energy-based objectives.

C. Generalization to unseen graph families

  • On unseen 2D grids and Barabási–Albert graphs, most learned models raise median Reach from roughly 0.81–0.94 for fixed angles to over 0.95, though GNNs become unstable on larger BA graphs.The test families contrast spatially local grids with scale-free BA networks; these topological differences shift solver β angles.Source: C. Generalization to unseen graph… · p. 8

D. Generalization to unseen graph sizes

E. Limitations of MSE-style proxy objectives

  • MSE errors become less correlated with energy as predictions move farther from the optimum, limiting MSE as a proxy on complex landscapes.MSE can serve as a proxy on easy periodic landscapes when errors are low; more accurate energy-based objectives carry greater computational overhead, particularly at higher depth.Source: E. Limitations of MSE-style proxy… · p. 9, Figure 10 · p. 9

F. Scaling behavior with dataset size

Increasing training data generally improves predicted-angle quality, and hardware tests find learned-model samples largely indistinguishable from solver samples while outperforming fixed angles. The discussion highlights the speed–accuracy trade-off, transfer across graph families, and limits imposed by proxy losses and approximate training labels.

F. Scaling behavior with dataset size

  • With all training data, GNN and GIN reached approximation ratios of 87.71% and 87.70%, respectively; increasing dataset size generally narrowed the gap toward the solver.All models with access to graph topology generally outperformed fixed angles, while the MLP had the lowest reported ratio, 86.89%, at 10% of the training data.Source: F. Scaling behavior with dataset size · pp. 9–10

VI. DISCUSSION AND CONCLUSION

  • A single model trained across graph families can replace per-instance optimization with a forward pass, reducing angle-generation time by several orders of magnitude; transfer to unseen graphs varies by architecture.Rescaling γ angles supports joint training across random regular, Erdős–Rényi, and heavy-hex graphs; plain transformers generalize to larger and unseen graphs more reliably than message-passing networks.Source: §VI · pp. 10–11

G. Hardware validation

  • Across 630 heavy-hex graphs on ibm boston, learned-model CVaRs were largely indistinguishable from the solver and outperformed fixed angles.The evaluation used 8,192 samples per graph at depths p = 1, 2, and 3; Fig. 12 reports CVaR at α = 90%, 95%, and 99%.Source: Figure 12 · p. 10, G. Hardware validation · p. 10

VII. DATA AVAILABILITY

  • The open-source release provides trained models and inference code across depths p ∈ {1, . . . , 5} as a drop-in replacement for per-instance optimization.Pretrained models and training code are made available through the named repositories and pipeline.Source: §VII · p. 11

Appendix A: Experimental settings of prior work

The appendix compares prior QAOA angle-setting evaluation practices, describes how training and test data are constructed, and checks solver-label quality and lower-tail model performance. The reported analyses highlight both depth-wise improvements in solver angles and variation in coverage across graph families and depths.

Appendix A: Experimental settings of prior work

  • Prior ML angle-setting evaluations vary in graph size and depth, post-prediction optimization, hardware versus simulation, and public code or model availability, complicating direct comparisons.Direct prediction is largely studied on graphs up to 20 nodes, while this work evaluates up to 200 nodes; refined predictions may include further optimization.Source: Appendix A · p. 13

1. Distribution of QAOA angles and ARs

  • All but ten graph instances have ∆AR > 0 between successive depths, and the solver-angle distributions show high ARs that increase with depth.A few AR values exceed 1, attributed to Pauli-propagation energy approximation errors.Source: §1 · p. 13, Figure 13 · p. 15

2. Training, validation, and test data split

  • Instances are split within each graph family, with 15% held out for testing and 90% of the remainder assigned to training, while validation supports early stopping.The held-out test instances remain consistent across circuit depths and are reserved for final results.Source: §2 · p. 13
  • Higher-depth datasets contain fewer Erdős–Rényi instances, and some large, dense Erdős–Rényi and random d-regular instances were excluded because they exceeded the compute budget.Ten heavy-hex instances at p = 5 were also removed after their energy was worse than at p = 4.Source: §2 · pp. 13, 15

1. Solver-relative performance distributions

  • At p = 5, the GNN’s worst-performing 5% of instances average 97.47% of solver accuracy, and its worst instance across five seeds reaches 93.41%.At p = 3, fifth-percentile Reach is 99.80% for the GNN and 99.13% for the MLP; the GNN and GIN have the strongest overall lower-tail performance at larger depths.Source: §1 · p. 15

2. Joint versus topology-specific training

Jointly trained models closely match topology-specific training, while global degree features account for much of the MLP’s predictive signal. Additional analyses examine size and topology shifts and describe model architectures used for angle prediction.

3. Influence of global graph features

  • At p = 3, mean degree alone recovers most of the full MLP’s performance, while node count alone reduces AR and additional structural statistics provide no improvement over simpler degree-based features.Adding graph size or degree variation provides a small further improvement.Source: §3 · p. 16, Figure 15 · p. 17

2. Joint versus topology-specific training

  • At p = 1, joint-versus-topology-specific AR differences are below 3×10^-4; at p = 3, the largest difference is about 2 × 10^-3 for the Graph Transformer on random d-regular graphs, where joint training performs better.Across graph families and both architectures, joint training closely matches topology-specific training without a consistent loss.Source: §2 · p. 16, Figure 14 · p. 17

Appendix D: Distribution-shift experiments

  • The distribution-shift analyses examine both larger-than-training graphs and unseen topologies using solver-optimized angles as reference solutions.The larger-graph test uses 150- and 200-node instances; weighted Barabási–Albert and 2D grid graphs are absent from training.Source: Appendix D · p. 17, §1 · p. 17, §2 · p. 17

1. Large-scale graphs

  • For 150- and 200-node Erdős–Rényi graphs, changed graph statistics and γ-angle distributions create input distribution shift, and the reported AR declines.The authors propose training on larger instances or decomposing large graphs into subgraphs as future directions.Source: §1 · p. 17

2. Unseen graph topologies

  • On unseen weighted Barabási–Albert and 2D grid graphs, approximation ratios shift higher from p = 1 to 4, with non-negative ∆AR for every evaluated instance.The optimized angles are unimodal within [0, π/2] and follow smooth layer-wise schedules; the passage attributes this to Interp. training.Source: §2 · p. 17

Appendix E: Model architecture details

  • The architecture set comprises a global-feature MLP and six graph-based models, which differ in how they represent graph structure and edge weights before predicting QAOA angles.The models are trained separately for each circuit depth to predict the 2p parameters minimizing expected Max-Cut energy.Source: Appendix E · pp. 17–18

1. Multilayer Perceptron

  • The MLP uses global graph-level features, four fully connected hidden layers with ReLU and dropout, then layer normalization and a linear projection to the 2p angles.It serves as a baseline for predicting angles from coarse graph properties without using graph structure or edge weights.Source: §1 · pp. 18–19

2. Edge-token transformer models

Edge-token transformers represent graph edges as tokens and process them jointly with a global token to predict QAOA angles. The diffusion-based variant adds noise conditioning during training while retaining deterministic regression at inference.

2. Edge-token transformer models

  • Edge-token models encode each edge’s endpoints and weight, process edge tokens jointly with a global graph-feature token, and use the resulting graph representation to predict QAOA angles.The edge-token family includes EdgeTF and diffusion-based DiffTF.Source: §2 · p. 19

a. Edge transformer

  • EdgeTF uses self-attention across observed edges, allowing information exchange beyond local neighborhoods, and randomly relabels nodes during training to discourage dependence on arbitrary node identities.Sinusoidal node-index encodings also apply to graphs with more nodes than those seen during training.Source: a. Edge transformer · pp. 19–20

b. Diffusion-based edge-token transformer

  • DiffTF applies a sampled forward-noising process to inputs during training as stochastic regularization, but predicts deterministically from clean inputs at inference without reverse diffusion.A timestep embedding conditions the projected features before they enter the EdgeTF-style transformer backbone.Source: b. Diffusion-based edge-token… · p. 20

3. Node-based graph encoders

Node-based encoders update node representations using graph connectivity and edge weights, then pool them into graph-level features for QAOA angle prediction. GraphTF applies attention only between neighboring nodes and incorporates edge weights into attention scores.

3. Node-based graph encoders

  • Node-based encoders update node features using connectivity and edge weights, pool node representations, and combine them with global graph features to predict QAOA angles.GraphTF and GCN are the two node-based models considered.Source: §3 · p. 20

a. Graph Transformer

  • GraphTF initializes nodes from log-degree and signed-log weighted-degree features, adds Laplacian positional encodings, and restricts self-attention to graph neighbors.Random sign flips during training address the sign ambiguity of Laplacian eigenvectors.Source: a. Graph Transformer · pp. 20–21
  • GraphTF adds a learned per-head bias derived from edge weights to attention scores, then mean-pools node representations and combines them with projected global features to predict angles.Non-neighbor attention scores are set to −∞, yielding zero attention weight.Source: a. Graph Transformer · p. 21

b. Graph Convolutional Network

The section compares weighted graph-convolution and message-passing encoders for predicting QAOA angles. The GNN uses receiver-conditioned messages and an unnormalized neighbor sum, while the graph-convolution model directly aggregates weighted neighbor representations.

b. Graph Convolutional Network

  • The GraphConv model iteratively updates node features using weighted information from directly connected neighbors, then pools node embeddings and combines them with graph-level features to predict 2p QAOA angles.Its implementation uses z-score-normalized node degrees, two GraphConv layers with ReLU and dropout, and a two-layer prediction head.Source: b. Graph Convolutional Network · p. 21

4. Message-passing graph networks

  • Message-passing graph networks compute messages, aggregate them across neighborhoods, and update node states; the section considers GNN and GIN models..Source: §4 · p. 21

a. Graph Neural Network

  • The GNN scales each neighbor embedding by its edge weight, conditions its message on both the neighbor and receiver embeddings, and updates nodes using the aggregated signal.The receiver-conditioned message can vary across edges arriving at different nodes; the model uses a global mean-pooling readout and predicts QAOA parameters.Source: a. Graph Neural Network · p. 22
  • The GNN sums incoming messages without degree normalization, so high-degree nodes accumulate larger aggregates, reflecting local connectivity density relevant to QAOA cost-Hamiltonian terms.Source: a. Graph Neural Network · p. 22

b. Graph Isomorphism Network

The GIN is designed to attain the 1-WL expressivity bound through injective updates and readout. The implementation adapts it to weighted QAOA graphs and uses mean pooling by default.

b. Graph Isomorphism Network

  • GIN uses sum aggregation and injective updates and readout to attain the 1-WL graph-isomorphism test's expressivity bound for message-passing GNNs.The paper describes sum aggregation as a universal injective function over multisets.Source: b. Graph Isomorphism Network · p. 22
  • The implementation scales neighbor embeddings by edge weights before summation, creating edge-conditioned GIN layers, and uses a single global pooling step rather than layer-wise concatenated readouts.Mean pooling is the default; the sum-based injective readout is available but not the default experimental configuration.Source: b. Graph Isomorphism Network · p. 22
  • The regressor embeds global graph statistics, broadcasts that context to nodes, and refines the initial embeddings through stacked edge-conditioned GIN layers before predicting QAOA parameters.The statistics include node and edge counts, edge-to-node ratio, mean degree, and degree standard deviation; the pooled graph vector is concatenated with global features for decoding.Source: b. Graph Isomorphism Network · pp. 22–23
Loading 2610.23296v1…