UP：用ChatGPT翻譯

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

隨機(jī)電路采樣是展示量子計(jì)算機(jī)能力的一種流行技術(shù)，但如果錯(cuò)誤未得到檢查，它將無(wú)法擴(kuò)展。

(相關(guān)資料圖)

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.

在隨機(jī)電路采樣中，研究人員對(duì)量子比特進(jìn)行隨機(jī)操作。一篇新論文探討了量子計(jì)算機(jī)中的錯(cuò)誤如何會(huì)相互作用，從而阻礙這些嘗試。

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.

量子計(jì)算機(jī)在哪些具體情況下能夠超越經(jīng)典計(jì)算機(jī)？這是一個(gè)很難回答的問(wèn)題，部分原因在于如今的量子計(jì)算機(jī)是非常棘手的東西，會(huì)遭受錯(cuò)誤的困擾，這些錯(cuò)誤會(huì)不斷累積并破壞它們的計(jì)算。

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.

從某個(gè)角度來(lái)看，他們已經(jīng)做到了。2019年，谷歌的物理學(xué)家宣布他們使用一臺(tái)53量子比特的機(jī)器實(shí)現(xiàn)了量子霸權(quán)，這是一個(gè)象征性的里程碑，標(biāo)志著量子計(jì)算機(jī)做到了超越任何實(shí)用經(jīng)典算法的事情。隨后，中國(guó)科學(xué)技術(shù)大學(xué)的物理學(xué)家也進(jìn)行了類(lèi)似的演示。

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.

但計(jì)算機(jī)科學(xué)家關(guān)注的不是單個(gè)機(jī)器的實(shí)驗(yàn)結(jié)果，而是想知道隨著量子計(jì)算機(jī)越來(lái)越大，經(jīng)典算法是否能夠跟得上?！跋Ｍ牵罱K量子計(jì)算機(jī)的優(yōu)勢(shì)會(huì)變得越來(lái)越明顯，直到?jīng)]有競(jìng)爭(zhēng)對(duì)手了，”得克薩斯大學(xué)奧斯汀分校的計(jì)算機(jī)科學(xué)家斯科特·亞倫森（Scott Aaronson）說(shuō)道。

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?

這個(gè)一般性問(wèn)題仍然很難回答，部分原因在于那些討厭的錯(cuò)誤。（未來(lái)的量子計(jì)算機(jī)將使用一種稱為量子糾錯(cuò)的技術(shù)來(lái)補(bǔ)償它們的不完美之處，但這種能力還有一段路要走。）即使沒(méi)有進(jìn)行糾錯(cuò)，是否仍有可能獲得期望的瘋狂的量子優(yōu)勢(shì)呢？

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.

大多數(shù)研究人員認(rèn)為答案是否定的，但他們無(wú)法證明對(duì)于所有情況都是這樣?，F(xiàn)在，在一篇發(fā)布在預(yù)印本服務(wù)器arxiv.org上的論文中，一組計(jì)算機(jī)科學(xué)家朝著全面證明量子糾錯(cuò)對(duì)于在隨機(jī)電路采樣中獲得持久的量子優(yōu)勢(shì)是必要的邁出了重要的一步。隨機(jī)電路采樣是谷歌用來(lái)展示量子霸權(quán)的特定問(wèn)題。他們通過(guò)開(kāi)發(fā)一種經(jīng)典算法，在存在錯(cuò)誤的情況下可以模擬隨機(jī)電路采樣實(shí)驗(yàn)來(lái)實(shí)現(xiàn)這一點(diǎn)。

“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.

“這是一個(gè)美妙的理論結(jié)果，”亞倫森說(shuō)道，同時(shí)強(qiáng)調(diào)新算法不適用于模擬像谷歌這樣的真實(shí)實(shí)驗(yàn)。

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.

在隨機(jī)電路采樣實(shí)驗(yàn)中，研究人員從一組量子比特開(kāi)始。然后，他們使用稱為量子門(mén)的操作隨機(jī)操作這些量子比特。有些門(mén)會(huì)導(dǎo)致一對(duì)量子比特糾纏，這意味著它們共享一個(gè)量子態(tài)，并且不能單獨(dú)描述。門(mén)的重復(fù)層使量子比特帶入更復(fù)雜的糾纏態(tài)中。

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.

為了了解這種量子態(tài)，研究人員然后測(cè)量數(shù)組中的所有量子比特。這將導(dǎo)致它們的集體量子態(tài)崩塌為一個(gè)普通比特的隨機(jī)字符串——0和1。可能的結(jié)果數(shù)量隨著數(shù)組中量子比特?cái)?shù)量的增加而迅速增長(zhǎng)：對(duì)于谷歌實(shí)驗(yàn)的53個(gè)量子比特，近似達(dá)到了10的15次方。并且，并不是所有的字符串出現(xiàn)的概率都是相等的。從一個(gè)隨機(jī)電路中進(jìn)行采樣意味著多次重復(fù)這樣的測(cè)量，以建立結(jié)果概率分布的圖像。

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?

