Evaluating QAOA expectation values can be as hard as counting optimal solutions

想象一个计算机不仅仅是在进行数值计算，而是在与概率共舞的世界。这就是量子计算的领域，它承诺解决那些如此错综复杂、以至于今天的超级计算机需要花费比宇宙年龄还要长的时间才能解开的问题。在这场舞蹈的核心，有一种被称为量子近似优化算法（QAOA）的流行舞步。可以将 QAOA 想象成一场高科技的寻宝游戏。你有一张地图（一个问题），上面有许多可能的路径，而你想找到那条能通向最多黄金（最佳解）的路径。量子计算机准备了一个特殊的“叠加”态——一种所有可能路径同时存在的神奇混合体——然后，通过一系列被称为“层”或“深度”的步骤，它试图倾斜概率，使得当你最终观察时，那条最佳路径能闪耀得最亮。

为了知道这场寻宝游戏是否进展顺利，科学家需要检查“期望值”。用通俗的话说，这就像是快速瞥一眼量子计算机的舞蹈，看看它离找到黄金还有多远，而无需实际停止舞蹈去清点每一枚金币。长期以来，研究人员知道如果舞蹈只有一个步骤（深度 $p=1$），检查这个分数很容易，就像阅读一份简单的食谱。但当舞蹈变得更加复杂，拥有两个或更多步骤时，情况又会如何呢？Wang 及其同事最近的一项研究表明，检查这些更深层次舞蹈的分数是极其困难的——难到几乎等同于解决原始的寻宝游戏本身。但它仅仅是和寻找一条好路径一样难，还是甚至更难？

Stuart Hadfield 撰写的这篇论文深入探讨了这个问题。作者证明了对于具有两层或更多层的 QAOA，检查分数不仅是寻找单个最佳解那么难，它甚至难到足以计算出所有存在的最佳解的总数。在计算机科学的世界里，寻找一个解是一个艰巨的挑战，但统计它们所有的数量则是另一种规模的“怪物”，通常被认为对于经典计算机来说更加不可逾越。Hadfield 展示了只要你在算法中加入第二层，这个“计数怪物”就会出现。这篇论文不仅仅是提出了这种可能性，它还提供了一个严密的数学证明，通过构建一种特定类型的题目图（problem graph），迫使任何试图计算 QAOA 分数的计算机本质上都在解决那个不可能完成的计数问题。这意味着，对于这些更深的量子算法，在最坏情况下，即便我们拥有一个完美的量子机器来运行这场舞蹈，检查其表现的这一行为本身，也可能在根本上超出了经典计算机的能力范围。

寻宝变得复杂了

让我们来拆解一下这个魔术技巧。QAOA 算法旨在解决“最大割”（MaxCut）问题。想象一群朋友正在参加派对，你想把他们分成两队（红队和蓝队）来玩游戏。目标是安排队伍，使得两队之间的“友谊”被打破的数量达到最大。这就是“最大割”。不同的安排效果不同，而且随着朋友人数的增加，寻找绝对最佳安排的过程会变得越来越难。

QAOA 算法试图通过旋转一枚量子硬币来找到这种最佳安排。它让每个人都处于叠加态（同时既是红色又是蓝色），然后应用一系列“扭转”（即层）。你添加的扭转越多，舞蹈就变得越精致。为了观察舞蹈是否奏效，科学家会计算一个“期望值”。你可以把它看作是一个“分数”，它告诉你在量子舞蹈中，平均有多少段友谊被打破了。

对于单次扭转（$p=1$），计算这个分数很容易。你可以在餐巾纸上写下来。但当你加入第二次扭转（$p=2$）时，事情变得诡异起来。之前的研究表明，计算这个分数是“NP-hard”的，意味着它与寻找单一最佳团队安排一样难。但 Hadfield 的论文说：“等等，它其实比那更糟。”

计数怪物

Hadfield 的主要发现是对我们理解难度的精准升级。他证明了对于 $p \ge 2$ 的 QAOA，计算分数不仅是“NP-hard”（寻找一个解），而是 #P-hard。

为了理解其中的区别，请想象你是一名侦探：

• NP-hard 就像是被问到：“你能找到一个犯下罪行的嫌疑人吗？”这很难，但如果你运气好或者足够努力，你可能会找到一个。
• #P-hard 就像是被问到：“总共有多少个嫌疑人犯下了罪行？”你必须找到每一个并统计它们的总数。

在计算机科学领域，统计数量通常被认为比仅仅寻找一个要难得多。Hadfield 表明，对于具有两层或更多层的 QAOA，计算分数所需的数学过程会迫使你去统计完美解的总数。

魔法小工具

他是如何证明这一点的呢？Hadfield 构建了一个聪明的“小工具”（gadget），就像是一个专门设计用来捕捉计算机的陷阱。他拿了一个标准的 MaxCut 问题，并在其周围构建了一个巨大的、复杂的图。这个图拥有特殊的“锚点”和“变量”块。

诀窍在于设计。当量子计算机在这个特定的图上运行其舞蹈时，最终的分数（期望值）会变成一个巨大的数学表达式，称为“劳伦特多项式”（Laurent polynomial）。这个表达式就像一串很长的项，每一项都有一个不同的变量幂次（例如 $z^1, z^2, z^3...$）。

Hadfield 展示了该字符串中的最高幂次（“极值系数”）隐藏着一个秘密。如果你能完美地计算出分数，你就能提取出这个最高幂次。而关键在于：那个特定数字的大小与原始问题的完美解总数直接成正比。

因此，如果你能轻松计算出这个图的 QAOA 分数，你就能瞬间得到“计数怪物”问题的答案。既然统计计数被认为对于经典计算机来说无法高效完成，那么计算 QAOA 分数也必然对它们而言是无法实现的。

“单条边”的惊喜

论文的内容甚至更加令人惊讶。你可能会想：“好吧，计算总分很难，但也许计算仅仅针对某一个特定友谊（单条边）的分数很容易呢？”

Hadfield 说：不。他证明了即使你只要求量子计算机告诉你两个特定人之间的相关性（一个“双量子比特相关器”，如 $\langle Z_r Z_s \rangle$），这个问题仍然是 #P-hard 的。难度不仅仅存在于宏观层面；它已经深深植入到了算法最微小的细节之中。

这对未来意味着什么

这篇论文划定了一条清晰的界限：

• 深度 $p=1$： 容易。我们可以高效地计算分数。
• 深度 $p \ge 2$： 困难。计算分数与统计所有最优解的总数一样难。

这具有重大的意义。许多现代算法使用 QAOA 来训练机器，通过调整“扭转”（参数）来获得更好的分数。如果计算分数如此困难，那么在经典计算机上训练这些算法（以观察量子机器的表现）对于深层电路来说可能是无法实现的。

作者还指出，这并不意味着量子计算机是无用的。事实上，这可能意味着它们更有用。如果经典计算机甚至无法检查分数，也许量子计算机是唯一的选择。然而，论文也警告说，这种“硬度”是一种最坏情况下的表现。这并不意味着每一个图都是无法解决的；它只是意味着存在一些特定的、棘手的图，使得经典计算机在处理这些图时的数学逻辑会崩溃。

总结

Stuart Hadfield 的论文是对量子界的一次警示。它告诉我们，当我们通过增加层数来增强 QAOA 的功能时，我们不仅仅是在让问题变得更难解决，我们还在让检查工作的过程变得指数级困难。我们已经从一个可以轻松验证量子舞蹈的世界，进入了一个验证舞蹈需要解决一个可能属于计算机科学中最难之“计数谜题”的世界。它提醒我们，在量子领域，你钻研得越深，数学就会变得越神秘。