お知らせ 2023年度・2024年度 学生員 会費割引キャンペーン実施中です
お知らせ 技術研究報告と和文論文誌Ｃの同時投稿施策(掲載料1割引き)について
お知らせ 電子情報通信学会における研究会開催について
お知らせ NEW 参加費の返金について
電子情報通信学会 研究会発表申込システム
講演論文 詳細		 技報閲覧サービス
[ログイン]
技報アーカイブ
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録／キーワード
講演名 2011-11-21 11:00
2つの短い量子証明を用いたQMAプロトコル
ルガル フランソワ（東大）・○中川翔太・西村治道（阪府大）
抄録 （和） この論文では，２つの対数サイズの(互いにもつれていない)量子証明を用いた，3SATに対するQMAプロトコルを与える．このプロトコルの完全性と健全性のギャップは$\Omega(\frac{1}{n\polylog{n}})$である．この結果は，NP完全問題に対するこの設定における，既存の最良の完全性／健全性ギャップを改良する． 
（英） This paper gives a QMA (Quantum Merlin-Arthur) protocol for 3-SAT with two logarithmic-size quantum proofs (that are not entangled with each other) such that the gap between the completeness and the soundness is $\Omega(\frac{1}{n\polylog{n}})$. This improves the best completeness/soundness gaps known for NP-complete problems in this setting.
キーワード （和） 量子計算量 / QMA / 量子もつれ / / / / /  
（英） quantum computational complexity / QMA / entanglement / / / / /  
文献情報 信学技報
資料番号  
発行日  
ISSN  
PDFダウンロード

研究会情報
研究会 QIT  
開催期間 2011-11-21 - 2011-11-22 
開催地（和） 大阪大学基礎工学研究科国際棟 
開催地（英） Osaka Univ. Engr. Sci. Sigma Hall (Toyonaka) 
テーマ（和） 量子情報, 一般 
テーマ（英） Quantum Information, etc. 
講演論文情報の詳細
申込み研究会 QIT 
会議コード 2011-11-QIT 
本文の言語 英語（日本語タイトルあり） 
タイトル（和） 2つの短い量子証明を用いたQMAプロトコル 
サブタイトル（和）  
タイトル（英） On QMA Protocols with Two Short Quantum Proofs 
サブタイトル（英）  
キーワード(1)（和/英） 量子計算量 / quantum computational complexity  
キーワード(2)（和/英） QMA / QMA  
キーワード(3)（和/英） 量子もつれ / entanglement  
キーワード(4)（和/英） /  
キーワード(5)（和/英） /  
キーワード(6)（和/英） /  
キーワード(7)（和/英） /  
キーワード(8)（和/英） /  
第1著者 氏名（和/英/ヨミ） ルガル フランソワ / Francois Le Gall / ルガル フランソワ
第1著者 所属（和/英） 東京大学 (略称： 東大)
The University of Tokyo (略称： Univ. of Tokyo)
第2著者 氏名（和/英/ヨミ） 中川 翔太 / Shota Nakagawa / ナカガワ ショウタ
第2著者 所属（和/英） 大阪府立大学 (略称： 阪府大)
Osaka Prefecture University (略称： Osaka Pref. Univ.)
第3著者 氏名（和/英/ヨミ） 西村 治道 / Harumichi Nishimura / ニシムラ ハルミチ
第3著者 所属（和/英） 大阪府立大学 (略称： 阪府大)
Osaka Prefecture University (略称： Osaka Pref. Univ.)
第4著者 氏名（和/英/ヨミ） / /
第4著者 所属（和/英） (略称： )
(略称： )
第5著者 氏名（和/英/ヨミ） / /
第5著者 所属（和/英） (略称： )
(略称： )
第6著者 氏名（和/英/ヨミ） / /
第6著者 所属（和/英） (略称： )
(略称： )
第7著者 氏名（和/英/ヨミ） / /
第7著者 所属（和/英） (略称： )
(略称： )
第8著者 氏名（和/英/ヨミ） / /
第8著者 所属（和/英） (略称： )
(略称： )
第9著者 氏名（和/英/ヨミ） / /
第9著者 所属（和/英） (略称： )
(略称： )
第10著者 氏名（和/英/ヨミ） / /
第10著者 所属（和/英） (略称： )
(略称： )
第11著者 氏名（和/英/ヨミ） / /
第11著者 所属（和/英） (略称： )
(略称： )
第12著者 氏名（和/英/ヨミ） / /
第12著者 所属（和/英） (略称： )
(略称： )
第13著者 氏名（和/英/ヨミ） / /
第13著者 所属（和/英） (略称： )
(略称： )
第14著者 氏名（和/英/ヨミ） / /
第14著者 所属（和/英） (略称： )
(略称： )
第15著者 氏名（和/英/ヨミ） / /
第15著者 所属（和/英） (略称： )
(略称： )
第16著者 氏名（和/英/ヨミ） / /
第16著者 所属（和/英） (略称： )
(略称： )
第17著者 氏名（和/英/ヨミ） / /
第17著者 所属（和/英） (略称： )
(略称： )
第18著者 氏名（和/英/ヨミ） / /
第18著者 所属（和/英） (略称： )
(略称： )
第19著者 氏名（和/英/ヨミ） / /
第19著者 所属（和/英） (略称： )
(略称： )
第20著者 氏名（和/英/ヨミ） / /
第20著者 所属（和/英） (略称： )
(略称： )
講演者 第2著者 
発表日時 2011-11-21 11:00:00 
発表時間 20分 
申込先研究会 QIT 
資料番号  
巻番号（vol） vol. 
号番号（no）  
ページ範囲  
ページ数  
発行日  

[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]
IEICE / 電子情報通信学会