群馬大学は，ノイズが非常に多く計算能力が「弱い」量子コンピューターであっても，古典コンピューターの性能を十分に上回ることを理論的に証明した（ニュースリリース）。

どのような量子アルゴリズムでも走らせることのできる汎用の量子コンピューターを作るのは一つの究極のゴールだが，大量の量子ビットを扱える汎用の量子コンピューターを実現するのはまだ難しく，最近では，特定の問題に対しては古典コンピューターよりも優れた計算が可能である量子コンピューター（非汎用の量子コンピューター）を開発する研究に興味が持たれている。

このように，計算能力の「弱い」非汎用の量子コンピューターで，古典コンピューターに対する優位性を示そうとする研究は「量子スプレマシー」と呼ばれている。非汎用の量子コンピューターの例として最も古いものに，one-clean-qubit モデルがある。このモデルは、偏極率の低い量子ビットを用いた量子コンピューターであるため，任意の量子計算を行なうことはできない。

しかし，結び目不変量の計算など特定の問題に限っては，現在の古典のベストのアルゴリズムよりも高速に解くことができることが知られている。この事実は，one-clean-qubit モデルが古典コンピューターよりも強力であることを示唆する。

しかしながら，将来より高速な古典アルゴリズムが見つかるかもしれず，one-clean-qubit モデルが本当に古典コンピューターを凌駕する「量子スプレマシー」を示すのか，長年の未解決問題だった。

研究では，今回初めて，この one-clean-qubit モデルが，古典コンピューターよりも高速であることを計算量理論に基づいて理論的に証明しました。これにより，上記の長年の未解決問題に解を与えたことになる。複雑な汎用量子コンピューターを実現しなくとも，近い将来に実現できる非汎用量子コンピューターでも古典コンピューターに対する優位性が証明できたことで，今後の量子テクノロジーの応用において重要な役割を果たしていくことが期待される。

とりわけ，最近IBMがクラウド量子計算のサービスを試験的に開始して話題となったが，将来クラウド量子計算が一般化した際には，まずはこのような非汎用の量子計算がクラウド上でな行われることになるため，この研究はその理論的基盤をなすものだとしている。