中山大學教授李綠周:容錯率並非前置因素,一次查詢精確量子算法大...

2020-12-25 IT之家

當前，以量子信息科學為代表的量子科技正在不斷形成新的科學前沿，激發革命性的科技創新，孕育對人類社會產生巨大影響的顛覆性技術。量子信息科技的具體應用包括量子通信、量子計算和量子精密測量三方面。

量子計算具有強大的並行計算和模擬能力，可為人工智慧、密碼分析、氣象預報等所需的大規模計算難題提供解決方案。總體來看，我國在量子計算方面與發達國家處於同一水平線。

我國量子領域在量子計算方面未來 10 到 15 年的發展目標是確立和鞏固我國在全球第一方陣的地位，有效解決大尺度量子系統的效率問題，研製對特定問題的求解能力全面超越經典超級計算機的專用量子模擬機，並為最終實現通用量子計算機探索出一條切實可行的道路。

日前，在由中國科學院物理研究所和量子計算研究中心主辦、中國科學院物理研究所學術服務部協辦的 「量子計算及量子信息研討會」上，中山大學李綠周教授作了題為《什麼樣的問題可以被一次查詢精確量子算法解決？》的報告，探討了一次查詢精確量子算法解決以及量子計算與經典計算的差別與優勢。

什麼叫做一次查詢精確量子算法解決？該量子算法只執行一次查詢操作，要求這一算法精確解決問題，沒有出錯概率，「這種情況下，它可能比經典算法有優勢」李綠周教授表示。像我們所知道的常規的 Shor 算法、Gover 算法都是有出錯概率的。

這個問題很簡單，但到現在還未完全解決。

探尋量子計算優勢

為什麼會關注量子計算，量子計算對比經典計算，其優勢在哪裡？針對哪些工作、哪一方面？量子計算速度更快、更好，那麼它是怎麼更快、怎麼更好？

度量量子計算與經典計算差別的角度有很多，李綠周教授主要從查詢複雜度方面分析了量子計算與經典計算的差別以及其優勢所在。

· 通過基本量子酉變換可以構建一些特定的量子算法。有了高效的量子算法，量子計算機的並行計算就可以充分發揮其優勢。

量子經典模型

為什麼討論這一模型？查詢模型意義何在？

· 查詢模型本質上是只關注某個子過程的調用次數，而不關心其內部結構。

· 查詢模型具有現實意義：例如，在執行摸個計算任務時，我們可能只關心讀取外存的次數，而不是在意外存內部的運行機制。

· 查詢模型為度量複雜性提供了一個便利的視角：時間複雜度下界難以刻畫或衡量（如 P 與 NP 的關係），二查詢複雜度通常有系統的度量方法。

· 經典與量子計算二者計算能力的比較很多時候是從查詢複雜度角度進行考量。比如 Deutsch-Jozsa 算法，Simon 算法，Grover 算法都是從查詢複雜度方面去體現這一點。

量子查詢模型

量子查詢算法

通過研究得出，經典情況下，一次只能查詢一位；量子情況下，一次可以以疊加形式查詢。

其次，著名的 Deutsch-Jozsa 算法就是一次查詢精確量子算法。那麼，能否找到更多的問題可以被一次查詢精確量子算法解決？

除此之外，一次查詢的有界誤差量子算法得到了一些研究，但是結果對精確量子不適用。

關於精確量子算法的意義，有觀點認為 「容忍出錯概率才換來了算法的提速」，精確量子算法對此事很好的反駁，體現了概率算法的區別。精確這個詞的說法體現了量子與概率從某種程度上的區別。

什麼樣的函數可以被一次查詢的量子算法精確計算？

基於實驗研究，得出三種結果：

· 對全函數的刻畫；

· 部分函數方面，得到了一些充分必要條件的初步的結果；

· 基於等價條件，構建了新的可被一次查詢量子算法精確計算的函數。

上面提及的新的函數包含兩類，它們都不是對稱函數，據了解，之前所有的函數能被一次查詢量子算法精確計算的函數都是對稱函數。新的非對稱函數目前還沒有應用價值。

附：

Shor 算法

