用主成分分析压缩量子优化参数空间,提升算法效率。
QAOA-PCA: Enhancing Efficiency in the Quantum Approximate Optimization Algorithm via Principal Component Analysis
- 通过主成分分析提取小规模问题的参数特征,降低大问题优化维度。
- 在相同参数量下,比标准QAOA少约30%迭代次数,效率显著提升。
- 适合资源受限的量子设备,兼顾计算效率与解的质量。
量子近似优化算法(QAOA)是解决组合优化问题的有前途的变分算法,但随着电路层数增加,参数数量线性增长,导致经典优化器需更多迭代,计算负担加重。为此,本文提出QAOA-PCA,一种基于主成分分析(PCA)的重参数化技术,通过从小规模问题的优化参数中提取主成分,降低大规模问题的参数维度。在典型最大割(MaxCut)问题上的实验表明,QAOA-PCA始终比标准QAOA所需迭代次数更少,实现显著效率提升。尽管相比同层数标准QAOA略低约2%的近似比,但在相同参数量下几乎总是表现更优。该方法在效率与性能间取得良好平衡,有效减少优化开销而不明显牺牲解质量。
原文摘要 · Abstract (English)
The Quantum Approximate Optimization Algorithm (QAOA) is a promising variational algorithm for solving combinatorial optimization problems on near-term devices. However, as the number of layers in a QAOA circuit increases, which is correlated with the quality of the solution, the number of parameters to optimize grows linearly. This results in more iterations required by the classical optimizer, which results in an increasing computational burden as more circuit executions are needed. To mitigate this issue, we introduce QAOA-PCA, a novel reparameterization technique that employs Principal Component Analysis (PCA) to reduce the dimensionality of the QAOA parameter space. By extracting principal components from optimized parameters of smaller problem instances, QAOA-PCA facilitates efficient optimization with fewer parameters on larger instances. Our empirical evaluation on the prominent MaxCut problem demonstrates that QAOA-PCA consistently requires fewer iterations than standard QAOA, achieving substantial efficiency gains. While this comes at the cost of a slight reduction in approximation ratio compared to QAOA with the same number of layers, QAOA-PCA almost always outperforms standard QAOA when matched by parameter count. QAOA-PCA strikes a favorable balance between efficiency and performance, reducing optimization overhead without significantly compromising solution quality.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。