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說，“這是最終的解決方案。”

關鍵詞：