- 科技報導
文章專區
2020-04-10量子霸權盡失？俄羅斯科學家破解Google量子演算法
460 期
Author 作者
編輯部
【本刊訊】俄羅斯斯科爾克沃科學與科技研究院（Skolkovo Institute of Science and Technology, Skoltech）科學家，日前發現Google廣泛採用的量子方法有基本侷限性（fundamental limitation），並把這個限制做量化。研究發表於《物理評論通訊》（Physical Review Letters）中。
當前計算機技術，真如Google所說已達到量子霸權（quantum supremacy）的境界了嗎？曾被視為證明「量子至上」的希望──量子近似優化演算法（quantum approximate optimization algorithm, QAOA），真實情況又是如何？
Google長年致力開發量子增強型處理器（quantum-enhanced processors），它能利用量子力學效應（quantum mechanical effects）提升數據的處理速度，為此Google也計畫在短期內設計出可在真實噪聲（noise）下運行的量子增強演算法，其中，QAOA正是開發抗噪聲量子增強算法的基礎。雖說Google在QAOA中採用的方法引起廣大關注，也激發研究界探索新穎應用程式（applications）的興趣，但他們仍不清楚該演算法的終極性能限制到底為何。經過Skoltech深度量子實驗室（Deep Quantum Laboratory）科學家比亞蒙特（Jacob Biamonte）的領導，技術團隊發現了Google廣泛採用的方法中有根本上的侷限，並將其量化出來。該研究詳細介紹了所發現的可達性缺陷（reachability deficits）以及缺陷對變分QAOA量子演算法（variational QAOA quantum algorithm）的限制。
由於內部量子至經典（quantumto-classical）的反饋過程，QAOA和其它變分量子演算法難用已知的數學技術進行分析。換句話說，給定的量子計算只能在固定的時間量裡運行，在此固定時間內僅可執行固定數量的量子運算。透過QAOA試圖形成的一系列最佳逼近值，以最小化目標函數來迭代（重複反饋過程）運用這些量子運算，該研究發現了在這過程中所產生的新限制。
在任何固定深度的量子電路中，QAOA逼近最佳解的能力從根本上取決於問題密度。就最大可滿足性問題（maximum satisfiability problem, MAX-SAT）來看，可以將密度定義為問題約束（problems constraints）與變量計數（variable count）的比率，簡潔來說就是「子句密度（clause density）」。在問題密度（problem densities）增加的情況下，隨機生成的MAX-SAT實例中固定深度的QAOA迴路性能，由QAOA最優值（optima）與精確最優值（exact optima）之差決定；儘管深度較大的版本可實現更好的性能，但它們仍顯示出可達性缺陷。
此次研究發現了高密度的問題實例，無論演算法的運行多長時間，所得到的最佳解決方案都無法保證結果近似。看來，量子增強演算法還有很長一段路要走呢！
新聞來源
Russian Scientists Break Google’s Quantum Algorithm, SciTech Daily, 2020.
