二分決定グラフにおける量子計算能力と通信計算量の関連
スポンサーリンク
概要
- 論文の詳細を見る
近年、量子・古典計算モデル間計算力差は計算量理論上の重要な問題となり、多数の量子・古典間計算力差が知られている。しかし、各計算力差間の関係は明らかになっていない。本研究では、既に量子-古典間差が知られている通信計算問題を、古典的計算モデルであるOBDDにおける問題に変換し、OBDD上の量子-古典間計算量差の存在を考察した。結果として、多パーティ間通信計算理論由来の関数を対象に誤りなしの場合において、古典的にはkパーティに対してlogk-1以上の幅が要求される一方、幅2の量子OBDDでその関数を計算するものが存在することを示した。この結果は、量子計算においてもOBDDの容量計算量と、通信計算量との間に何らかの関連が存在することを示唆するものである。
- 一般社団法人情報処理学会の論文
- 2001-05-18