【研究領域課題番号】18K19776 (KAKENデータベースで見る）

【研究キーワード】

量子計算 / 量子優越性 / グラウ最適化 / グラフ不変量 / 計算量理論 / 近似量子コンピュータ / 統計物理 / グラフ / マトロイド / 最適化 / 量子コンピュータ / BDD / 量子優位性 / FPTアルゴリズム / マイナー埋込 / 不変多項式 / 量子超越性 / 量子畳込み / グラフ最適化

【研究成果の概要】

グラフのIsing分配関数の計算に対して、グラフ構造の複雑さを表すパラメタの中で枝幅・ランク幅に着目し、そのパラメタを用いた計算量で効率的なものを構成した。特に、パラメタが定数で抑えられるなどの場合に有効である。Ising分配関数からPotts分配関数、そして2変数グラフ不変多項式のTutte多項式へと展開し、有効閉路なしグラフ枝向き付け数に関する成果も得た。Tutte多項式の単峰性が満たされない反例も最小の例を示した。量子優越性に関して、浅層量子回路における近似量子コンピュータであるIBM量子コンピュータにおいて種々Bell不等式の破れの検証を行い、浅層量子回路での量子計算の有効性を示した。

【研究の社会的意義】

量子コンピュータ開発のスピードが、グローバルな研究投資によって実機が使えるようになり、本研究で開発した古典・量子アルゴリズムについて、研究当初は難しかった量子コンピュータにより実験するところまで到達できている。それによって、現在のノイズのある近似量子コンピュータにおける誤差緩和手法の適用と、さらなる方向の提示もでき、当初の予想を超える研究発表を行うことができている。シミュレーションではなく、近似量子コンピュータ実機による実験を先駆的に発表することで、社会的にも量子コンピュータの時代の到来を認識できるものとなっている。

【研究種目】挑戦的研究(萌芽)

【研究期間】2018-06-29 - 2022-03-31

【配分額】6,370千円 (直接経費: 4,900千円、間接経費: 1,470千円)