近日，來自 TMU、滑鐵盧大學和 IBM 的研究者在 Science 上發表論文，首次證明了量子算法可以在特定代數問題上擁有相對於經典算法的理論優勢，而在此之前，這還只是個猜想。
Science 評論道：
人們預期量子計算機在求解特定計算問題的時候其性能比經典計算機更高。這種預期基於計算複雜度理論中一個有充分根據的猜想，但嚴謹地把量子算法和經典算法進行對比是很難實現的。Bravyi 等人在理論上證明了，並行量子電路求解特定線性代數問題時需要的計算步驟和問題規模無關，而類似的經典電路需要的計算步數隨着問題規模的增長而指數級增加。這就是所謂的量子優勢，源於量子電路中存在的量子關聯，這在經典電路中是無法被重現的。
論文：Quantum advantage with shallow circuits
論文地址：http://science.sciencemag.org/content/362/6412/308
arXiv 地址：https://arxiv.org/pdf/1704.00690.pdf
多年來，量子計算機不僅僅是一個想法，人們還在爲此付諸行動。如今，企業、政府和情報機構都在投資發展量子技術。現在，TUM 複雜量子系統理論研究院教授 Robert König，與滑鐵盧大學量子計算研究所的 David Gosset 以及來自 IBM 的 Sergey Bravyi 合作，已經爲這個充滿希望的領域奠定了基石。
傳統計算機遵循經典物理定律。它們依賴二進制數 0 和 1。這些數字被儲存並用於數學運算。在傳統的儲存單元中，每個比特（信息的最小單位）都由一個電位來表示，該電位決定該比特設置爲 1 還是 0。
但在量子計算機中，一個比特（量子比特）可以同時爲 0 和 1。因爲量子物理定律允許電子一次佔據多個狀態。因此，量子比特（qubit）以多個重疊狀態存在。這種所謂的疊加允許量子計算機一次對多個值執行操作，而單個傳統計算機必須順序執行這些操作。量子計算的前景在於能夠更快速地解決某些問題。
從猜想到證明
König 和他的同事決定性地證明了量子計算機的優勢。爲此，他們開發了一種可以求解一類特別困難的代數問題的量子電路。新的電路有很簡單的結構：它僅在每個量子比特上執行固定數量的運算。這樣的電路被稱作擁有固定的深度。在他們的研究中，研究者證明了這個問題不能用固定深度的經典電路求解。他們還進一步回答了量子算法超越所有經典電路的原因：量子算法利用了量子物理的非局域性。
在本研究之前，量子計算機的優勢既沒有得到證明，也沒辦法用實驗方法進行展示，儘管有證據指向這個可能。一個實例是 Shor 的量子算法，該算法有效解決了大數素因子分解問題。然而，這僅僅是一個複雜的理論猜想，沒有量子計算機，這個問題就無法有效解決。也可以理解爲高效的方法是存在的，只是經典計算機還沒找到。
Robert König 認爲，新的結果主要是對複雜理論的貢獻。他表示，「我們的結果表明，量子信息處理的確有很多優點——不必依賴於未證明的複雜理論猜想。」除此之外，該研究爲量子計算機研究樹立了新的里程碑。由於結構簡單，這一新的量子電路可以作爲量子算法近期實驗實現的備選對象。
參考內容：https://phys.org/news/2018-10-proof-quantum-advantage.html