量子計(jì)算機(jī)優(yōu)勢(shì)的第一個(gè)證明

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

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

然而，在量子計(jì)算機(jī)中，一個(gè)位可以同時(shí)為0和1。這是因?yàn)榱孔游锢矶稍试S電子一次占據(jù)多個(gè)狀態(tài)。因此，量子比特或量子比特存在于多個(gè)重疊狀態(tài)中。這種所謂的疊加允許量子計(jì)算機(jī)一次性對(duì)許多值執(zhí)行操作，而單個(gè)傳統(tǒng)計(jì)算機(jī)必須順序執(zhí)行這些操作。量子計(jì)算的前景在于能夠更快地解決某些問題。

從猜想到證明

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

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

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