京都大学、弱い量子コンピュータの強さを証明：量子スプレマシーを検証

京都大学の研究グループは、1量子ビットしか使えない「弱い」量子コンピュータでも、現行のコンピュータ（古典コンピュータ）より「強い」場面があることを、理論的に証明した。

[馬本隆綱，EE Times Japan]

one-clean qubitモデル以外にも適用可能な新手法

　京都大学基礎物理学研究所の森前智行講師と理学研究科の藤井啓祐特定准教授らによる研究グループは2018年5月、1量子ビットしか使えない「弱い」量子コンピュータでも、現行のコンピュータ（古典コンピュータ）より「強い」場面があることを、理論的に証明したと発表した。

　今回の研究は、森前氏と藤井氏らの他、国立情報学研究所の小林弘忠特任研究員、名古屋大学大学院情報学研究科の西村治道准教授、東京大学先端科学技術研究センターの玉手修平特任助教、NTTの谷誠一郎上席特別研究員らが共同で行った。

　量子コンピュータは、量子力学に基づき動作するコンピュータ。古典力学に基づいて動作し、2進法で演算を行う現行のコンピュータに比べると、極めて高速に演算処理を実行できる。ただし、大量の量子ビットを自由自在に用いることができる巨大な万能量子コンピュータを実現するには、まだ技術的課題も多いという。

量子コンピュータのイメージ 出典：京都大学他

　そこで研究グループは、実質的に1量子ビットしか使えないが、近い将来に実現可能とみられる「弱い」量子コンピュータに注目し、古典コンピュータに対する優位性（量子スプレマシー）を新たな手法で検証した。

　「弱い」量子計算モデルはいくつか研究されているという。この1つに「one-clean qubitモデル」がある。近年、「多項式階層の無限性」に基づき、量子スプレマシーが理論的に証明された。しかし、postBQP（事後選択を可能とする量子コンピュータが多項式時間で解ける判定問題の集合）という計算量クラスを利用するこの方法では、事後選択用と結果出力用に、最低3つの出力量子ビットを測定する必要がある。このため、きれいに初期化された量子ビットが1つしか使えないone-clean qubitモデルでも、量子スプレマシーが発現するかどうかはこれまで明確になっていなかった。

　研究グループは今回、one-clean qubitモデルを用いて、1量子ビットの測定のみで優位性が得られることを論理的に証明した。具体的には、NP（解が正しいことを検証することが多項式時間でできる判定問題の集合）の量子版であるNQPを、証明する手法に用いたという。

　今回発見した新たな手法は、「互作用無しの光粒子量子コンピュータ」や、「交換するゲートのみからなる量子コンピュータ」「ランダムゲートからなる量子コンピュータ」など、one-clean qubitモデル以外の弱い量子計算モデルにも応用でき、これらの優位性を証明することが可能だという。

　今回の研究成果について研究グループは、「古典コンピュータに対して、単なる量子スプレマシーを示すことにとどまらず、有用な量子アルゴリズムの開発にもつながる」とみている。