New Algorithm Closes Quantum Supremacy Window新算法关闭了量子霸权窗口

UP：用ChatGPT翻译

Random circuit sampling, a popular technique for showing the power of quantum computers, doesn’t scale up if errors go unchecked.

随机电路采样是展示量子计算机能力的一种流行技术，但如果错误未得到检查，它将无法扩展。

In random circuit sampling, researchers take quantum bits and randomly manipulate them. A new paper explores how errors in quantum computers can multiply to thwart these efforts.

在随机电路采样中，研究人员对量子比特进行随机操作。一篇新论文探讨了量子计算机中的错误如何会相互作用，从而阻碍这些尝试。

In what specific cases do quantum computers surpass their classical counterparts? That’s a hard question to answer, in part because today’s quantum computers are finicky things, plagued with errors that can pile up and spoil their calculations.

量子计算机在哪些具体情况下能够超越经典计算机？这是一个很难回答的问题，部分原因在于如今的量子计算机是非常棘手的东西，会遭受错误的困扰，这些错误会不断累积并破坏它们的计算。

By one measure, of course, they’ve already done it. In 2019, physicists at Google announced that they used a 53-qubit machine to achieve quantum supremacy, a symbolic milestone marking the point at which a quantum computer does something beyond the reach of any practical classical algorithm. Similar demonstrations by physicists at the University of Science and Technology of China soon followed.

从某个角度来看，他们已经做到了。2019年，谷歌的物理学家宣布他们使用一台53量子比特的机器实现了量子霸权，这是一个象征性的里程碑，标志着量子计算机做到了超越任何实用经典算法的事情。随后，中国科学技术大学的物理学家也进行了类似的演示。

But rather than focus on an experimental result for one particular machine, computer scientists want to know whether classical algorithms will be able to keep up as quantum computers get bigger and bigger. “The hope is that eventually the quantum side just completely pulls away until there’s no competition anymore,” said Scott Aaronson, a computer scientist at the University of Texas, Austin.

但计算机科学家关注的不是单个机器的实验结果，而是想知道随着量子计算机越来越大，经典算法是否能够跟得上。“希望是，最终量子计算机的优势会变得越来越明显，直到没有竞争对手了，”得克萨斯大学奥斯汀分校的计算机科学家斯科特·亚伦森（Scott Aaronson）说道。

That general question is still hard to answer, again in part because of those pesky errors. (Future quantum machines will compensate for their imperfections using a technique called quantum error correction, but that capability is still a ways off.) Is it possible to get the hoped-for runaway quantum advantage even with uncorrected errors?

这个一般性问题仍然很难回答，部分原因在于那些讨厌的错误。（未来的量子计算机将使用一种称为量子纠错的技术来补偿它们的不完美之处，但这种能力还有一段路要走。）即使没有进行纠错，是否仍有可能获得期望的疯狂的量子优势呢？

Most researchers suspected the answer was no, but they couldn’t prove it for all cases. Now, in a paper posted to the preprint server arxiv.org, a team of computer scientists has taken a major step toward a comprehensive proof that error correction is necessary for a lasting quantum advantage in random circuit sampling — the bespoke problem that Google used to show quantum supremacy. They did so by developing a classical algorithm that can simulate random circuit sampling experiments when errors are present.

大多数研究人员认为答案是否定的，但他们无法证明对于所有情况都是这样。现在，在一篇发布在预印本服务器arxiv.org上的论文中，一组计算机科学家朝着全面证明量子纠错对于在随机电路采样中获得持久的量子优势是必要的迈出了重要的一步。随机电路采样是谷歌用来展示量子霸权的特定问题。他们通过开发一种经典算法，在存在错误的情况下可以模拟随机电路采样实验来实现这一点。

 “It’s a beautiful theoretical result,” Aaronson said, while stressing that the new algorithm is not practically useful for simulating real experiments like Google’s.

“这是一个美妙的理论结果，”亚伦森说道，同时强调新算法不适用于模拟像谷歌这样的真实实验。

In random circuit sampling experiments, researchers start with an array of qubits, or quantum bits. They then randomly manipulate these qubits with operations called quantum gates. Some gates cause pairs of qubits to become entangled, meaning they share a quantum state and can’t be described separately. Repeated layers of gates bring the qubits into a more complicated entangled state.

