西蒙算法在量子計算機上「跑」得更快

2021-02-15 中科院物理所

來自南非的一組研究團隊近日成功地在量子計算機上運行了西蒙算法（Simon’s algorithm），且這一算法在量子計算機上的運行表現比電子計算機表現得更好。相關論文刊登在《物理評論快報》上。

　　量子計算機是一種基於量子力學的計算設備，用來存儲數據的對象是量子比特而非經典計算機的電子比特。科學界普遍認為，由於量子計算機能夠利用量子糾纏和疊加等獨特的量子物理屬性，在運行某些特定算法時，它會比現有計算機更為快速和高效。遺憾的是，到目前為止，還沒有辦法在量子計算機上運行這些量子算法來檢驗這一理論。

　　西蒙算法便是適用於量子計算機算法中的一種，它由丹尼爾·西蒙20年前提出，認為這種算法能夠挖掘量子計算機的加速潛力。西蒙算法的目的，是為了解決量子黑箱問題，即將執行計算任務的一段程序或者一個公式看作黑箱，看黑箱是否對每一個可能的輸入給出一個唯一的輸出。

　　據物理學家組織網11月18日（北京時間）報導，研究團隊在一臺量子計算機上運行了該算法的最簡單版本，僅僅用了六個量子比特，量子計算機完成這一任務僅用了兩次迭代，而普通計算機得用三次。這種區別似乎不算什麼，但人們相信，如果增加更多量子比特，量子計算機和普通計算機運算能力的差別就會拉大，這也意味著，量子計算機能更快、更高效地解決此類算法問題。不過，還是要潑一盆冷水，到目前為止，能夠運行西蒙算法並沒有什麼實際價值，該實驗的唯一目的是證明量子計算機在一種算法上能夠做得更好。

　　不過，也別太灰心，證明了類似算法在量子計算機上運行得更快，科研人員或可以期待，像肖爾算法（可被用來進行大數質因數分解，這是加密機制的重要組成部分）這樣的量子算法在量子計算機上同樣能「跑」得更快。

（來源：科技日報）

歡迎轉發分享；

關注請在公眾號搜索中科院物理所，或掃描下方二維碼：

