谷歌量子AI的最新理论研究表明，大规模量子计算机能够解决传统经典计算机无法处理的某些优化问题。
从设计更高效的航线到组织临床试验，优化问题无处不在。然而对于许多现实世界的挑战，即使是最强大的超级计算机也难以找到最佳解决方案。这引发了量子计算领域一个持续数十年的重要问题：量子机器能否在经典计算机失败的优化问题上取得成功？这一直是一个极其困难的数学问题，在很大程度上仍未解决。随着量子硬件能力的快速发展，研究大规模容错量子计算机最终商业和科学用例的理论问题变得越来越紧迫。
在最近发表的《自然》论文中，来自谷歌量子AI以及斯坦福大学、麻省理工学院和加州理工学院的合作研究人员为这个问题带来了新的见解。我们介绍了一种高效的量子算法——称为解码量子干涉（DQI）——该算法利用量子力学的波动特性创建干涉模式，收敛到使用经典计算机极难找到的近最优解。
不过，这里有一个问题。要构建必要的干涉模式，必须解决另一个称为解码的困难计算问题。在解码问题中，给定一个格子和空间中的一个点，需要找到最接近该点的格子元素。例如，棋盘上方格的角点形成一个二维格子。在棋盘上随机位置撒下一粒沙子后，解码问题就是找到最近的角点。虽然这个问题在二维方形格子中很容易解决，但在数百或数千维的某些格子中可能变得非常困难。
幸运的是，在过去几十年中，解码问题得到了极其深入的研究，主要是由于在纠正数据存储或传输过程中产生的错误方面的应用。人们已经设计出许多复杂而强大的算法来解决各种特殊结构格子的解码问题。我们发现，对于某些类型的优化问题，相关的解码问题具有适合用这些强大解码算法解决的结构类型。然而，只有通过量子计算的力量，这些解码算法才能被利用来解决优化问题。通过将DQI的量子干涉与这些复杂的解码算法相结合，足够大的量子计算机可以找到这些优化问题的近似解——这些解似乎超出了任何已知经典方法的范围。
这一为优化提供加速的量子算法的数学发现提高了我们对量子计算机最终用例的理解。当量子计算硬件足够先进时，研究人员可以使用DQI算法来解决具有经典挑战性的优化问题。
在这项工作中，我们的最佳结果是针对一个称为最优多项式交集（OPI）的问题。在OPI问题中，给定一个目标点列表，希望通过调整次数低于点数的多项式系数来交集尽可能多的点。这是数据科学中称为多项式回归的常见任务。这个问题的变体在数字纠错和密码学背景下都有出现。因此，人们已经开发出复杂的算法来在某些特殊情况下解决它，但对于其他情况，使用传统经典计算机的已知算法解决这个问题仍然极其困难。
使用DQI，量子计算机可以将此转换为解码里德-所罗门码（在DVD和二维码中广泛使用的代码系列）的问题。人们已经开发出非常好的算法来解码里德-所罗门码，因此，使用DQI的量子计算机可以找到比经典计算机上已知算法更好的OPI问题近似最优解。例如，我们的分析表明，某些OPI问题的例子可以被量子计算机使用仅约几百万次基本量子逻辑操作来解决，而在传统经典计算机上使用最高效的已知经典算法需要超过10的23次方（一千万亿亿）次基本操作才能解决。
退一步来看，我们可以问为什么将优化问题转换为解码问题会有优势？通过更深入地理解这一点，人们可以希望获得直觉来指导寻找量子计算机可能提供优势的其他优化问题。
我们开始的优化问题和我们将其转换的解码问题都是称为NP困难问题的东西。这表明，即使在量子计算机的帮助下，也不可能高效地找到这些问题所有实例的精确解。通过使用量子效应，DQI将一个困难问题转换为另一个困难问题。这如何实现任何目标？关键在于NP困难性涉及给定问题最困难实例的难度。如果问题实例被限制具有一些额外结构，这可以使它们更容易。DQI的承诺是，某些类型的结构可能使解码问题更容易，而不会同时使用传统计算机解决优化问题更容易。
在OPI问题中，产生的格子具有代数结构；基向量的分量不是任意的，而是通过将一个数提升到连续更高次幂获得的。这种代数结构反映在原始优化问题（OPI）和量子计算机可以将其转换的解码问题（里德-所罗门解码）中。这种结构使解码问题变得更容易，但据我们所知，并不会使传统计算机的优化问题更容易。在这种情况下，使用量子计算的力量将优化问题转换为解码问题的能力提供了优势。
在论文中，我们还考虑了缺乏代数结构但基向量稀疏（即主要由零组成）的更通用格子。相应的优化问题称为max-k-XORSAT。格子的稀疏性反映在每个约束只涉及少数变量（最多k个）这一事实中。在max-k-XORSAT中，约束比变量多，不可能满足所有约束。相反，人们希望找到满足尽可能多约束的解决方案。虽然听起来很抽象，但max-k-XORSAT问题通常用作新优化算法的测试平台，并包括许多其他著名的优化问题作为特殊情况，如max-cut和QUBO。
DQI可以将max-k-XORSAT转换为由稀疏矩阵定义的代码的解码问题。这样的代码称为低密度奇偶校验（LDPC）代码。在1960年代发现稀疏性使解码问题变得更容易。然而，原始max-k-XORSAT问题的稀疏性也使其在传统计算机上使用称为模拟退火的算法更容易解决。因此，很难找到具有恰当稀疏性的max-k-XORSAT问题，使解码器比我们比较的模拟退火算法受益更多。在论文中，我们提出了一个例子问题，其中稀疏性恰到好处，使DQI似乎比模拟退火具有速度优势。然而，我们设法使用专门为我们的例子量身定制的专用算法在传统计算机上高效地解决了这个问题。因此，目前，与OPI不同，我们没有既可以被DQI解决又无法被在传统计算机上运行的任何已知算法高效解决的max-k-XORSAT问题的例子。
由于稀疏优化问题具有广泛的实际应用，我们继续寻找DQI可能在稀疏优化问题上实现量子优势的方法。特别是，DQI激发了对解码LDPC代码的经典和量子算法的新研究方向。
DQI算法为开发量子优化算法提供了强大的新工具包。这种将优化问题转换为解码问题的方法为解决该领域最长期存在的问题之一提供了新途径。我们很兴奋地看到研究人员，无论是在谷歌还是在更广泛的社区中，将用这些工具构建什么。
Q&A
Q1：什么是解码量子干涉算法？它有什么特殊之处？
A：解码量子干涉（DQI）是由谷歌量子AI开发的一种高效量子算法，它利用量子力学的波动特性创建干涉模式，能够找到经典计算机极难找到的近最优解。该算法的特殊之处在于能将优化问题转换为解码问题，从而利用已有的强大解码算法来解决优化难题。
Q2：最优多项式交集问题为什么适合用量子计算机解决？
A：最优多项式交集问题具有代数结构，其格子的基向量分量通过将数字提升到连续更高次幂获得。这种结构使得对应的解码问题（里德-所罗门解码）变得更容易，但不会使原始优化问题在经典计算机上更容易解决，因此量子计算机能够获得优势。
Q3：DQI算法在实际应用中有什么限制？
A：DQI算法需要解决解码问题来构建干涉模式，这本身也是一个困难的计算问题。此外，该算法需要大规模的容错量子计算机才能实现，目前的量子硬件还无法支持。对于某些问题如稀疏优化问题，找到量子优势仍然是个挑战。
