用于组合优化问题高质量解决方案的新型量子算法

传统的量子算法无法解决受量子计算机运行时间限制的组合优化问题（COP）。 为了解决这个问题，研究人员开发了一种称为后处理变分调度量子算法的新算法。 这种创新算法的新颖之处在于使用后处理技术与变分调度相结合，可以在短时间内获得高质量的 COP 解决方案。

组合优化问题 (COP) 在许多不同领域都有应用，例如物流、供应链管理、机器学习、材料设计和药物发现等，用于寻找复杂问题的最佳解决方案。 使用经典计算机来解决这些问题通常需要非常密集的计算，因此使用量子计算机解决 COP 引起了学术界和工业界的极大关注。

量子计算机利用叠加的量子特性，使用专门的量子位，可以以无限但包含的 0 或 1 或两者的任意组合状态存在，来快速解决大型问题。 然而，当 COP 涉及约束时，绝热量子退火等传统量子算法很难在量子计算机的运行时间内获得接近最优的解决方案。 量子技术的最新进展催生了量子退火器和门型量子器件等设备，为解决 COP 提供了合适的平台。 不幸的是，它们容易受到噪声的影响，这限制了它们在计算成本较低的量子算法中的适用性。

为了应对这一挑战，日本早稻田大学计算机科学与通信工程系助理教授 Tatsuhiko Shirai 和 Nozomu Tokawa 教授最近开发了一种突破性的后处理变分调度量子算法 (pVSQA)。 “使用量子设备解决 COP 的两种主要方法是变分调度和后处理。我们的算法将变分调度与后处理方法相结合，将不可行的解决方案转化为可行的解决方案，使我们能够在有限的 COP 上实现接近最优的解决方案。量子退火器和基于门的量子计算机，”白井博士解释道。 他们的研究于 2024 年 3 月 13 日发表在《IEEE Transactions on Quantum Engineering》杂志上。

创新的pVSQA算法使用量子设备首先通过量子计算生成变分量子态。 然后用它生成一个概率分布函数，该函数由 COP 约束内的所有可行和不可行的解决方案组成。 接下来，后处理方法将不可行解转换为可行解，使概率分布只剩下可行解。 然后使用经典计算机使用这个新的概率分布来计算成本函数的能量期望值。 重复此计算会得到接近最优的解决方案。

研究人员使用模拟器和真实的量子设备（例如量子退火器和门型量子设备）分析了该算法的性能。 实验表明，pVSQA 在模拟器上的预定时间内实现了接近最优的性能，并且优于传统的量子算法，无需在真实量子设备上进行后处理。

白井博士强调了该算法的潜在应用，他表示：“迫切需要进行剧烈的社会变革来解决各种社会问题。例子包括实现碳中和社会以解决气候变化问题，以及实现可持续发展目标以解决气候变化问题。” “能源需求增加和粮食短缺等问题。有效解决组合优化问题是实现这些转型的核心。我们的新方法将在实现这些长期社会转型中发挥重要作用。”

总之，这项研究标志着使用量子计算机解决 COP 问题向前迈出了重要一步，有望解决各个领域的复杂现实问题。

参考

数字编号： https://doi.org/10.1109/TQE.2024.3376721

作者：白井龙彦1、户川望1

所属机构：早稻田大学计算机科学与通信工程系

关于早稻田大学

早稻田大学位于东京市中心，是一所领先的私立研究型大学，自 1882 年以来一直致力于本地和全球层面的学术卓越、创新研究和公民参与。这所大学在其历史上培养了许多变革者，其中包括九位总理以及商界、科技界、文学界、体育界、电影界的多位领导人。 早稻田大学与海外研究机构有着密切的合作，致力于推进尖端研究并培养能够为解决复杂的全球社会问题做出贡献的领导者。 根据联合国2015年通过的可持续发展目标（SDG），大学设定了到2032年实现零碳校园的目标。

要了解有关早稻田大学的更多信息，请访问 https://www.waseda.jp/top/en

关于助理教授白井龙彦

白井龙彦 (Tatsuhiko Shirai) 目前是日本早稻田大学计算机与通信工程系助理教授。 他获得了硕士和博士学位。 分别于2013年和2016年获得东京大学物理学博士学位。 2022年获得SLDM研究组优秀论文奖。 他的研究兴趣包括量子算法、量子开放系统和量子计算。 他是日本物理学会会员。