Query-Efficient Quantum Approximate Optimization via Graph-Conditioned Trust Regions

Molena Huynh's new paper introduces a graph-conditioned trust-region method that dramatically reduces the query cost of the Quantum Approximate Optimization Algorithm (QAOA). In low-depth QAOA implementations, the dominant expense is often the number of objective evaluations rather than circuit depth. The method uses a graph neural network to predict a Gaussian distribution over QAOA angles, where the mean initializes a local optimizer, the covariance defines an ellipsoidal trust region, and predicted uncertainty determines an instance-dependent evaluation budget. This creates a search policy rather than just an initial parameter estimate.

Evaluated on MaxCut at depth p=2 for Erdos-Renyi, 3-regular, Barabasi-Albert, and Watts-Strogatz graphs with 8-16 vertices, the method reduces mean circuit evaluations from 343 (random restarts) and 85 (strongest learned baseline) to 45±7, while maintaining sampled approximation ratios within 3 percentage points of concentration-based heuristics. The predictive uncertainty is well-calibrated (ECE=0.052, Spearman rho=0.770), and learned trust regions transfer to graph sizes not seen during training. The advantage is purely in reduced query cost at comparable solution quality, not in improving absolute approximation ratios.