Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete

スポンサーリンク

概要

• 論文の詳細を見る

• This paper presents stronger methods of achieving perfect completeness in quantum interactive proofs. First, it is proved that any problem in QMA has a two-message quantum interactive proof system of perfect completeness with constant soundness error, where the verifier has only to send a constant number of halves of EPR pairs. This in particular implies that the class QMA is necessarily included by the class QIP_1 (2) of problems having two-message quantum interactive proofs of perfect completeness, which gives the first nontrivial upper bound for QMA in terms of quantum interactive proofs. It is also proved that any problem having an m-message quantum interactive proof system necessarily has an (m+1)-message quantum interactive proof system of perfect completeness. This improves the previous result due to Kitaev and Watrous, where the resulting system of perfect completeness requires m+2 messages if not using the parallelization result.

• 一般社団法人電子情報通信学会の論文
• 2013-06-17

著者

• 西村 治道

  名古屋大学人間情報学研究科

• ルガル フランソワ

  東京大学情報理工学系研究科

• 小林 弘忠

  国立情報学研究所情報学プリンシプル研究系

関連論文

• General scheme for perfect quantum network coding with free classical communication (コンピュテーション)
• Quantum Oracles and Computational Complexity (Algebraic Systems, Formal Languages and Computations)
• 量子Turing機械の局所遷移関数 (情報数理に関連する応用函数解析の研究)
• 量子コンピュータの計算量(応用函数解析の研究)
• 量子コンピュ-タの計算量
• Constructing quantum network coding schemes from classical nonlinear protocols (コンピュテーション)
• 時間ドロボー問題の物質的ゼロ知識証明 (理論計算機科学の新展開)
• Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete
• 局所ハミルトニアンの非冗長性の計算量
• 量子コンピュータ:1.量子計算の基礎

スポンサーリンク