京大ら,弱い量子コンピューターでも古典より強いと証明

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

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

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

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

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

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

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

その他関連ニュース

  • 医科歯科大ら,光子と人工原子の量子ビットを交換
    医科歯科大ら,光子と人工原子の量子ビットを交換 2024年05月24日
  • 理研,シリコン量子ビットの高精度読み出しを実現 2024年02月14日
  • 東大,電子とテラヘルツ電磁波の強結合状態を実現 2024年02月14日
  • 東大,量子コンピューター2種の時間発展を比較 2023年12月05日
  • 東大,テラヘルツと電子の強結合状態を高感度検出 2023年11月09日
  • 中央大,光格子中の量子エンタングルメントに知見 2023年11月02日
  • 産総研ら,超伝導量子ビットを光で初期化 2023年10月31日
  • 凸版印刷,量子で肉眼で判別できない不良を検知 2023年09月20日