| 講演名 | 1999/7/16 ナップサック問題の量子アルゴリズム 鈴野 聡志, 増田 夏樹, 大矢 雅則, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 量子コンピュータとは, 量子力学を動作原理とするコンピュータのことである. 現在のコンピュータに比べ, 量子状態の干渉性を用いて計算を高速にでき, 発熱を少なくできるなどの特徴を持ち, 次世代のコンピュータとして期待されている. ナップサック問題とはNP完全に属する問題で, 現在のコンピュータでは効率よく解くアルゴリズムは見つかっていない. 本論文では, 量子コンピュータが高速に計算できる証明とし, ナップサック問題の量子アルゴリズムを述べ, quピットを表現する重ね合わせ状態ができれば, ナップサック問題が多項式時間で解けることを示す. |
| 抄録(英) | Quantum computer is a computer based on quantum dynamics. More precisely, the quantum coherence of states is used for quantum computation, which enables the computation with much higher speed compared with digital computer. Knapsack problem belongs to class of NP-complete and its effective algorithm has not been found yet. In this paper, we discuss the quantum algorithm of the knapsack problem and show that it can be solved in polynomial time if the qu-bit., i. e. the superposition of pure states is detected. |
| キーワード(和) | 量子アルゴリズム / ナップサック問題 / NP完全 |
| キーワード(英) | quantum algorithm / knapsack problem / NP-complete |
| 資料番号 | IT99-23 |
| 発行日 |
| 研究会情報 | |
| 研究会 | IT |
|---|---|
| 開催期間 | 1999/7/16(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Information Theory (IT) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | ナップサック問題の量子アルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | Quantum algorithm of knapsack problem |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 量子アルゴリズム / quantum algorithm |
| キーワード(2)（和/英） | ナップサック問題 / knapsack problem |
| キーワード(3)（和/英） | NP完全 / NP-complete |
| 第 1 著者 氏名（和/英） | 鈴野 聡志 / Satoshi Suzuno |
| 第 1 著者 所属（和/英） | 東京理科大学理工学部情報科学科 Department of Information Sciences Faculty of Science and Technology Science University of Tokyo |
| 第 2 著者 氏名（和/英） | 増田 夏樹 / Natsuki Masuda |
| 第 2 著者 所属（和/英） | 東京理科大学理工学部情報科学科 Department of Information Sciences Faculty of Science and Technology Science University of Tokyo |
| 第 3 著者 氏名（和/英） | 大矢 雅則 / Masanori Ohya |
| 第 3 著者 所属（和/英） | 東京理科大学理工学部情報科学科 Department of Information Sciences Faculty of Science and Technology Science University of Tokyo |
| 発表年月日 | 1999/7/16 |
| 資料番号 | IT99-23 |
| 巻番号（vol） | vol.99 |
| 号番号（no） | 187 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |