與傳統計算機相比，量子計算機可以利用量子糾纏和疊加原理來(lái)顯著(zhù)提升計算速度。近日，由 Robin Kothari 帶領(lǐng)的微軟研究團隊，就在兩個(gè)已經(jīng)持續 20 多年的常見(jiàn)問(wèn)題的研究上取得了重大的突破。具體說(shuō)來(lái)是，研究團隊重新討論了一些重要問(wèn)題類(lèi)別中最大可行的量子加速問(wèn)題，且其算法能夠在比例量子計算機上實(shí)現指數級的加速。

非結構化問(wèn)題的量子加速研究(來(lái)自：Microsoft)

　　早在 2019 年的時(shí)候，Robin Kothari 與研究合著(zhù)者 Hao Huang 就已經(jīng)實(shí)現了一定的突破。

　　該設想解決了困擾人們已久的靈敏度猜想問(wèn)題，且證明了針對非結構化問(wèn)題的最佳量子加速是四次(T versus T^4)。

　　幸運的是，新研究表明，同樣的證明方法，亦可用于回答有關(guān)圖形量子加速的古老猜想。該問(wèn)題具體涉及分析大量非結構化數據集，并在其中查找潛在的連接與模式。

　　1999 年的時(shí)候，Buhrman 等人提出 —— 任何量子算法都必須查詢(xún) Ω(√n) 次，才能確定單調圖的性質(zhì)。

　　推測答案的復雜度與時(shí)間呈線(xiàn)性相關(guān)，與最優(yōu)解相對的最壞情況邊界為 Ω(n)，可借助 Grover 算法來(lái)實(shí)現。

　　近日，Kothari 團隊以最優(yōu)方式證明了這一猜想。鑒于與該猜想有關(guān)的經(jīng)典對應物尚未得到證明，微軟研究人員的這項成果也是獨一無(wú)二的。

　　最驚訝的是，我們竟然能夠完全解出這個(gè)量子模擬猜想，而經(jīng)典版本仍然未能解決。
　?。?a href="http://www.lsbmaoyi.com">邯鄲做網(wǎng)站公司）

Facebook推出Discover新...

首批商用5G國家網(wǎng)速一覽...