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

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

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

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

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

這個問題很簡單，但到現在還未完全解決，李綠周教授稱。

探尋量子計算優勢

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

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

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

量子經典模型

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

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

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

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

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

量子查詢模型

量子查詢算法

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

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

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

關于精確量子算法的意義，有觀點認為“容忍出錯概率才換來了算法的提速”，精確量子算法對此是很好的反駁，體現了概率算法的區別。

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

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

·對全函數的刻畫；

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

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

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

責任編輯：gt