人們預期量子計算機在求解特定估算問題的時侯其性能比精典計算機更高。這些預期基于估算復雜度理論中一個有充分依據的猜測，但嚴謹地把量子算法和精典算法進行對比是很難實現的。等人在理論上證明了，并行量子電路求解特定線性代數問題時須要的估算步驟和問題規模無關，而類似的精典電路須要的估算步數隨著問題規模的下降而對數式降低。這就是所謂的量子優勢，緣于量子電路中存在的量子關聯，這在精典電路中是難以被再現的。
論文：with
論文地址：
arXiv地址：
多年來，量子計算機不僅僅是一個看法，人們還在因此付諸行動?，F在，企業、政府和情報機構都在投資發展量子技術。如今，TUM復雜量子系統理論研究院院長K?nig，與滑鐵盧學院量子估算研究所的David以及來自IBM的合作，早已為這個飽含希望的領域奠定了基石。
傳統計算機遵守精典化學定理。它們依賴二補碼數0和1。這種數字被存儲并用于物理運算。在傳統的存儲單元中，每位比特（信息的最小單位）都由一個電位來表示，該電位決定該比特設置為1還是0。
但在量子計算機中，一個比特（量子比特）可以同時為0和1。由于量子化學定理容許電子一次搶占多個狀態。為此，量子比特（qubit）以多個重疊狀態存在。這些所謂的疊加容許量子計算機一次對多個值執行操作，而單個傳統計算機必須次序執行這種操作。量子估算的前景在于能否更快速地解決個別問題。
從推測到證明
K?nig和他的朋友決定性地證明了量子計算機的優勢。因此，她們開發了一種可以求解一類非常困難的代數問題的量子電路。新的電路有很簡單的結構：它僅在每位量子比特上執行固定數目的運算。這樣的電路被叫做擁有固定的深度。在她們的研究中，研究者證明了這個問題不能用固定深度的經典電路求解。她們還進一步回答了量子算法趕超所有精典電路的緣由：量子算法借助了量子化學的非局域性。
在本研究之前，量子計算機的優勢既沒有得到證明，也沒辦法用實驗方式進行展示，雖然有證據指向這個可能。一個實例是Shor的量子算法關于量子物理的論文，該算法有效解決了大數素因子分解問題。但是，這僅僅是一個復雜的理論推測，沒有量子計算機，這個問題就難以有效解決。也可以理解為高效的方式是存在的，只是精典計算機還沒找到。
K?nig覺得，新的結果主要是對復雜理論的貢獻。他表示，「我們的結果表明，量子信息處理的確有好多優點——不必依賴于未證明的復雜理論猜測?！钩酥?strong>關于量子物理的論文，該研究為量子計算機研究樹立了新的里程碑。因為結構簡單，這一新的量子電路可以作為量子算法近日實驗實現的備選對象。
參考內容：