Mar, 2024

图学习用于量子近似优化算法参数预测

PDF
TL;DR我们的研究通过使用图神经网络（GNN）作为热启动技术来优化 QAOA 初始化，为了减少量子计算资源的开销，牺牲了大量的经济计算资源，从而提高了 QAOA 的效果；实验结果表明 GNN 有助于提高 QAOA 的性能，为量子计算中的混合量子 - 经典方法开辟了新的途径，也为实际应用做出了贡献。
quantum computingcombinatorial optimizationquantum approximate optimization algorithm (qaoa)graph neural networks (gnn)hybrid quantum-classical approaches
发现论文，激发创造
  • 量子近似优化算法在最大割问题上的表现

    本文研究了量子近似优化算法在 MaxCut 问题上的性能，并使用自动微分和随机梯度下降优化量子电路。研究表明，使用批处理可以分摊训练成本，QAOA 算法可以在短小的电路深度下超越多项式时间的高曼 - 威廉姆斯算法，在固定电路深度下的表现不受问题规模的影响。此外，MaxCut QAOA 可在有限量子比特连接的门控量子计算机上有效实现，使用量子比特交换网络。

    Nov, 2018

  • 学习优化变分量子电路来解决组合问题

    本文提出了两种基于机器学习的方法，采用强化学习 (RL) 框架和核密度估计 (KDE) 技术，分别用于优化 QAOA 电路，从小规模问题实例中学习，然后在较大的问题实例中使用，结果表明与其他现成的优化器相比，这两种方法可以将优化度缺口减少多达 30.15 个因子。

    Nov, 2019

  • 量子近似优化算法：性能、机制及在近期设备上的实现

    本文深入研究了混合量子 - 经典变分算法中外循环经典优化的有效途径，并在 MaxCut 问题上通过发现优化参数中的模式，提出了启发式策略以在 $O (poly (p) $) 的时间内，找到近似最优的 p 级 QAOA $o$ 参数。与量子退火比较发现 QAOA 可以通过优化学习利用非绝热机制来克服与湮灭光谱间隙相关的挑战。在资源分析中，揭示了仅当问题规模大于数字模拟但可在近期设备中访问时，优化才是重要的，并提出用 2D 中性原子系统实现大型 MaxCut 问题的可行方法，从而挑战最佳经典算法所达到的范畴。

    Dec, 2018

  • 多起点方法用于量子近似优化

    本研究使用多次启动优化方法优化量子近似优化算法在图形聚类问题中的性能，并证明重用类似问题的最优参数可以扩展用于 MAXCUT 的相似结果。

    May, 2019

  • 平面超导处理器上的非平面图问题的量子近似优化

    本文演示了 Google Sycamore 超导量子位计算机在组合优化问题上的应用及 QAOA 算法，克服了硬件连接性图不同于实际问题图的挑战，并提出了在未来的开发中应注重更多这样的问题。

    Apr, 2020

  • QAOA-in-QAOA：在小型量子机器上解决大规模 MaxCut 问题

    本文研究了通过分治启发式方法来解决计算机中的复杂组合优化问题，提出了一种名为 QAOA-in-QAOA（$ ext {QAOA}^2$）的解决方案，可以在较小量子机器的情况下解决异常大的 MaxCut 问题，并证明保证了其最优性。实验结果表明，该方法相对于目前已知的最好的经典算法有竞争力甚至更好的性能。

    May, 2022

  • 通过经典神经网络学习量子神经网络的学习方法

    本文提出一种使用经典神经网络协助量子学习的元学习方法，通过训练经典递归神经网络对 Quantum Approximate Optimization Algorithm (QAOA) for MaxCut，QAOA for Sherrington-Kirkpatrick Ising model 以及 Hubbard model 的参数进行快速优化，以减少优化迭代次数。同时，发现该方法可以推广到其他问题类型，使得量子学习更加高效。

    Jul, 2019

  • 量子退火初始化量子近似优化算法

    研究了 QAOA 在 MaxCut 问题上的优化问题，指出随机初始化容易陷入低级局部最小点，通过 Trotterized quantum annealing 协议实现参数初始化，并找到最佳的 Trotter 时间步长，这为在近期量子设备上实现 QAOA 提供了实用的初始化方法，同时揭示了 QAOA 和量子退火之间的新联系。

    Jan, 2021

  • 量子近似优化算法实现量子霸权

    该文研究了基于门模型的量子计算机上的量子近似优化算法（QAOA）及其可能表现出的量子霸权，发现即使低深度 QAOA 的输出也无法在任何经典设备上进行高效模拟，并提出了量子绝热算法（QADI）仍存在一个 oracle 使采样成为可能的限制。这表明 QAOA 不仅可能在优化方面有用，而且在实现量子霸权方面也具有潜力。

    Feb, 2016

  • 图形 Q-Learning 用于组合优化

    本论文提出并证明了图神经网络可以应用于解决组合优化问题，通过将优化过程视为顺序决策问题，使用 Q-Learning 训练图神经网络可以在参数和训练时间上只占一小部分的情况下接近达到最先进的启发式求解器的性能。

    Jan, 2024