某些計算難題只可能在量子計算機上解決

2020-12-16 中關村在線

    研究人員提出了一個全新的計算問題，證明其在一個經典的馮諾依曼計算機上即便不是無解的，也將是非常困難的；但是理論上它可以用量子技術來高效率地解決。這個被稱為高斯玻色子抽樣的問題是幾年前提出的一個類似經典抽樣的計算問題，目的是展示量子計算機具有的不可替代的潛在優勢。


圖片來源於百度搜索

    來自捷克布拉格技術大學和德國帕德博恩大學的研究人員在最近一期《物理評論》(Physical Review Letters)上發表了一篇關於高斯玻色子取樣的論文。

    總體而言，高斯玻色子抽樣問題與Scott Aaronson和Alex Arkhipov在2011年提出的原始玻色子抽樣問題極其相似。在這兩個問題中，給予光子穩定輸入頻率，找出測量從光學系統出現的某些光子模式的概率。在複雜性理論中，玻色子抽樣被認為是一個＃P-hard問題，這使得傳統計算機不可能在有限的時間裡解決這個問題。

    因為目前還沒有能夠解決玻色子抽樣問題的量子計算機，幾個研究團隊決定另闢蹊徑，試圖用量子光學實驗來解決這個問題。結果證實本質上的計算難度無法通過設計實驗的手段來繞過。這些實驗的原本最大難點之一是產生大量的單光子。由於完全確定性的單光子源目前尚不存在，迄今為止所進行的所有實驗都使用了概率性而不是確定性的光子源。

    使用概率光子源的缺點是隨著光子數目的增加，產生光子的成本呈指數級增長。到目前為止，使用的光子數量最多的是五個，這還不足以顯示使用量子計算機的優勢。

    為了在實驗中方便地獲得更多的光子，研究人員專門研究了使用高斯態的玻色子取樣。雖然高斯狀態已經被用於各種實驗，但它們的高斯性質從來沒有被專門研究過。這些領域的優勢是實驗成本較低。

    論文主要作者漢密爾頓接受Phys.org採訪時說：「我們設計的實驗方案一個最大的優點是能夠更多使用我們指定輸入狀態的光子。這意味著，如果光子數量是實驗物理學家的主要瓶頸，那麼使用高斯狀態的光子應該能更容易完成實驗。」

    研究的主要結果之一是，儘管實驗如今更容易實現，但高斯玻色子抽樣仍然是一個P-hard問題，因此，像玻色子抽樣一樣，也有可能作為一個體現量子計算優勢的實例，兩代計算機的分野。具體而言，研究人員發現，高斯玻色子採樣與一個稱為Hafnian的矩陣函數有關，這是一個如此困難的問題，目前還沒有可以有效地逼近解的算法。

vga.zol.com.cn true http://vga.zol.com.cn/665/6651560.html report 1853 研究人員提出了一個全新的計算問題，證明其在一個經典的馮諾依曼計算機上即便不是無解的，也將是非常困難的；但是理論上它可以用量子技術來高效率地解決。這個被稱為高斯玻色子抽樣的問題是幾年前提出的一個類似經典抽樣的計算問題，目的是展示量子計算機具有的不可替代...

