非有界誤り量子質問計算量

スポンサーリンク

概要

• 論文の詳細を見る

• 本論文は,ブール関数を計算する量子アルゴリズムの成功確率が真に1/2より大きくするための質問計算量,すなわち,非有界誤り量子質問計算量について研究している.量子通信計算量の結果と同様,どんなブール関数に対しても量子質問計算量は常に古典質問計算量のちょうど半分であることを本論文は示す.また,この通信計算量と質問計算量の結果から本論文は,非有界誤りの設定においてもBuhrman-Cleve-Wigderson[STOC'98]が提案した量子質問アルゴリズムを量子通信プロトコルに変換するブラックボックス手法が最適であることを示す.その上,本論文は,非有界誤りモデルを拡張するモデルについても言及する.本論文はこのモデルで量子質問計算量と古典質問計算量を比較すする時,通信計算量の結果と違って,部分関数に対してΘ(log n)のギャップが存在する一方,一般に知られた全関数に対してギャップがないことを証明する.

• 2008-03-03

著者

• 西村 治道

  大阪府立大学理学系研究科

• モンタナロ アスリー

  ブリストル大学計算機科学研究科

• レイモンド ルディー

  日本アイ・ビー・エム(株)東京基礎研究所

• 西村 治道

  大阪府立大学理学系研究科情報数理科学専攻

• 西村 治道

  大阪府立大学

関連論文

• Designing Quantum Game Strategies from Quantum Communication Protocols
• 大学祭でのCSアンプラグド博物館型展示企画の実践
• General scheme for perfect quantum network coding with free classical communication (コンピュテーション)
• 非有界誤り量子質問計算量
• (4, 1)-量子ランダムアクセス符号の非存在について
• 量子ネットワーク上での効率的な情報の伝送(計算理論とアルゴリズムの新展開)
• Transmitting classical information on the quantum network efficiently
• 7.量子通信計算量理論 : 花子から太郎へ(量子コンピュータと量子計算)
• Constructing quantum network coding schemes from classical nonlinear protocols (コンピュテーション)
• On QMA Protocols with Two Short Quantum Proofs (New Trends in Algorithms and Theory of Computation)

スポンサーリンク