用图神经网络指导量子优化,大幅减少电路评估次数。
Query-Efficient Quantum Approximate Optimization via Graph-Conditioned Trust Regions
- 用图神经网络预测参数分布,构建自适应搜索区域
- 评估次数从343降至45次,解质量与传统方法相当
- 适合低深度量子计算中需节省评估成本的场景
在低深度量子近似优化算法(QAOA)实现中,主要开销常为目标函数评估次数而非电路深度。本文提出一种图条件信任域方法以降低查询成本。通过图神经网络预测QAOA参数的高斯分布N(μ, Σ),均值用于初始化局部优化器,协方差定义椭球形信任域约束搜索范围,预测不确定性决定实例相关的评估预算。由此学习到的分布构成搜索策略,而不仅限于初始参数估计。在局部光滑性、曲率、校准和噪声的显式假设下,推导出信任域内目标函数退化上界、梯度方差下界、去极化噪声下期望目标排序保持性及有限样本覆盖率保证。在n=8-16顶点的Erdos-Renyi、3-regular、Barabasi-Albert和Watts-Strogatz图上,对p=2深度的MaxCut问题进行评估。相比随机重启和最强的基线学习点预测方法,平均评估次数由343和85下降至45±7,同时采样近似比保持在浓度启发式方法的3个百分点内。该方法不提升绝对近似比,优势在于同等解质量下显著降低查询成本。实验中预测不确定性已校准(ECE=0.052,Spearman相关系数ρ=0.770),且学习到的信任域可迁移至训练时未使用的图规模。结果表明,在低深度、查询主导的场景下,图条件信任域可在不修改变分族的前提下有效减少QAOA的查询成本。
原文摘要 · Abstract (English)
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. 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. 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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。