微软攻克了两个已有20年历史的量子计算问题
与传统计算机相比，量子计算机可以利用量子纠缠和叠加原理来显著提升计算速度。近日，由 Robin Kothari 带领的微软研究团队，就在两个已经持续 20 多年的常见问题的研究上取得了重大的突破。具体说来是，研究团队重新讨论了一些重要问题类别中最大可行的量子加速问题，且其算法能够在比例量子计算机上实现指数级的加速。 wQ}r/2n|^
"yWw3(V2>
[attachment=100295] i5,iJe0cA
非结构化问题的量子加速研究（来自：Microsoft） ex3 Qbr
早在 2019 年的时候，Robin Kothari 与研究合著者 Hao Huang 就已经实现了一定的突破。 v}B%:1P4
NYm"I`5w
该设想解决了困扰人们已久的灵敏度猜想问题，且证明了针对非结构化问题的最佳量子加速是四次（T versus T^4）。
$3-v W{<
Ey6R/M)?:y
幸运的是，新研究表明，同样的证明方法，亦可用于回答有关图形量子加速的古老猜想。该问题具体涉及分析大量非结构化数据集，并在其中查找潜在的连接与模式。 QV;o9j
e#"h@kZP
1999 年的时候，Buhrman 等人提出 —— 任何量子算法都必须查询 Ω（√n） 次，才能确定单调图的性质。 Shn,JmR
i? 00!t
推测答案的复杂度与时间呈线性相关，与最优解相对的最坏情况边界为 Ω（n），可借助 Grover 算法来实现。
3EoCEPb#
9T,/R1N8
近日，Kothari 团队以最优方式证明了这一猜想。鉴于与该猜想有关的经典对应物尚未得到证明，微软研究人员的这项成果也是独一无二的。 Dg&84,bv^
LQ+/|_( .
最惊讶的是，我们竟然能够完全解出这个量子模拟猜想，而经典版本仍然未能解决。
|