在随机电路采样实验中，研究人员从一组量子比特开始。然后，他们使用称为量子门的操作随机操作这些量子比特。有些门会导致一对量子比特纠缠，这意味着它们共享一个量子态，并且不能单独描述。门的重复层使量子比特带入更复杂的纠缠态中。

To learn about that quantum state, researchers then measure all the qubits in the array. This causes their collective quantum state to collapse to a random string of ordinary bits — 0s and 1s. The number of possible outcomes grows rapidly with the number of qubits in the array: With 53 qubits, as in Google’s experiment, it’s nearly 10 quadrillion. And not all strings are equally likely. Sampling from a random circuit means repeating such measurements many times to build up a picture of the probability distribution underlying the outcomes.

为了了解这种量子态，研究人员然后测量数组中的所有量子比特。这将导致它们的集体量子态崩塌为一个普通比特的随机字符串——0和1。可能的结果数量随着数组中量子比特数量的增加而迅速增长：对于谷歌实验的53个量子比特，近似达到了10的15次方。并且，并不是所有的字符串出现的概率都是相等的。从一个随机电路中进行采样意味着多次重复这样的测量，以建立结果概率分布的图像。

The question of quantum advantage is simply this: Is it hard to mimic that probability distribution with a classical algorithm that doesn’t use any entanglement?

量子优势的问题很简单：使用不使用任何纠缠的经典算法模仿该概率分布是否很困难？

In 2019, researchers proved that the answer is yes for error-free quantum circuits: It is indeed hard to classically simulate a random circuit sampling experiment when there are no errors. The researchers worked within the framework of computational complexity theory, which classifies the relative difficulty of different problems. In this field, researchers don’t treat the number of qubits as a fixed number such as 53. “Think of it as n, which is some number that’s going to increase,” said Aram Harrow, a physicist at the Massachusetts Institute of Technology. “Then you want to ask: Are we doing things where the effort is exponential in n or polynomial in n?” This is the preferred way to classify an algorithm’s runtime — when n grows large enough, an algorithm that’s exponential in n lags far behind any algorithm that’s polynomial in n. When theorists speak of a problem that’s hard for classical computers but easy for quantum computers, they’re referring to this distinction: The best classical algorithm takes exponential time, while a quantum computer can solve the problem in polynomial time.

2019年，研究人员证明，对于没有错误的量子电路，答案是肯定的：当没有错误时，经典模拟随机电路采样实验确实很困难。这些研究人员在计算复杂性理论框架内工作，该理论对不同问题的相对难度进行分类。在这个领域，研究人员不将量子比特的数量视为一个固定的数字，例如53。麻省理工学院的物理学家Aram Harrow说：“把它看作是n，n是一个将要增加的数字。”“然后你想问：我们是否在做的事情中，所需的工作量是n的指数或n的多项式？”这是分类算法运行时间的首选方法 - 当n足够大时，指数级别的算法远远落后于多项式级别的算法。当理论家谈论对经典计算机而言很难但对量子计算机很容易的问题时，他们指的是这个区别：最好的经典算法需要指数时间，而量子计算机可以在多项式时间内解决该问题。

Yet that 2019 paper ignored the effects of errors caused by imperfect gates. This left open the case of a quantum advantage for random circuit sampling without error correction.

然而，这篇2019年的论文忽略了由不完美的门引起的误差的影响。这留下了在没有纠错的情况下，随机电路采样的量子优势的可能性。

If you imagine continually increasing the number of qubits as complexity theorists do, and you also want to account for errors, you need to decide whether you’re also going to keep adding more layers of gates — increasing the circuit depth, as researchers say. Suppose you keep the circuit depth constant at, say, a relatively shallow three layers, as you increase the number of qubits. You won’t get much entanglement, and the output will still be amenable to classical simulation. On the other hand, if you increase the circuit depth to keep up with the growing number of qubits, the cumulative effects of gate errors will wash out the entanglement, and the output will again become easy to simulate classically.