相關焦點

  • 量子計算機將威脅網際網路安全基礎的不對稱加密算法
    （量子計算機的性能超越所有傳統計算機），在其自研的量子計算機上用時3分20秒完成的任務需要最強超算運算1萬年，但隨後谷歌提交給NASA的論文後被刪除。上周的2019雲棲大會上，阿里達摩院就有一個宣布，就是其量子實驗室宣布完成了第一個可控的量子比特研發工作。那麼，性能強大的量子計算什麼時候能夠破解密碼？結論是：量子計算對諸如RSA和ECC這樣的不對稱密碼算法構成了生存威脅，這些算法實際上是當前所有網際網路安全的基礎。這個結論來自美國國家科學院量子計算可行性和含義的技術評估委員會。
  • 量子計算機的算法模型初探
    量子計算機的運行是對qubit（量子位）的操作，從一個量子態演化到另一個量子態，決定兩個量子態如何演化的是量子門，其實質是一個遵循量子力學的Unitary Operator（么正算符）。以上特質決定了兩種計算機的算法有根本不同。
  • 新的「陷離離子」算法可預測早期量子計算機的計算能力
    薩塞克斯大學的量子物理學家創建了一種算法，該算法可加快當前正在開發的早期量子計算機的計算速度。他們創造了一種在量子計算機周圍路由離子（或帶電原子）的新方法，以提高計算效率。 Sussex團隊展示了如何使用他們的新「路由算法」最有效地完成這種量子計算機中的計算。他們的論文「全球連接的被困離子量子計算機的高效量子位路由」 發表在《高級量子技術》雜誌上 。
  • 在量子計算機上確定本徵態和熱態的新算法
    在量子化學中，玻恩–奧本海默近似是一個假設，即分子中的電子運動和核運動可以分開。其他各種科學問題也需要在量子計算機上精確計算哈密頓基態、激發態和熱態。 一個重要的例子是組合優化問題，可以將其簡化為找到合適的自旋系統的基態。到目前為止，在量子計算機上計算哈密頓本徵態的技術主要基於相位估計或變分算法，這些算法被設計為近似最低能量本徵態（即基態）和許多激發態。
  • 「九章」量子計算機的裡程碑意義
    【現象】近日，中國科學技術大學宣布，該校潘建偉團隊與中科院上海微系統所、國家並行計算機工程技術研究中心合作，成功構建76個光子的量子計算原型機「九章」，求解數學算法「專家表示，「如果量子計算原型機，在某個問題上的計算能力超過了最強的傳統計算機，就證明量子計算在未來有多方超越的可能。」通俗來講，就是用極端複雜的問題來考驗量子計算，讓它在實際應用中證明自己的實力。
  • ——潘建偉團隊解說「九章」量子計算機
    算力新高度 技術三優勢「量子優越性」——橫亙在量子計算研究之路上的第一道難關。這是一個科學術語：作為新生事物的量子計算機，一旦在某個問題上的計算能力超過了最強的傳統計算機，就證明了量子計算機的優越性，跨過了未來多方面超越傳統計算機的門檻。多年來，國際學界一直高度關注、期待這個裡程碑式轉折點到來。
  • 裡程碑式突破 潘建偉團隊解說』九章』量子計算機
    算力新高度 技術三優勢「量子優越性」——橫亙在量子計算研究之路上的第一道難關。這是一個科學術語：作為新生事物的量子計算機，一旦在某個問題上的計算能力超過了最強的傳統計算機，就證明了量子計算機的優越性，跨過了未來多方面超越傳統計算機的門檻。多年來，國際學界一直高度關注、期待這個裡程碑式轉折點到來。
  • ——潘建偉團隊解說「九章」量子計算機
    （小標題）算力新高度 技術三優勢「量子優越性」——橫亙在量子計算研究之路上的第一道難關。這是一個科學術語：作為新生事物的量子計算機，一旦在某個問題上的計算能力超過了最強的傳統計算機，就證明了量子計算機的優越性，跨過了未來多方面超越傳統計算機的門檻。
  • 「九章」計算機助力我國首次實現「量子計算優越性」
    「量子計算優越性」，指的是作為新生事物的量子計算機，一旦在某個問題上的計算能力超過了最強的傳統計算機，就證明了量子計算機的優越性，跨過了未來在多方面超越傳統計算機的門檻。「這將實驗各方面的技術推進到遠超以前的水平。」
  • 量子計算機原理與退火算法的通俗解釋
    但隨著科學的發展，量子理論的巨大潛能越來越多的被發掘出來，並被應用到了多種領域。本文的目的是盡力用基礎易懂的語言來解釋自己所理解的量子物理的基礎理論並著重介紹量子計算機的實現原理、量子計算機所使用的量子退火算法以及量子計算機的應用。
  • 「九章」量子計算機的裡程碑意義 | 新知
    「九章」，求解數學算法「高斯玻色取樣」只需200秒，而目前世界最快的超級計算機要用6億年。專家表示，「如果量子計算原型機，在某個問題上的計算能力超過了最強的傳統計算機，就證明量子計算在未來有多方超越的可能。」通俗來講，就是用極端複雜的問題來考驗量子計算，讓它在實際應用中證明自己的實力。
  • 量子計算機有望突破，新理論提示開發量子算法更有效方法
    普渡大學的科學家們說，但是大多數時候，創造一種可以擊敗傳統計算機的量子算法是一個偶然的過程。為了給該過程帶來更多指導並減少其隨意性，這些科學家開發了一種新理論，該理論可能最終導致對量子算法進行更系統的設計。發表在《高級量子技術》雜誌上的一篇論文中描述的新理論是確定可以用可接受數量的量子門來創建和處理哪些量子態以勝過普通算法的首次已知嘗試。
  • 一文讀懂「量子霸權」|量子計算機|算法_網易訂閱
    一般認為，如果量子計算機在「某些特定問題」上的計算能力超過了傳統經典計算機，那麼就被認為實現了「量子霸權」。專家估計，如果量子計算機能操控超過49個量子比特，其在某個特定問題上的計算速度就有可能超過包含超級計算機在內的任何傳統計算機。　　為什麼谷歌那麼在意自己獲得了「量子霸權」？人類實現「量子霸權」究竟有多大意義？
  • 新的量子算法破解了非線性方程,計算機能否代替人類成為先知?
    在 11 月發表的獨立研究中，Childs 領導的團隊和 MIT 的團隊都描述了一個強大的工具，可以使量子計算機更好地對非線性動力學進行建模。與傳統計算機相比，量子計算機能夠利用量子現象更有效地執行某些特定的計算。正是由於具有這些功能，量子計算機得以使複雜的線性微分方程式被快速地推翻。長期以來，研究人員一直希望他們可以通過巧妙的量子算法來解決非線性問題。
  • 量子編程取得突破:量子計算機的第一種直觀語言
    ETH智能系統實驗室（SRI）的計算機科學教授Martin Vechev說：「對量子計算機進行編程仍然是研究人員面臨的挑戰，這就是為什麼我如此興奮，以至於我們現在可以繼續蘇黎世ETH對量子計算機和程式語言的發展。」他認為：「與現有語言相比，我們的量子程式語言Silq使程式設計師能夠更好地利用量子計算機的潛力，因為代碼對於程式設計師而言更緊湊，更快，更直觀並且更易於理解。」
  • 新的量子算法破解了非線性方程,計算機能否代替人類成為「先知」?
    在 11 月發表的獨立研究中，Childs 領導的團隊和 MIT 的團隊都描述了一個強大的工具，可以使量子計算機更好地對非線性動力學進行建模。與傳統計算機相比，量子計算機能夠利用量子現象更有效地執行某些特定的計算。正是由於具有這些功能，量子計算機得以使複雜的線性微分方程式被快速地推翻。長期以來，研究人員一直希望他們可以通過巧妙的量子算法來解決非線性問題。
  • 計算機科學家設定基準以優化量子計算機性能
    計算機科學家表明，高速量子計算機如何使用其電路執行量子程序的現有編譯器會抑制計算機實現最佳性能的能力。具體來說，研究表明，改進量子編譯設計可以使計算速度比目前演示的速度快45倍。計算機科學家創建了具有最佳深度或大小的基準量子電路系列。在計算機設計中，電路深度越小，可以更快地完成計算。
  • 谷歌開源量子算法框架Criq,有望找到量子計算機真正用途
    比方說，使用五個糾纏量子的算法，能同時進行 25 或者 32 個運算，而傳統計算機必須一個接一個地運算。理論上， 300 個糾纏量子能進行的並行運算數量，比宇宙中的原子還要多。在谷歌看來，過去幾年裡，量子計算在量子硬體的構建、量子算法方面都有明顯的發展，隨著Noisy Intermediate Scale Quantum（NISQ）計算機的出現，開發用於理解這些機器功率的算法變得越來越重要。然而，在NISQ處理器上設計量子算法時的一個常見問題是如何充分利用這些有限的量子器件 ，集中資源來解決難題，而不是損耗在算法與硬體之間不良映射上。
  • 量子計算機會真正摧毀比特幣嗎？
    量子物理學家正在闡述量子計算機對密碼學和加密貨幣的現實影響。在YouTube視頻中，量子物理學家Anastasia Marchenkova分享了有關利用量子計算機打破加密技術的競賽的兩分錢。「 Shor的[量子]算法可以破壞RSA和橢圓曲線加密，這是一個問題，因為如今我們的許多數據都使用這兩種算法進行了加密。量子計算機並非在所有方面都更快。它們在某些問題上的速度更快，而且碰巧這種RSA和橢圓曲線加密屬於這種保護。
  • 20年攻克三大技術難關,潘建偉團隊解說「九章」量子計算機
    這是一個科學術語：作為新生事物的量子計算機，一旦在某個問題上的計算能力超過了最強的傳統計算機，就證明了量子計算機的優越性，跨過了未來多方面超越傳統計算機的門檻。多年來，國際學界一直高度關注、期待這個裡程碑式轉折點到來。