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

基于图条件置信域的查询高效量子近似优化

Abstract: In low-depth implementations of the Quantum Approximate Optimization Algorithm (QAOA), the dominant cost is often the number of objective evaluations rather than circuit depth. We introduce a graph-conditioned trust-region method for reducing this query cost. A graph neural network predicts a Gaussian distribution N(mu, Sigma) over QAOA angles. The mean initializes a local optimizer, the covariance defines an ellipsoidal trust region that constrains the search, and the predicted uncertainty determines an instance-dependent evaluation budget. Thus the learned distribution defines a search policy rather than only an initial parameter estimate.

摘要： 在量子近似优化算法（QAOA）的低深度实现中，主要成本往往是目标函数的评估次数，而非电路深度。我们引入了一种基于图条件的置信域方法来降低这种查询成本。图神经网络（GNN）预测 QAOA 角度上的高斯分布 N(mu, Sigma)。均值用于初始化局部优化器，协方差定义了约束搜索的椭球置信域，而预测的不确定性则决定了针对特定实例的评估预算。因此，学习到的分布定义了一种搜索策略，而不仅仅是初始参数估计。

Under explicit assumptions on local smoothness, curvature, calibration, and noise, we derive bounds on objective degradation within the trust region, lower bounds on gradient variance, preservation of expected objective ordering under depolarizing noise, and finite-sample coverage guarantees. We evaluate the method for MaxCut at depth p = 2 on Erdos-Renyi, 3-regular, Barabasi-Albert, and Watts-Strogatz graphs with n = 8-16 vertices. Relative to random restarts and the strongest learned point-prediction baseline, the method reduces the mean number of circuit evaluations from 343 and 85 to 45 +/- 7, while maintaining sampled approximation ratios within 3 percentage points of concentration-based heuristics.

在对局部平滑度、曲率、校准和噪声做出明确假设的前提下，我们推导了置信域内目标函数退化的界限、梯度方差的下界、去极化噪声下期望目标排序的保持性，以及有限样本覆盖保证。我们在 n = 8-16 个顶点的 Erdos-Renyi、3-正则、Barabasi-Albert 和 Watts-Strogatz 图上，针对深度 p = 2 的 MaxCut 问题评估了该方法。与随机重启和最强的学习点预测基准相比，该方法将平均电路评估次数从 343 次和 85 次降低至 45 +/- 7 次，同时保持采样近似比在基于集中度启发式算法的 3 个百分点以内。

The method does not improve absolute approximation ratios; its advantage is reduced query cost at comparable solution quality. The predictive uncertainty is calibrated in the experiments, with ECE = 0.052 and Spearman correlation rho = 0.770, and the learned trust regions transfer to graph sizes not used during training. The results identify a low-depth, query-dominated regime in which graph-conditioned trust regions reduce the query cost of QAOA without modifying the ansatz.

该方法并未提高绝对近似比；其优势在于在同等解质量下降低了查询成本。实验中预测的不确定性经过了校准，ECE 为 0.052，Spearman 相关系数 rho 为 0.770，且学习到的置信域可迁移至训练时未使用的图规模。研究结果确定了一种低深度、查询主导的机制，在这种机制下，基于图条件的置信域可以在不修改 ansatz 的情况下降低 QAOA 的查询成本。