量子計算機優(yōu)勢的第一個證明

多年來，量子計算機并不僅僅是一個想法。今天，公司，政府和情報機構(gòu)正在投資開發(fā)量子技術(shù)。TUM復(fù)雜量子系統(tǒng)理論教授RobertKönig與滑鐵盧大學(xué)量子計算研究所的David Gosset和IBM的Sergey Bravyi合作，現(xiàn)在已經(jīng)在這個充滿希望的領(lǐng)域奠定了基石。

傳統(tǒng)的計算機遵守經(jīng)典物理學(xué)的規(guī)律。它們依賴于零和一的二進(jìn)制數(shù)。這些數(shù)字被存儲并用于數(shù)學(xué)運算。在傳統(tǒng)的存儲器單元中，每個比特 - 最小的信息單元 - 由確定該比特是設(shè)置為1還是0的電荷表示。

然而，在量子計算機中，一個位可以同時為0和1。這是因為量子物理定律允許電子一次占據(jù)多個狀態(tài)。因此，量子比特或量子比特存在于多個重疊狀態(tài)中。這種所謂的疊加允許量子計算機一次性對許多值執(zhí)行操作，而單個傳統(tǒng)計算機必須順序執(zhí)行這些操作。量子計算的前景在于能夠更快地解決某些問題。

從猜想到證明

König和他的同事現(xiàn)在已經(jīng)最終證明了量子計算機的優(yōu)勢。為此，他們開發(fā)了一種能夠解決特定困難代數(shù)問題的量子電路。新電路結(jié)構(gòu)簡單 - 它只對每個量子位執(zhí)行固定數(shù)量的操作。這種電路被稱為具有恒定的深度。在他們的工作中，研究人員證明使用經(jīng)典的恒定深度電路無法解決手頭的問題。他們進(jìn)一步回答了為什么量子算法勝過任何可比較的經(jīng)典電路的問題：量子算法利用了量子物理學(xué)的非局域性。

在這項工作之前，量子計算機的優(yōu)勢既沒有得到證實也沒有經(jīng)過實驗證明 - 盡管有證據(jù)指向了這個方向。一個例子是Shor的量子算法，它有效地解決了素因子分解的問題。然而，如果沒有量子計算機，這個問題就不能有效地解決，這只是一個復(fù)雜性理論的猜想。也可以想象，對于經(jīng)典計算機來說，還沒有找到正確的方法。

RobertKönig認(rèn)為新結(jié)果主要是對復(fù)雜性理論的貢獻(xiàn)。“我們的結(jié)果表明量子信息處理確實提供了好處 - 而不必依賴未經(jīng)證實的復(fù)雜性理論猜想，”他說。除此之外，這項工作為量子計算機之路提供了新的里程碑。由于其結(jié)構(gòu)簡單，新的量子電路是量子算法的近期實驗實現(xiàn)的候選者。