| 講演名 | 2014-03-10 DQC1モデルの古典シミレーション困難性について 森前 智行, 藤井 啓祐 /, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | |
| 抄録(英) | Deterministic quantum computation with one quantum bit (DQC1) is a model of quantum computing where the input restricted to containing a single qubit in a pure state and with all other qubits in a completely-mixed state, with only a single qubit measurement at the end of the computation [E. Knill and R. Laflamme, Phys. Rev. Lett. 81, 5672 (1998)]. While it is known that DQC1 can efficiently solve several problems for which no known classical efficient algorithms exist, the question of whether DQC1 is really more powerful than classical computation remains open. In this paper, we introduce a slightly modified version of DQC1, which we call DQC1_k, where k output qubits are measured, and show that DQC1_k cannot be classically efficiently simulated for any k ≧ 3 unless the polynomial hierarchy collapses at the third level. |
| キーワード(和) | 量子計算 |
| キーワード(英) | |
| 資料番号 | COMP2013-62 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2014/3/3(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | DQC1モデルの古典シミレーション困難性について |
| サブタイトル（和） | |
| タイトル（英） | On the hardness of the classical simulation of the DQC1 model |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 量子計算 |
| 第 1 著者 氏名（和/英） | 森前 智行 / Tomoyuki MORIMAE |
| 第 1 著者 所属（和/英） | 群馬大学先端ユニット ASRLD Unit, Gunma University |
| 第 2 著者 氏名（和/英） | 藤井 啓祐 / / Keisuke FUJII |
| 第 2 著者 所属（和/英） | 京都大学白眉センター:京都大学大学院情輯学研究科 / The Hakubi Center for Advance Research, Kyoto University:Graduate School of Informatics, Kyoto University |
| 発表年月日 | 2014-03-10 |
| 資料番号 | COMP2013-62 |
| 巻番号（vol） | vol.113 |
| 号番号（no） | 488 |
| ページ範囲 | pp.- |
| ページ数 | 5 |
| 発行日 | |