與傳統(tǒng)計(jì)算機(jī)相比，量子計(jì)算機(jī)可以利用量子糾纏和疊加原理來顯著提升計(jì)算速度。近日，由 Robin Kothari 帶領(lǐng)的微軟研究團(tuán)隊(duì)，就在兩個(gè)已經(jīng)持續(xù) 20 多年的常見問題的研究上取得了重大的突破。具體說來是，研究團(tuán)隊(duì)重新討論了一些重要問題類別中最大可行的量子加速問題，且其算法能夠在比例量子計(jì)算機(jī)上實(shí)現(xiàn)指數(shù)級(jí)的加速。 >rmqBDKaQ  
h_3E)jc  
Ee%%d  
早在 2019 年的時(shí)候，Robin Kothari 與研究合著者 Hao Huang 就已經(jīng)實(shí)現(xiàn)了一定的突破。 \aUC(K~o\;  
By",rD- r  

該設(shè)想解決了困擾人們已久的靈敏度猜想問題，且證明了針對(duì)非結(jié)構(gòu)化問題的最佳量子加速是四次（T versus T^4）。

$AjHbU.I{  
:g=qz~2Xk  
幸運(yùn)的是，新研究表明，同樣的證明方法，亦可用于回答有關(guān)圖形量子加速的古老猜想。該問題具體涉及分析大量非結(jié)構(gòu)化數(shù)據(jù)集，并在其中查找潛在的連接與模式。 .|>3k'<l  
cO+qs[ BQ  

1999 年的時(shí)候，Buhrman 等人提出 —— 任何量子算法都必須查詢 Ω（√n） 次，才能確定單調(diào)圖的性質(zhì)。 Y0dEH^I  
' ;FnIZ  
推測答案的復(fù)雜度與時(shí)間呈線性相關(guān)，與最優(yōu)解相對(duì)的最壞情況邊界為 Ω（n），可借助 Grover 算法來實(shí)現(xiàn)。

DGn;m\B  
Eib5  
近日，Kothari 團(tuán)隊(duì)以最優(yōu)方式證明了這一猜想。鑒于與該猜想有關(guān)的經(jīng)典對(duì)應(yīng)物尚未得到證明，微軟研究人員的這項(xiàng)成果也是獨(dú)一無二的。 m6\E$;`  
-[9JJ/7y  

最驚訝的是，我們竟然能夠完全解出這個(gè)量子模擬猜想，而經(jīng)典版本仍然未能解決。