群馬大学大学院理工学府電子情報部門の森前智行准教授は、ノイズが非常に多く計算能力が弱い量子コンピューターであっても、古典コンピューターの性能を十分に上回ることの理論的な証明に成功した。
量子コンピューターとは、量子力学に従って動作する全く新しいタイプのコンピューターのこと。私たちが現在使っているコンピューター（古典コンピューター）をはるかに凌駕する計算性能を持つと信じられており、その実現に大きな期待が寄せられている。
中でも、どのような量子アルゴリズムでも走らせることのできる汎用量子コンピューターの開発は一つの究極のゴールとされ、世界中で多くの研究者が取り組んでいる。しかしながら、大量の量子ビットを扱える汎用量子コンピューターの実現はまだ難しく、最近では、汎用ではなく、ある特定の問題に対して優れた計算を可能とする非汎用の量子コンピューター開発に注目が集まっている。
非汎用量子コンピューターの例として最も古いものに、one-clean-qubitモデルが挙げられる。one-clean-qubitモデルは、任意の量子計算を行うことはできないが、結び目不変量の計算など特定の問題に限っては、現在の古典のベストのアルゴリズムよりも高速に解くことができる。この事実は、one-clean-qubitモデルが古典コンピューターよりも強力であることを示唆するが、その証明はこれまでなされていなかった。
本研究では、このone-clean-qubitモデルが古典コンピューターよりも高速であることを計算量理論に基づいて初めて理論的に証明した。これにより、複雑な汎用量子コンピューターを作らずとも、近い将来に実現できる技術で、量子コンピューターの古典コンピューターに対する優位性を実演できるようになると期待されている。