量子優(yōu)勢(shì)的問(wèn)題很簡(jiǎn)單：使用不使用任何糾纏的經(jīng)典算法模仿該概率分布是否很困難？

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年，研究人員證明，對(duì)于沒(méi)有錯(cuò)誤的量子電路，答案是肯定的：當(dāng)沒(méi)有錯(cuò)誤時(shí)，經(jīng)典模擬隨機(jī)電路采樣實(shí)驗(yàn)確實(shí)很困難。這些研究人員在計(jì)算復(fù)雜性理論框架內(nèi)工作，該理論對(duì)不同問(wèn)題的相對(duì)難度進(jìn)行分類(lèi)。在這個(gè)領(lǐng)域，研究人員不將量子比特的數(shù)量視為一個(gè)固定的數(shù)字，例如53。麻省理工學(xué)院的物理學(xué)家Aram Harrow說(shuō)：“把它看作是n，n是一個(gè)將要增加的數(shù)字?！薄叭缓竽阆雴?wèn)：我們是否在做的事情中，所需的工作量是n的指數(shù)或n的多項(xiàng)式？”這是分類(lèi)算法運(yùn)行時(shí)間的首選方法 - 當(dāng)n足夠大時(shí)，指數(shù)級(jí)別的算法遠(yuǎn)遠(yuǎn)落后于多項(xiàng)式級(jí)別的算法。當(dāng)理論家談?wù)搶?duì)經(jīng)典計(jì)算機(jī)而言很難但對(duì)量子計(jì)算機(jī)很容易的問(wèn)題時(shí)，他們指的是這個(gè)區(qū)別：最好的經(jīng)典算法需要指數(shù)時(shí)間，而量子計(jì)算機(jī)可以在多項(xiàng)式時(shí)間內(nèi)解決該問(wè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年的論文忽略了由不完美的門(mén)引起的誤差的影響。這留下了在沒(méi)有糾錯(cuò)的情況下，隨機(jī)電路采樣的量子優(yōu)勢(shì)的可能性。

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.

如果你像復(fù)雜性理論學(xué)者那樣想象不斷增加量子比特的數(shù)量，并且還想考慮誤差的影響，你需要決定是否繼續(xù)添加更多的量子門(mén)層——增加電路深度，正如研究人員所說(shuō)的那樣。假設(shè)你保持電路深度恒定，比如相對(duì)較淺的三層，當(dāng)你增加量子比特的數(shù)量時(shí)，你不會(huì)得到太多的糾纏，輸出仍然可以被經(jīng)典模擬。另一方面，如果你增加電路深度來(lái)跟上不斷增長(zhǎng)的量子比特?cái)?shù)量，量子門(mén)誤差的累積效應(yīng)將會(huì)沖淡糾纏，輸出將再次變得容易被經(jīng)典模擬。

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.

但是在中間存在一個(gè)適當(dāng)?shù)纳疃葏^(qū)間。在這篇新論文之前，即使在量子比特?cái)?shù)量增加時(shí)，量子優(yōu)勢(shì)在這里仍然有可能存在。在這種中間深度的情況下，您需要極慢地增加電路深度，以便隨著量子比特?cái)?shù)量的增長(zhǎng)。即使輸出結(jié)果不斷受到錯(cuò)誤的影響，但在每一步中仍然很難在經(jīng)典計(jì)算機(jī)上模擬。

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.

新論文填補(bǔ)了這一漏洞。作者們推導(dǎo)出了一個(gè)經(jīng)典算法，用于模擬隨機(jī)電路采樣，并證明其運(yùn)行時(shí)間是運(yùn)行相應(yīng)量子實(shí)驗(yàn)所需時(shí)間的一個(gè)多項(xiàng)式函數(shù)。這個(gè)結(jié)果建立了經(jīng)典和量子方法在隨機(jī)電路采樣上速度之間的緊密理論聯(lián)系。

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.

新算法適用于一類(lèi)重要的中等深度電路，但其基本假設(shè)對(duì)某些更淺的電路不成立，留下了一個(gè)小的空缺，其中有效的經(jīng)典模擬方法是未知的。但是很少有研究人員抱有希望，認(rèn)為隨機(jī)電路采樣在這個(gè)狹窄的窗口內(nèi)會(huì)被證明難以在經(jīng)典計(jì)算機(jī)上模擬。 "我覺(jué)得它的機(jī)會(huì)相當(dāng)小，" Bill Fefferman說(shuō)，他是芝加哥大學(xué)的計(jì)算機(jī)科學(xué)家，也是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.”

結(jié)果表明，按照計(jì)算復(fù)雜性理論的嚴(yán)格標(biāo)準(zhǔn)，隨機(jī)電路采樣不會(huì)產(chǎn)生量子優(yōu)勢(shì)。與此同時(shí)，它說(shuō)明了復(fù)雜性理論家不加區(qū)分地稱之為高效的多項(xiàng)式算法并不一定在實(shí)踐中快速。新的經(jīng)典算法隨著誤差率的降低而變得越來(lái)越慢，在量子霸權(quán)實(shí)驗(yàn)中實(shí)現(xiàn)的低誤差率下，它太慢了，不切實(shí)際。在沒(méi)有誤差的情況下，它完全崩潰，因此這個(gè)結(jié)果并不違背研究人員關(guān)于理想情況下難以經(jīng)典模擬隨機(jī)電路采樣的已知結(jié)論。谷歌量子霸權(quán)研究的物理學(xué)家Sergio Boixo表示，他認(rèn)為這篇論文“更像是對(duì)隨機(jī)電路采樣的一個(gè)好的證實(shí)，而不是其他什么東西”。

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.

所有的研究人員都同意一個(gè)觀點(diǎn)：新算法強(qiáng)調(diào)了量子糾錯(cuò)對(duì)于量子計(jì)算長(zhǎng)期成功的關(guān)鍵性。Fefferman說(shuō)，“這是最終的解決方案。”

關(guān)鍵詞：