文献

J-GLOBAL ID：201302243470705854   整理番号：13A1223016

量子対話証明を完全に完全性のあるものにするより強力な手法

Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete

著者 (3件)： KOBAYASHI Hirotada (National Inst. of Informatics) ,  LE GALL Francois (Univ. Tokyo) ,  NISHIMURA Harumichi (Nagoya Univ.)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 113  号： 108(COMP2013 19-24)  ページ： 31-38  発行年： 2013年06月17日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 短報  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： この論文は量子対話証明を完全に完全性のあるものにするより強力な手法を提示する。最初に,QMA(量子Merlin-Arthur)のいかなる問題も,一定の健全性誤りを有する完全に完全性のある2メッセージの量子対話証明システムをもつことを証明する。ここでは,ベリファイアーはEPR対の半分の定数を発信するだけでよい。このことは,特に,完全に完全性のある2メッセージの量子対話証明を持つ問題のクラスQIP1(2)に,クラスQMAが必然的に含まれることを意味する。このことは,QMAに対して,量子対話証明に関する最初の非自明な上限を与える。また,mメッセージ量子対話証明システムを持ついかなる問題も,完全に完全性のある(m+1)メッセージ量子対話証明システムを必然的にもつことを証明する。これは,KitaevとWatrousによるこれまでの結果を改善し,並列化の結果を使用するのでなければ,完全に完全性のある結果としてのシステムはm+2メッセージを必要とすることになる。(翻訳著者抄録)

シソーラス用語： *量子計算 ,  *計算量理論 ,  分類 ,  *証明 ,  完全性 ,  健全性 ,  *メッセージ交換 ,  *コンピュータ ,  *量子コンピュータ
準シソーラス用語： 計算量クラス ,  *対話証明 ,  *量子計算機

分類 (2件)： 計算理論  (JB02000A) ,  その他の計算機  (JC06020B)

タイトルに関連する用語 (5件)： 量子 ,  対話 ,  証明 ,  完全性 ,  手法