相關焦點

  • 科普:量子計算機是這樣計算的
    當您看了這兩篇D-Wave公司的文章，您就會明白：什麼是量子計算機、它是如何實現和工作的、它長得什麼樣、解決什麼類型的問題等……D-Wave系統公司，是世界上第一個量產量子計算機的公司，堪稱量子計算機的鼻祖。本文及下一篇文章都是翻譯他們寫的科普文章《量子計算入門》和《D-Wave量子計算機硬體介紹》，李電匠在此逐段逐段的翻譯整合如下，之前的分開翻譯的部分，請進入歷史消息中查找。
  • 什麼是量子計算機?「九章」確立的「量子計算優越性」有多厲害
    「目前的量子計算機使用的是如原子、離子、光子等物理系統，不同類型的量子計算機使用的是不同的粒子，這次的『九章』使用的是光子。」袁嵐峰說。　　袁嵐峰告訴記者，量子計算機並不是對所有的問題都超過經典計算機，而是只對某些特定的問題超過經典計算機，因其對這些特定的問題設計出高效的量子算法。「對於沒有量子算法的問題，例如最簡單的加減乘除，量子計算機就沒有任何優勢。」
  • 量子計算機算力有多強?可能是無數平行宇宙中的計算機在同時計算
    說起量子計算機，很多人可能聽過，這個是當前比較流行的一個詞彙。然而在上個世紀，就已經提出了量子計算機的基本原理。既然名字裡有「量子」的名字，那麼這個計算機到底跟量子力學有沒有關係呢？早在上個世紀，就有人發現正傳和反轉完全可以當做圖靈計算機中的0和1，完全可以使用這個特性開發一個量子計算機！但是這個總得有優勢吧？不然幹嘛不用電子計算機呢？優勢量子計算機最大的優勢剛好就是它的原理。
  • 量子計算機的首要任務是加速機器學習
    正規的神經網絡可能擁有10億個神經元連接，所有連接都需要進行調整。傳統計算機計算單元的所有連接都用龐大的數字矩陣表示，運行神經網絡就是在計算矩陣代數。傳統的方法是，用一個專門的晶片（例如：圖像處理器）來完成這些矩陣運算。而在完成矩陣運算上，量子計算機是不可匹敵的。
  • 要算15萬年難題只需1秒 量子計算機開啟中國速度
    傳統電子計算機要算15萬年的難題，量子計算機只需1秒 　　1981年，美國物理學家費曼指出，由於量子系統具有天然的並行處理能力，用它所實現的計算機很可能會遠遠超越經典計算機。1994年，麻省理工學院的Peter·Shor教授提出分解大質因數的高效量子算法，量子計算引發了世界各國的強烈興趣。
  • 前途無量的量子計算
    對照於傳統的通用計算機，其理論模型是通用圖靈機；而通用的量子計算機，其理論模型即是用量子力學規律重新詮釋的通用圖靈機。1982年，美國著名物理學家理察·費曼教授提出了量子計算的概念，並指出以量子力學為基礎的計算機在處理特定問題時，具有遠超傳統計算機的能力優勢。
  • IBM:決勝量子計算五大戰略!商用近在咫尺
    量子行為的兩個特性，也就是疊加和糾纏，使量子計算機有能力解決目前的常規或傳統機器無能為力的問題：1、疊加。 傳統計算機使用的是只包含「1」或「0」的二進位位。而量子計算機則使用量子位，可以描述「1」、 「0」或者量子位的可能狀態的任意組合（稱為「疊加」）。因此，具有 n 個量子位的量子計算機通過這些量子位彼此疊加，形成了 2n 種可能性。
  • 什麼是量子計算機?「九章」量子計算機又有多神?
    12月4日，包括本報在內的許多媒體報導了一個量子計算的大成果：中國科學技術大學的潘建偉、陸朝陽等人構建了一臺76個光子100個模式的量子計算機「九章」，它處理「高斯玻色取樣」的速度比目前最快的超級計算機「富嶽」快一百萬億倍。也就是說，超級計算機需要一億年完成的任務，「九章」只需一分鐘。
  • 混合量子位解決了量子計算的關鍵障礙!
    博科園-科學科普：科學技術類基於自旋的量子計算機具有解決普通計算機無法解決的數學難題潛力，但在使這些計算機具有可伸縮性方面仍存在許多問題。現在由理研中心(RIKEN Center for Emergent Matter Science)領導的一個國際研究小組已經為量子計算設計了一個新的架構。通過構造一個由兩種不同類型的qubit(量子計算機的基本計算元素)組成的混合設備，他們創建了一個可以快速初始化和讀取的設備，同時還能保持高控制保真度。
  • 牛津大學量子物理博士:我們為什麼需要量子計算?
    未來兩到三年內有望擴大到 50 個量子比特，達到所謂的「量子優越性」(Quantum Supremacy)。屆時在某些問題上，量子計算機的計算能力將超過目前最強大的經典並行計算機。但要達到真正的商業應用，量子比特需要達到百萬級，這是一個非常大的門檻。當規模如此龐大時，量子計算機就可以克服錯誤問題。  即使是最樂觀的科學家也認為，量子計算機不會完全取代現在的電腦。
  • 九章量子計算機在某些方面很厲害,適當的宣傳可以喚起大家的熱情
    叫做高斯玻色採樣，那麼這兩個問題的這個選擇是充分發揮了，就這個現在的所能實現的就是個量子計算的最大的優勢。 它的目的什麼呢？他不是真正的說能夠代替傳統的這個計算機，而是要起到一個宣傳作用。谷歌是這樣。咱們這個也是這樣，就是說讓大家認識到量子計算機最起碼就現在已經在某些特殊的問題上遠遠超過了傳統計算機。
  • 九章量子計算機實現量子霸權?
    不僅是高斯玻色採樣，去年穀歌量子計算取得突破，用來模擬的對象叫隨機量子電路採樣。雖然模擬對象不一樣，但背後邏輯是一樣的。目的就是為了證明，在某些問題上，量子計算相對於傳統計算具有碾壓級別的優勢，這個優勢具體體現在什麼地方，簡單說一下第一次加速，我們要想提高運算速度，要一個重要方法就是搞並行計算，CPU堆和就是這個道理。
  • 「量子霸權」還是「量子優勢」?量子計算競賽「加速時」
    他所帶領的團隊原計劃在去年年底前利用49量子比特模擬系統攻克經典計算機無法解出的難題，率先登頂「量子霸權」。 「我們理想的真正的可實用量子計算是基於成百上千的量子比特，49個量子比特是不夠的。我們已經證明，在傳統超級計算機上使用全新的算法，可以模擬這個數量級的量子計算機。」
  • 當神經網絡遇上量子計算:谷歌證明量子神經網絡可訓練圖像分類
    谷歌已經證明了量子計算也能解決傳統機器學習中的圖像分類問題，而且隨著技術發展，量子計算機將在在學習能力上超越經典的神經網絡。另外量子計算還能解決經典網絡中一些棘手問題，比如預防出現模型訓練中的梯度消失問題。量子神經網絡在第一篇論文中，谷歌構建一個神經網絡的量子模型，研究如何在量子處理器上執行神經網絡的分類任務。
  • 量子計算機的性能何時能超越傳統計算機?
    量子計算被認為能夠解決傳統計算不能解決的問題，但目前量子計算面臨諸多挑戰，性能還未超越傳統計算機。從實踐者的角度看，量子計算的部署至少還需要幾年時間。，甚至解決普通計算機無法解決的問題。如果率先掌握量子技術，將有利於提升國家的競爭力。量子計算的前景在20世紀80年代首次得到認可，但至今仍未實現。量子計算機難以設計、建造和編程。其中，相干性、量子損失是巨大的挑戰，這對量子計算機的運營至關重要，這可能會導致重要程序在運營之前系統就崩潰。
  • 量子計算機的架構,硬體,軟體等都有成果!量子計算時代快了
    與早期經典計算類似，使用真空管、繼電器電路或電晶體構建系統，今天的量子計算機系統可以由幾種硬體技術構建。領先的技術包括超導量子位元和捕獲離子量子位元，其他候選技術也有相當大的興趣。然而，與傳統的二進位計算機不同，量子計算機技術是如此的不同，甚至可以在一個量子位上執行的基本門操作也有很大不同。為軟體使用選擇最合適的門操作，是一個重要的量子計算機設計決策。
  • 量子計算的瓶頸能打破嗎?
    對於科技公司來說，尋找更大算力的新型計算機不可避免。經過數十年的研究，量子計算機相比於其他類型計算機已經具有足夠的優勢來執行超越地球上任何其他計算機的計算。通常認為其上運行的殺手級應用程式能夠解析大數據，這也是現代加密技術的關鍵問題。
  • 「九章」計算機助力我國首次實現「量子計算優越性」
    近日，中國科學技術大學潘建偉、陸朝陽等學者組成的研究團隊與中國科學院上海微系統與信息技術研究所、國家並行計算機工程技術研究中心合作，構建了76個光子的量子計算原型機「九章」。計算玻色採樣問題，「九章」處理5000萬個樣本只需200秒，而目前世界最快的超級計算機需要6億年。
  • 你知道什麼是量子計算機嗎?
    01量子計算機是計算機嗎？首先，用一句話來概括什麼是量子計算機：量子計算機是一種使用量子力學的計算機，它能比普通計算機更高效地執行某些特定的計算。所以說，量子計算機是一種計算機，但它不是簡單的「進階版」計算機。
  • 從基礎量子位到當下火熱的量子計算機,一文助你入門量子計算
    該算法可能過於耗時，無法在實踐中使用，但如果存在這樣的算法，那麼至少在原則上，數學是可以理解的。為了攻擊希爾伯特的這一問題，圖靈精確的定義了算法的含義，並描述了我們現在所稱的圖靈機器（Turing machine）：可以執行任何算法的單一通用可編程計算設備。從那時起，計算機逐漸發展成為了一個產業，數十億臺基於圖靈模型的計算機已經售出。