與傳統計算機相比，量子計算機可以利用量子糾纏和疊加原理來顯著提升計算速度。
近日，由 Robin Kothari 帶領的微軟研究團隊，就在兩個已經持續 20 多年的常見問題的研究上取得了重大的突破。
【非結構化問題的量子加速研究，來自：Microsoft】
早在 2019 年的時候，Robin Kothari 與研究合著者 Hao Huang 就已經實現了一定的突破。
該設想解決了困擾人們已久的靈敏度猜想問題，且證明了針對非結構化問題的最佳量子加速是四次（T versus T^4）。
幸運的是，新研究表明，同樣的證明方法，亦可用於回答有關圖形量子加速的古老猜想。該問題具體涉及分析大量非結構化資料集，並在其中查詢潛在的連線與模式。
1999 年的時候，Buhrman 等人提出 —— 任何量子演算法都必須查詢 Ω（√n） 次，才能確定單調圖的性質。
推測答案的複雜度與時間呈線性相關，與最優解相對的最壞情況邊界為 Ω（n），可藉助 Grover 演算法來實現。
近日，Kothari 團隊以最優方式證明了這一猜想。鑑於與該猜想有關的經典對應物尚未得到證明，微軟研究人員的這項成果也是獨一無二的。
最驚訝的是，我們竟然能夠完全解出這個量子模擬猜想，而經典版本仍然未能解決。
與傳統計算機相比，量子計算機可以利用量子糾纏和疊加原理來顯著提升計算速度。
近日，由 Robin Kothari 帶領的微軟研究團隊，就在兩個已經持續 20 多年的常見問題的研究上取得了重大的突破。
【非結構化問題的量子加速研究，來自：Microsoft】
早在 2019 年的時候，Robin Kothari 與研究合著者 Hao Huang 就已經實現了一定的突破。
該設想解決了困擾人們已久的靈敏度猜想問題，且證明了針對非結構化問題的最佳量子加速是四次（T versus T^4）。
幸運的是，新研究表明，同樣的證明方法，亦可用於回答有關圖形量子加速的古老猜想。該問題具體涉及分析大量非結構化資料集，並在其中查詢潛在的連線與模式。
1999 年的時候，Buhrman 等人提出 —— 任何量子演算法都必須查詢 Ω（√n） 次，才能確定單調圖的性質。
推測答案的複雜度與時間呈線性相關，與最優解相對的最壞情況邊界為 Ω（n），可藉助 Grover 演算法來實現。
近日，Kothari 團隊以最優方式證明了這一猜想。鑑於與該猜想有關的經典對應物尚未得到證明，微軟研究人員的這項成果也是獨一無二的。
最驚訝的是，我們竟然能夠完全解出這個量子模擬猜想，而經典版本仍然未能解決。