如果你像复杂性理论学者那样想象不断增加量子比特的数量，并且还想考虑误差的影响，你需要决定是否继续添加更多的量子门层——增加电路深度，正如研究人员所说的那样。假设你保持电路深度恒定，比如相对较浅的三层，当你增加量子比特的数量时，你不会得到太多的纠缠，输出仍然可以被经典模拟。另一方面，如果你增加电路深度来跟上不断增长的量子比特数量，量子门误差的累积效应将会冲淡纠缠，输出将再次变得容易被经典模拟。

But in between lies a Goldilocks zone. Before the new paper, it was still a possibility that quantum advantage could survive here, even as the number of qubits increased. In this intermediate-depth case, you increase the circuit depth extremely slowly as the number of qubits grows: Even though the output will steadily get degraded by errors, it might still be hard to simulate classically at each step.

但是在中间存在一个适当的深度区间。在这篇新论文之前，即使在量子比特数量增加时，量子优势在这里仍然有可能存在。在这种中间深度的情况下，您需要极慢地增加电路深度，以便随着量子比特数量的增长。即使输出结果不断受到错误的影响，但在每一步中仍然很难在经典计算机上模拟。

The new paper closes this loophole. The authors derived a classical algorithm for simulating random circuit sampling and proved that its runtime is a polynomial function of the time required to run the corresponding quantum experiment. The result forges a tight theoretical connection between the speed of classical and quantum approaches to random circuit sampling.

新论文填补了这一漏洞。作者们推导出了一个经典算法，用于模拟随机电路采样，并证明其运行时间是运行相应量子实验所需时间的一个多项式函数。这个结果建立了经典和量子方法在随机电路采样上速度之间的紧密理论联系。

The new algorithm works for a major class of intermediate-depth circuits, but its underlying assumptions break down for certain shallower ones, leaving a small gap where efficient classical simulation methods are unknown. But few researchers are holding out hope that random circuit sampling will prove hard to simulate classically in this remaining slim window. “I give it pretty small odds,” said Bill Fefferman, a computer scientist at the University of Chicago and one of the authors of the 2019 theory paper.

新算法适用于一类重要的中等深度电路，但其基本假设对某些更浅的电路不成立，留下了一个小的空缺，其中有效的经典模拟方法是未知的。但是很少有研究人员抱有希望，认为随机电路采样在这个狭窄的窗口内会被证明难以在经典计算机上模拟。 "我觉得它的机会相当小，" Bill Fefferman说，他是芝加哥大学的计算机科学家，也是2019年理论论文的作者之一。

The result suggests that random circuit sampling won’t yield a quantum advantage by the rigorous standards of computational complexity theory. At the same time, it illustrates the fact that polynomial algorithms, which complexity theorists indiscriminately call efficient, aren’t necessarily fast in practice. The new classical algorithm gets progressively slower as the error rate decreases, and at the low error rates achieved in quantum supremacy experiments, it’s far too slow to be practical. With no errors it breaks down altogether, so this result doesn’t contradict anything researchers knew about how hard it is to classically simulate random circuit sampling in the ideal, error-free case. Sergio Boixo, the physicist leading Google’s quantum supremacy research, says he regards the paper “more as a nice confirmation of random circuit sampling than anything else.”

结果表明，按照计算复杂性理论的严格标准，随机电路采样不会产生量子优势。与此同时，它说明了复杂性理论家不加区分地称之为高效的多项式算法并不一定在实践中快速。新的经典算法随着误差率的降低而变得越来越慢，在量子霸权实验中实现的低误差率下，它太慢了，不切实际。在没有误差的情况下，它完全崩溃，因此这个结果并不违背研究人员关于理想情况下难以经典模拟随机电路采样的已知结论。谷歌量子霸权研究的物理学家Sergio Boixo表示，他认为这篇论文“更像是对随机电路采样的一个好的证实，而不是其他什么东西”。

On one point, all researchers agree: The new algorithm underscores how crucial quantum error correction will be to the long-term success of quantum computing. “That’s the solution, at the end of the day,” Fefferman said.

所有的研究人员都同意一个观点：新算法强调了量子纠错对于量子计算长期成功的关键性。Fefferman说，“这是最终的解决方案。”