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

研究人员开发了一种名为后处理变异调度量子算法的新算法，用于解决在量子计算机操作时间内带有约束的组合优化问题（COPs）。该创新算法的新颖之处在于利用后处理技术结合变异调度，以在短时间内获得COPs的高质量解决方案。

COPs在物流、供应链管理、机器学习、材料设计和药物发现等许多不同领域都有应用，用于找到复杂问题的最佳解决方案。这些问题在经典计算机上通常需要非常大的计算量，因此使用量子计算机解决COPs引起了学术界和工业界的广泛关注。

量子计算机利用了超定位的量子特性，利用专门的量子比特，可以存在于0或1或两者的任意组合的无限又有限数量的状态，从而快速解决大型问题。然而，当COPs涉及约束时，传统的量子算法如绝热量子退火很难在量子计算机的操作时间内获得接近最优解。近年来量子技术的进步导致了量子退火器和门式量子设备等设备的出现，提供了适合解决COPs的平台。不幸的是，它们容易受到噪声的影响，这限制了它们用于具有较低计算成本的量子算法。

为了解决这一挑战，日本早稻田大学计算机科学与通信工程系的Tatsuhiko Shirai助理教授和Nozomu Togawa教授最近开发了一种突破性的后处理变异调度量子算法（pVSQA）。Shirai博士解释说：“解决COPs的两种主要方法是变异调度和后处理。我们的算法将变异调度与将不可行解决方案转换为可行解决方案的后处理方法相结合，使我们能够在量子退火器和门式量子计算机上实现对COPs的近最优解。”他们的研究于2024年3月13日发表在《IEEE量子工程期刊》上。

这一创新的pVSQA算法首先利用量子设备通过量子计算生成一个变异量子状态。然后利用后处理方法将不可行解决方案转换为可行解决方案，使概率分布中只剩下可行解决方案。然后使用经典计算机利用这个新的概率分布计算成本函数的能量期望值。重复这个计算可以得到一个接近最优解。

研究人员使用模拟器和真实量子设备（如量子退火器和门式量子设备）分析了该算法的性能。实验结果显示，pVSQA在模拟器上在预定时间内实现了接近最优的性能，并且在真实量子设备上优于没有后处理的传统量子算法。

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

总之，这项研究标志着在使用量子计算机解决COPs方面迈出了重要一步，为解决各个领域的复杂现实问题带来了希望。