講演名 | 1996/10/31 誤り限定量子Turing機械の計算能力について 西野 哲朗, |
---|---|
PDFダウンロードページ | PDFダウンロードページへ |
抄録(和) | 本論文では, ある種の誤り限定量子Turing機械で多項式時間内に受理できる言語のクラス C⊆BQPを導入する. そして, クラス CがいかなるNP完全言語も含まないと思われる強い状況証拠を, 回路計算量理論の手法を用いて示す. |
抄録(英) | In this paper, we introduce a class C⊆BQP of languages which can be accepted by a certain kind of bounded error quantum Turing machines in polynomial time. Then we show a strong evidence that C cannot include any NP-complete language by using a method of circuit complexity theory. |
キーワード(和) | 量子計算量理論 / 回路計算量理論 / BQP / BPP / NP |
キーワード(英) | quantum complexity theory / circuit complexity theory / BQP / BPP / NP |
資料番号 | COMP96-36 |
発行日 |
研究会情報 | |
研究会 | COMP |
---|---|
開催期間 | 1996/10/31(から1日開催) |
開催地(和) | |
開催地(英) | |
テーマ(和) | |
テーマ(英) | |
委員長氏名(和) | |
委員長氏名(英) | |
副委員長氏名(和) | |
副委員長氏名(英) | |
幹事氏名(和) | |
幹事氏名(英) | |
幹事補佐氏名(和) | |
幹事補佐氏名(英) |
講演論文情報詳細 | |
申込み研究会 | Theoretical Foundations of Computing (COMP) |
---|---|
本文の言語 | ENG |
タイトル(和) | 誤り限定量子Turing機械の計算能力について |
サブタイトル(和) | |
タイトル(英) | On the Computational Power of Some Bounded Error Quantum Turing Machines |
サブタイトル(和) | |
キーワード(1)(和/英) | 量子計算量理論 / quantum complexity theory |
キーワード(2)(和/英) | 回路計算量理論 / circuit complexity theory |
キーワード(3)(和/英) | BQP / BQP |
キーワード(4)(和/英) | BPP / BPP |
キーワード(5)(和/英) | NP / NP |
第 1 著者 氏名(和/英) | 西野 哲朗 / Tetsuro Nishino |
第 1 著者 所属(和/英) | 電気通信大学電子情報学科 The University of Electro-Communications |
発表年月日 | 1996/10/31 |
資料番号 | COMP96-36 |
巻番号(vol) | vol.96 |
号番号(no) | 343 |
ページ範囲 | pp.- |
ページ数 | 6 |
発行日 |