あるAnonymous Coward 曰く、

群馬大学の森前智行准教授が、古典的な非汎用量子コンピュータモデルである「one-clean-qubit」モデルで解くことのできる結び目不変量の計算と行った問題については、量子コンピュータではない「古典コンピュータ」によるアルゴリズムよりも量子コンピュータのほうが高速に解けることを理論的に証明したと発表した（群馬大学と科学技術振興機構の共同発表、大学ジャーナル、論文）。

one-clean-qubitモデルによる量子コンピュータは任意の量子計算は行えないものの、特定の問題に関しては高速に解けることが知られていた。また、量子コンピュータと古典コンピュータの計算可能性は等しく、また量子コンピュータは古典コンピュータと同様の演算も行えるため、古典コンピュータで高速に解ける問題は量子コンピュータでも高速に解けるとされていた。今回の研究結果は、量子コンピュータが特定の問題において古典コンピュータよりも高速に解けることを証明するものとなる。