量子近似优化算法
本文研究了量子近似优化算法在 MaxCut 问题上的性能,并使用自动微分和随机梯度下降优化量子电路。研究表明,使用批处理可以分摊训练成本,QAOA 算法可以在短小的电路深度下超越多项式时间的高曼 - 威廉姆斯算法,在固定电路深度下的表现不受问题规模的影响。此外,MaxCut QAOA 可在有限量子比特连接的门控量子计算机上有效实现,使用量子比特交换网络。
Nov, 2018
本文深入研究了混合量子 - 经典变分算法中外循环经典优化的有效途径,并在 MaxCut 问题上通过发现优化参数中的模式,提出了启发式策略以在 $O (poly (p) $) 的时间内,找到近似最优的 p 级 QAOA $o$ 参数。与量子退火比较发现 QAOA 可以通过优化学习利用非绝热机制来克服与湮灭光谱间隙相关的挑战。在资源分析中,揭示了仅当问题规模大于数字模拟但可在近期设备中访问时,优化才是重要的,并提出用 2D 中性原子系统实现大型 MaxCut 问题的可行方法,从而挑战最佳经典算法所达到的范畴。
Dec, 2018
本文研究了通过分治启发式方法来解决计算机中的复杂组合优化问题,提出了一种名为 QAOA-in-QAOA($ ext {QAOA}^2$)的解决方案,可以在较小量子机器的情况下解决异常大的 MaxCut 问题,并证明保证了其最优性。实验结果表明,该方法相对于目前已知的最好的经典算法有竞争力甚至更好的性能。
May, 2022
用两位随机矩阵构建的一类新型的经典概率电路,通过数值研究在解决各种增长规模的图上的最大割问题方面,提出的变分电路比量子近似优化算法表现出更好的性能。
Aug, 2023
本文介绍了量子近似优化算法(QAOA),并证明了对于固定参数和来自合理分布的实例,目标函数值会在多数情况下几乎相等,这适用于大型 3 - 正则图上的 MaxCut 实例,并且结果可泛化到其他问题和深度量子电路,并且发现使用相同的参数可以在不同的位数下获得良好的性能表现,这为减少或消除外循环优化提供了可能性。
Dec, 2018
本文探讨了 RQAOA 算法在 MAX-k-CUT 问题上的应用,进行了经典算法和量子经典混合算法的比较,并发现 level-1 的 RQAOA 算法可以优于现有 SDP 基础的经典算法,该算法可能是 NISQ 设备的有用算法。
Nov, 2020
本文演示了 Google Sycamore 超导量子位计算机在组合优化问题上的应用及 QAOA 算法,克服了硬件连接性图不同于实际问题图的挑战,并提出了在未来的开发中应注重更多这样的问题。
Apr, 2020
我们的研究通过使用图神经网络(GNN)作为热启动技术来优化 QAOA 初始化,为了减少量子计算资源的开销,牺牲了大量的经济计算资源,从而提高了 QAOA 的效果;实验结果表明 GNN 有助于提高 QAOA 的性能,为量子计算中的混合量子 - 经典方法开辟了新的途径,也为实际应用做出了贡献。
Mar, 2024
本研究对量子近似优化算法的性能进行了评估,其中研究了加权 MaxCut 和 2-SAT 问题实例的概率、期望能值和近似比相关的比率三个不同的度量方式。研究表明,该算法的性能强烈依赖于问题实例,D-Wave 2000Q 量子退火器的性能表现优于在模拟器上执行的量子近似优化算法。
Jul, 2019
理解参数化量子电路在机器学习任务中的能力是量子机器学习中最重要的问题之一。本文通过函数逼近的角度分析了参数化量子电路的表达能力,并展示了在逼近连续和平滑函数方面数据重新上传参数化量子电路的明确构造,以及其在宽度、深度和可训练参数数量方面的定量逼近误差界限。此外,我们还将提出的参数化量子电路与近乎最优的深度神经网络进行了比较,在逼近高维平滑函数方面,表明参数化量子电路和深度神经网络之间的模型尺寸比在输入维度方面呈指数级减小,这为展示量子机器学习的量子优势提供了潜在的新途径。
Oct, 2023