1994 年，Shor 提出因子分解的量子算法。該算法的基本思想是，首先通過量子並行性通過一步計算獲得所有函數值，然後通過測量函數得到相關聯的函數自變量的疊加態，並對其進行量子快速傅立葉變換，亦即將大數質因子分解轉化為用 QFFT 在多項式步驟內完成的一個函數的周期問題。

Gover 算法

1996 年，貝爾實驗室 Gover 提出。對於 N 個苑蘇的資料庫，用傳統計算機平均要嘗試 N/2 次才能成功，而用量子計算機輔以 Grover 算法不需要超過√N 次。在很 N 大時，速度的優越性非常明顯。這是因為量子計算機將 N 資料庫的個被搜索的對象疊加為 Hilbert 空間中的個態，要搜索的態只是其中的一個分量。

度量角度

· 時間複雜度，關注所耗費時間，如 Shor 算法；

· 查詢複雜度，關注調用某一子過程的次數，如 Gover 算法，有根號的提速；

· 通信複雜度，關注雙方協同完成某一任務時用了多少通信量；

· 電路深度複雜性，關注邏輯門、並行運行時間問題，如 Science2018 的工作，嚴格地證明了有一個問題量子的用常量深度電路就可以解決，但經典常量深度電路無法解決；

· 狀態複雜度，關注一個狀態變遷系統涉及到多少個狀態，狀態越少，系統越簡單；

· 樣本複雜度，關注學習某一目標函數需要多少樣本。

