京都大学，国立情報学研究所，名古屋大学，東京大学，日本電信電話らは共同で，実質的に1量子ビットしか使えないような「弱い」量子コンピューターでも，ある場面では古典コンピューターより「強い」ことを，理論的に証明した（ニュースリリース）。

大量の量子ビットを自由自在に使え，任意の量子アルゴリズムを完全にエラー耐性のある状態で実行できるような量子コンピューターを実現するのはまだ難しく，近い将来に実現できるレベルの「弱い」量子コンピューターで，古典コンピューターに対する優位性（量子スプレマシー）を示そうとする研究が盛んに行なわれている。

これまで，さまざまな「弱い」量子計算モデルが研究されてきた。中でも，「one－clean qubitモデル」と呼ばれるモデルは最も古い1つで，きれいに初期化された量子ビットは1つしか使えないが，結び目不変量であるJones多項式の計算など，古典コンピューターで効率的に計算する方法が知られていない量を効率的に計算できることが示されている。そのため，このモデルは，古典計算機よりは少し「強い」だろう，と予想されていた。

しかし，「今のところJones多項式の効率的な古典アルゴリズムが知られていない」というだけで，将来，効率的な古典アルゴリズムが発見されれば優位性は無くなる。近年，より強固な計算量理論的基盤に基づいて，one－clean qubitモデルの優位性が理論的に証明されたが，この証明では出力量子ビットを3つ以上測定する必要があるため，このモデルで量子スプレマシーが出るかどうかは未解決だった。

研究では，one－clean qubitモデルにおいて，1量子ビットの測定のみでも量子スプレマシーが得られることを初めて理論的に証明した。従来の証明にはpostBQPという計算量クラスを利用していたため，事後選択用と結果出力用に最低3つの量子ビットを測定する必要があった。今回はNQPというNPの量子版を使うことにより，1つの量子ビットの測定のみで十分になった。

さらに，今回の手法は，ほかの弱い量子計算モデルにも応用することができ，これらのモデルの量子スプレマシーを，従来より強い計算量理論的基盤で証明しなおすことにも成功した。今回の結果は，従来の結果よりもより強固な計算量理論的基盤で量子スプレマシーを証明するもの。

この研究は，理論的基盤を整備するものであり，今後の量子計算の理論的，実験的研究の発展に大きく寄与するものだという。また，量子スプレマシーの研究は，単に古典に対する優位性を示すだけでなく，有用な量子アルゴリズムの開発につながることも目指しており，one－clean qubitモデルを使った高速な量子アルゴリズムを開発するのは，今後の重要な課題だとしている。