QAOA-Predictor - A Graph Neural Network for Predicting QAOA Performance

Quantum Computing promises to solve complex combinatorial optimization problems more efficiently than classical methods, with the Quantum Approximate Optimization Algorithm (QAOA) being a leading candidate. Recent fixed-parameter variations of QAOA eliminate costly run-time optimization, but determining their optimal initialization as well as the number of required layers (p) for a target solution remains a critical, unsolved challenge. In our recent work, we introduce QAOA-Predictor, a graph neural network designed to predict the success probability of Linear-Ramp QAOA (LR-QAOA) across different problem instances and depths. By learning from a large dataset of simulated LR-QAOA runs, the predictor can quickly estimate performance without costly quantum simulations or hardware runs, guiding users to make informed decisions about when and how to deploy QAOA effectively.

How the predictor works

The pipeline begins with a quadratic unconstrained binary optimization (QUBO) formulation, standard for problems such as Max-Cut, knapsack, or number partitioning. The QUBO is converted to an Ising spin model and normalized. The resulting interaction graph — nodes for variables, weighted edges for couplings — becomes the input to a graph neural network. Message-passing layers build node embeddings, global pooling produces a fixed-size graph representation, and a small multilayer perceptron combines this with the scalar values of p and the ramp amplitudes to output a probability between 0 and 1.

Figure 1 shows the end-to-end workflow: from a QUBO matrix to normalized Ising graph, GNN processing, and final probability prediction that guides LR-QAOA execution. The schematic highlights how a single forward pass replaces costly parameter optimization.

The model was trained on a large set of simulated LR-QAOA instances across 12 different problem classes, from classic graph problems (Max-Cut, vertex cover) to unstructured ones (uniform randomly generated). The simulator provides the “ground-truth” success probabilities by sampling 10,000 shots per instance. A simple mean-absolute-error loss was minimized, and the model was compared against a convolutional neural network (treating the Hamiltonian matrix as an image) and a k-nearest-neighbor baseline using hand-crafted matrix features.

Results and insights

Figure 2: Mean probability of sampling the optimal solution versus circuit depth p for Max-Cut (left) and Knapsack (right) across problem sizes N = 5 to 19. Each point averages 150 random instances.

Figure 2 shows the performance of LR-QAOA with fixed ramp amplitudes Δγ,β = 0.3 on two representative problem classes. LR-QAOA works by replacing the expensive per-layer parameter optimization of standard QAOA with a simple linear schedule: the angles ramp linearly from zero across p layers, controlled by just two global amplitudes. This linear schedule is inspired by quantum annealing and is not tailored to any specific problem instance, yet it achieves surprisingly good performance across a wide range of cases. This makes the method lightweight and easy to deploy. The left panel (Max-Cut) shows its strengths: success probability rises reliably with depth, reaching 80 % for N = 7 already at p = 20 and for N = 14 at p = 60. Yet the weaknesses are equally clear. Larger instances demand far more layers, and the right panel (Knapsack) shows that overall success probabilities remain lower and improve only modestly with depth. For some problem classes, simply adding layers does not compensate for structural hardness—highlighting that LR-QAOA is a practical but not universal solver.

To understand the data the model was trained on, Figure 3 presents a PCA embedding of the validation set. When colored by problem class (left), the points form distinct, clearly visible clusters. This shows that the 12 problem types (Max-Cut, Knapsack, vertex cover, etc.) possess clearly different structural signatures in their Ising Hamiltonians. When colored by instance size N (right), a systematic shift appears within each cluster, giving the model natural cues about how performance scales with problem size.

Figure 3: The two-dimensional PCA projection reveals strong class separation and a smooth size dependence, confirming that the dataset is rich and structured enough for reliable learning.

Finally, Figure 4 shows the performance of QAOA-Predictor on the validation instances for Max-Cut (top). The left scatter plots compare predicted versus true success probabilities across layers 1–100, while the right panels zoom in on the best- and worst-predicted instances (colored by error).

The strengths of the approach stand out: for many instances the predictions track the true curves closely, allowing the model to identify promising depths with useful accuracy. The method reliably flags when extra layers will pay off and when they will not.

However, weaknesses appear in several examples, where the predictor deviates more noticeably—especially at intermediate depths or for harder instances. These larger errors show that the GNN's predictions are not perfect and should be used as guidance rather than absolute truth.

Figure4: Left: scatter plots showing prediction quality (MAE across layers 1–100). Right: best and worst instances with predicted and true success probability curves versus depth p.

What this means for quantum computing today

On current quantum hardware, circuit executions are resource-expensive. QAOA-Predictor offers a fast pre-filter: run the GNN, discard parameter sets or entire problem instances whose predicted success probability is too low, and focus quantum resources only on the promising cases. For problems where LR-QAOA already works reasonably well (certain Max-Cut instances, for example), the tool can suggest the smallest p that is likely to reach a target success rate— saving valuable quantum resources. The predictor can therefore also be used to identify promising problem instances and help new users to quickly find cases where quantum advantage might be within reach.

Looking ahead

Our current work is a proof-of-concept that can evolve. Future versions could be trained on real hardware data rather than perfect simulations, incorporate noise models, or even suggest preprocessing steps (variable reduction, graph sparsification) when the predictor flags poor prospects. Another important further step is the quantification of uncertainty in the predictions, so users can better rely on the tool’s guidance.Additionlly, while in this work we only focused on LR-QAOA, the same approach could be adapted to other quantum optimization algorithms, broadening its applicability.

Learn more and try our online demo

For more information, check out our paper, which includes detailed descriptions of the model architecture, training procedure, and comprehensive results across all 12 problem classes. The preprint is available on arXiv: 2603.02990. And if you want to learn more about LR-QAOA itself, the original paper introducing the method is available at Nature npj quantum information.

Also, we have a online version of our approach available at quast-decisiontree.com, where you can test our model with a variety of QUBO instances and see the predicted performance of LR-QAOA across different depths. This tool is designed to be user-friendly and accessible, allowing researchers and practitioners to quickly assess the potential of LR-QAOA for their specific problems without needing to run costly quantum simulations.