局所ハミルトニアンの非冗長性の計算量
スポンサーリンク
概要
- 論文の詳細を見る
Gharibian, Kempe [ICALP2012] は局所ハミルトニアンの冗長性に関する問題 QIRR を導入した.この問題は,局所ハミルトニアンの和が与えられたときにエネルギー期待値の条件を満たした部分和が存在するかを問う問題である.彼らはこの問題が cq-Σp2 困難であることを証明したが,その完全性を示すことはなかった.本論文ではまず,局所ハミルトニアンに関する計算複雑さの高い問題から QIRR への帰着を与え,QIRR が cq-Σp2 に属さない証拠を与える.その後,より適切な形で局所ハミルトニアンの冗長性に関する問題を定義し,再定式化した問題が cq-Σp2 完全であることを示す.
- 2014-06-06
著者
関連論文
- Quantum Oracles and Computational Complexity (Algebraic Systems, Formal Languages and Computations)
- 量子Turing機械の局所遷移関数 (情報数理に関連する応用函数解析の研究)
- 量子コンピュータの計算量(応用函数解析の研究)
- 量子コンピュ-タの計算量
- 時間ドロボー問題の物質的ゼロ知識証明 (理論計算機科学の新展開)
- Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete
- 局所ハミルトニアンの非冗長性の計算量
- 量子コンピュータ:1.量子計算の基礎