组合优化问题 (COP) 在许多不同领域都有应用，例如物流、供应链管理、机器学习、材料设计和药物发现等，用于寻找复杂问题的最佳解决方案。使用经典计算机来解决这些问题通常需要非常密集的计算，因此使用量子计算机解决 COP 引起了学术界和工业界的极大关注。
量子计算机利用叠加的量子特性，使用专门的量子位，可以以无限但包含的 0 或 1 或两者的任意组合状态存在，来快速解决大型问题。然而，当 COP 涉及约束时，绝热量子退火等传统量子算法很难在量子计算机的运行时间内获得接近最优的解决方案。量子技术的最新进展催生了量子退火器和门型量子器件等设备，为解决 COP 提供了合适的平台。不幸的是，它们容易受到噪声的影响，这限制了它们在计算成本较低的量子算法中的适用性。
为了应对这一挑战，日本早稻田大学计算机科学与通信工程系助理教授 Tatsuhiko Shirai 和 Nozomu Tokawa 教授最近开发了一种突破性的后处理变分调度量子算法 (pVSQA)。 “使用量子设备解决 COP 的两种主要方法是变分调度和后处理。我们的算法将变分调度与后处理方法相结合，将不可行的解决方案转化为可行的解决方案，使我们能够在量子退火器和基于门的量子计算机上实现约束 COP 的接近最优的解决方案， ”Shirai 博士解释道。他们的研究于 2024 年 3 月 13 日发表在《IEEE Transactions on Quantum Engineering》杂志上 。
创新的pVSQA算法使用量子设备首先通过量子计算生成变分量子态。然后用它生成一个概率分布函数，该函数由 COP 约束内的所有可行和不可行的解决方案组成。接下来，后处理方法将不可行解转换为可行解，使概率分布只剩下可行解。然后使用经典计算机使用这个新的概率分布来计算成本函数的能量期望值。重复此计算会得到接近最优的解决方案。
研究人员使用模拟器和真实的量子设备(例如量子退火器和门型量子设备)分析了该算法的性能。实验表明，pVSQA 在模拟器上的预定时间内实现了接近最优的性能，并且优于传统的量子算法，无需在真实量子设备上进行后处理。
白井博士强调了该算法的潜在应用，他表示：“解决各种社会问题迫切需要进行剧烈的社会变革。例如，实现碳中和社会以解决气候变化问题，实现可持续发展目标以解决能源需求增加和粮食短缺等问题。有效解决组合优化问题是实现这些转变的核心。我们的新方法将在实现这些长期社会变革中发挥重要作用。”
免责声明：本文由用户上传，如有侵权请联系删除！
