量子グラフ理論確立による量子計算能力の限界解明
【研究分野】情報学基礎
【研究キーワード】
量子計算理論 / 量子グラフ理論 / 量子コンピュータ / 計算量理論 / グラフマイナー理論 / 量子格子グラフ理論 / 量子グラフマイナー理論 / 格子グラフ / イジングモデル / 分配関数 / 指数時間アルゴリズム
【研究成果の概要】
量子計算能力の限界解明を目指して、研究分担者・連携研究者らにより多角的に研究を進め、次のような成果をあげた。
(1) 測定ベース量子計算等の量子計算モデルの離散・物理構造に着目し、量子回路最適化や状態変換可能性・測定の汎用実装法・周期グラフ状態の万能計算性について成果を得た。(2) グラフの点マイナー理論を適用して、量子情報の観点からイジング分配関数の効率的計算法を考察し、量子グラフ彩色について量子非局所性での計算量理論での還元性を導入した解析法を提案した。(3) 量子多証明者対話証明について、量子AMゲームに関する統一的成果を得た。(4) 古典回路設計理論で重要なBDDを量子計算と結びつけた。
【研究代表者】