相關焦點

  • 超越谷歌「量子霸權」 中科大團隊研製量子計算原型機「九章」問世
    安徽網 大皖客戶端訊息 記者今天從中國科學技術大學獲悉，該校潘建偉、陸朝陽等組成的研究團隊與中科院上海微系統所、國家並行計算機工程技術研究中心合作，構建了76個光子100個模式的量子計算原型機「九章」，實現了具有實用前景的「高斯玻色取樣」任務的快速求解。
  • 華裔天才唐乙文,18歲創立新算法,《科學》稱:他殺死量子計算
    俗話說龍生龍鳳生鳳，老鼠的兒子會打洞，唐乙文如此優秀，自然有著生物學上的遺傳因素，也缺少不了父親的敦敦教誨。如何實現計算的加快，成本的降低也就成為了擺在量子計算、傳統計算面前的首要問題。 當時，科學界包括唐乙文的導師——量子信息領域的專家亞倫森教授在內，都認為得益於量子力學疊加性的存在，傳統算法是不可能超越量子算法的運行速度的。 但是，唐乙文在學習了量子算法後，卻提出了不同的看法。
  • 中國量子計算原型機「九章」問世,實現「量子霸權」
    量子計算需經歷「三步走」正是由於量子計算機在原理上具有超快的並行計算能力，可望通過特定算法在一些具有重大社會和經濟價值的問題方面，如密碼破譯、大數據優化、材料設計、藥物分析等，相比經典計算機實現指數級別的加速。事實上，量子計算機的研製是一個極具挑戰並且周期可能較長的工作。
  • 突破「量子霸權」!中國量子計算原型機「九章」問世
    (製圖：陸朝陽，彭禮超) 量子計算機在原理上具有超快的並行計算能力，可望通過特定算法在一些具有重大社會和經濟價值的問題方面（如密碼破譯、大數據優化、材料設計、藥物分析等）相比經典計算機實現指數級別的加速。當前，研製量子計算機已成為世界科技前沿的最大挑戰之一，成為歐美各發達國家角逐的焦點。
  • 量子計算正從「玩具」變成「工具」 我國的量子計算正處於什麼階段?
    30多年前，在科學家們對量子疊加、量子糾纏等量子力學基本問題的研究過程中，精細的量子調控技術逐漸發展起來，使得人類從對量子規律的被動觀測跨越到對量子狀態的主動精確操縱，由此我們現在所說的「量子科技」便誕生了。量子科技是融合量子調控和信息技術而產生的新興學科。在這一領域，我國已經取得了一系列重要科學問題和關鍵核心技術突破，並在部分方向實現國際領先。
  • 走向大眾生活,量子科技實用化未來可期——第181期廣州科普大講壇
    11月18日下午，廣州科普大講壇第181期《走向實用化的量子技術》特別直播節目，在廣東廣播電視臺直播間熱烈開講，中山大學物理與天文學院教授、物理與天文學院量子信息和測控團隊負責人羅樂，就量子科技的應用與影響、實用化發展方向、廣東量子科技發展的現狀、粵港灣大灣區能否成為量子信息科技時代的矽谷灣區等方面，給觀眾和網友們帶來了一場內容豐富的知識盛宴，讓公眾更加深刻地理解了量子力學
  • 中國科學技術大學:量子計算原型機「九章」問世
    實現「量子計算優越性」量子計算機在原理上具有超快的並行計算能力，可望通過特定算法在一些具有重大社會和經濟價值的問題方面（如密碼破譯、大數據優化、材料設計、藥物分析等）相比經典計算機實現指數級別的加速。當前，研製量子計算機已成為世界科技前沿的最大挑戰之一，成為歐美各發達國家角逐的焦點。
  • 量子計算正從「玩具」變成「工具」
    30多年前，在科學家們對量子疊加、量子糾纏等量子力學基本問題的研究過程中，精細的量子調控技術逐漸發展起來，使得人類從對量子規律的被動觀測跨越到對量子狀態的主動精確操縱，由此我們現在所說的「量子科技」便誕生了。 　　量子科技是融合量子調控和信息技術而產生的新興學科。在這一領域，我國已經取得了一系列重要科學問題和關鍵核心技術突破，並在部分方向實現國際領先。
  • 王者榮耀:容錯率體現陣容強度,學會搭配高容錯率陣容上分更輕鬆
    前言容錯率這個詞在遊戲中應用廣泛，它通常用來判斷一個團隊中隊友出錯所帶來的影響值，如果容錯率高說明該團隊的可允許隊員犯更多的錯卻不影響勝利，如果容錯率低說明該團隊十分不搭稍有失誤就會導致失敗。所以容錯率一詞通常用在遊戲陣容的選擇中來表達，選出容錯率高的陣容就更接近於遊戲的勝利。
  • 裡程碑式突破 中國科學家實現「量子霸權」
    （製圖：陸朝陽，彭禮超）量子計算機在原理上具有超快的並行計算能力，可望通過特定算法在一些具有重大社會和經濟價值的問題方面（如密碼破譯、大數據優化、材料設計、藥物分析等）相比經典計算機實現指數級別的加速。當前，研製量子計算機已成為世界科技前沿的最大挑戰之一，成為歐美各發達國家角逐的焦點。
  • Light人物:專訪清華大學龍桂魯教授
    現任清華大學物理系教授、北京量子信息科學研究院研究員。本期，很榮幸邀請到龍桂魯教授接受Light人物採訪。在這次採訪中，龍教授將分享自己在量子信息科研與教書育人的經驗。今天就讓我們一起走近龍教授，了解他和Light背後的故事。
  • 量子糾纏,時空幾何與機器學習
    近年來，量子信息技術取得了連續的突破。它將成為下一代技術革命的領導者嗎？加州大學聖地牙哥分校的智力科學家兼助理教授尤亦莊通過量子擦除實驗表明，量子糾纏會影響因果關係甚至改變時間流逝，並討論了量子與智能之間的關係。本文主要討論近二十年來的進展，尤其是過去一年中量子力學領域的進展以及未來可能的進展。在過去的一年中，有兩個關鍵詞，量子引力和人工智慧。
  • 「九章」量子計算機的三大厲害之處
    量子計算優越性，也被稱為「量子霸權」。量子計算機的工作原理具有超快的並行計算能力，它往往通過特定算法，在一些具有重大社會和經濟價值的問題方面起到非常重要作用，比如密碼破譯、大數據優化、材料設計、藥物分析等，因此，相比經典計算機而言，它能夠實現指數級別的加速。如果經典計算機是普通的跑者，那么九章量子計算機相當於跑中之王，世界紀錄創作者。
  • 潘建偉院士:量子計算正從「玩具」變成「工具」
    30多年前，在科學家們對量子疊加、量子糾纏等量子力學基本問題的研究過程中，精細的量子調控技術逐漸發展起來，使得人類從對量子規律的被動觀測跨越到對量子狀態的主動精確操縱，由此我們現在所說的「量子科技」便誕生了。　　量子科技是融合量子調控和信息技術而產生的新興學科。在這一領域，我國已經取得了一系列重要科學問題和關鍵核心技術突破，並在部分方向實現國際領先。
  • 中國科學院潘建偉院士:量子計算正從「玩具」變成「工具」
    30多年前，在科學家們對量子疊加、量子糾纏等量子力學基本問題的研究過程中，精細的量子調控技術逐漸發展起來，使得人類從對量子規律的被動觀測跨越到對量子狀態的主動精確操縱，由此我們現在所說的「量子科技」便誕生了。
  • 我國量子計算機「九章」,200秒完成超算需6億年才能求解難題
    」，衡量指標包括量子比特數、設備交叉通信、門和測量誤差、電路編譯效率以及設備連接等影響因素。2020年12月4日，中科大潘建偉教授團隊就實現76光量子計算機，只用200秒就求解數學算法高斯玻色取樣，而這個過程使用當今世界最先進的超級計算機「富嶽」需要6億年！國際學術期刊《科學》評價這一成果時稱「一個最先進的實驗」、「一個重大成就」。這個76量子比特量子原型計算機控制有多難？
  • 量子材料研究的新範式以精確模型計算及實驗揭示拓撲物質特性
    圖1. 量子磁體TMGO的NMR自旋晶格弛豫速率測量結果，T_L和T_U之間高起的平臺就是拓撲KT相。 最近，他與北京航空航天大學的李偉博士、復旦大學的戚揚教授、中國人民大學的於偉強教授和南京大學的溫錦生教授合作，解開了2016年諾貝爾物理學獎得獎論說「拓撲相」之謎。
  • ——潘建偉團隊解說「九章」量子計算機
    實驗顯示，「九章」對經典數學算法高斯玻色取樣的計算速度，比目前世界最快的超算「富嶽」快一百萬億倍，從而在全球第二個實現了「量子優越性」。高斯玻色取樣是一個計算概率分布的算法，可用於編碼和求解多種問題。「這是量子領域的重大突破，朝著研製比傳統計算機更有優勢的量子設備邁出一大步！我相信成果背後付出了巨大的努力。」德國馬克斯·普朗克研究所所長伊格納西奧·西拉克說。美國麻省理工學院教授德克·英格倫認為，這是「一項了不起的成就」「一個劃時代的成果」。
  • 中山大學嶺南學院楊子暉教授、曾燕教授獲第八屆高等學校科學研究...
    中山大學共25項成果獲得獎勵。其中，獲著作論文獎19項(一等獎3項，二等獎9項，三等獎7項)；獲諮詢服務報告獎二等獎1項，青年成果獎5項。中山大學嶺南學院共兩項成果獲得獎項，其中著作論文一等獎一項，著作論文二等獎一項。本次獲一等獎為中山大學歷屆獲一等獎數量最多一次。中青年學者表現突出，50歲以下的中青年學者獲獎佔比48%。
  • 20年攻克三大技術難關,潘建偉團隊解說「九章」量子計算機
    實驗顯示，「九章」對經典數學算法高斯玻色取樣的計算速度，比目前世界最快的超算「富嶽」快一百萬億倍，從而在全球第二個實現了「量子優越性」。高斯玻色取樣是一個計算概率分布的算法，可用於編碼和求解多種問題。「這是量子領域的重大突破，朝著研製比傳統計算機更有優勢的量子設備邁出一大步！我相信成果背後付出了巨大的努力。」德國馬克斯·普朗克研究所所長伊格納西奧·西拉克說。美國麻省理工學院教授德克·英格倫認為，這是「一項了不起的成就」「一個劃時代的成果」。加拿大卡爾加裡大學量子研究所所長巴裡·桑德斯說，毫無疑問，這個實驗結果遠遠超出了傳統機器的模擬能力。