| 講演名 | 2001/9/7 衝突問題に対する量子アルゴリズムについて 大久保 誠也, 西野 哲朗, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 量子計算は, Turing機械がモデルである古典計算よりも効率的である可能性が指摘されている.そのようなアルゴリズムとして, 因数分解を小さな誤り確率で高速に行うShorのアルゴリズムや, 検索問題を効率的に解くGroverのアルゴリズムが知られている.本論では, 暗号分野で重要な衝突問題(collision problem)を取りあげる.ここで, 衝突とはf(x)=f(y)を満たす組(x, y)のことである.本論では, 論文[4]で示された衝突問題のアルゴリズムで使われているソーティングのアルゴリズムを変更することにより, アルゴリズム全体の計算量にどのような変化が生じるかを考察する. |
| 抄録(英) | It is believed that quantum computations are more efficient than classical computations based on Turing machines because of the efficiency of Shor's factorization algorithm or Grover's quantum searching algorithm. On the other hand, an efficient quantum algorithm for the collision problem is known. Here, a collision is a two distinct element pair (x, y) such that f(x)=f(y) for a given function f. This problem is very important in the field of cryptography. In this paper, we observe the relationships between the types of sorting algorithms used in the above quantum algorithm for the collision problem and the computational complexity of this quantum algorithm. |
| キーワード(和) | 衝突問題 / 量子アルゴリズム / Groverのアルゴリズム / 量子計算量 |
| キーワード(英) | collision problem / quantum algorithm / Grover's algorithm / quantum complexity |
| 資料番号 | COMP2001-35 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2001/9/7(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 衝突問題に対する量子アルゴリズムについて |
| サブタイトル（和） | |
| タイトル（英） | On Quantum Algorithms for the Collision Problem |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 衝突問題 / collision problem |
| キーワード(2)（和/英） | 量子アルゴリズム / quantum algorithm |
| キーワード(3)（和/英） | Groverのアルゴリズム / Grover's algorithm |
| キーワード(4)（和/英） | 量子計算量 / quantum complexity |
| 第 1 著者 氏名（和/英） | 大久保 誠也 / Seiya OKUBO |
| 第 1 著者 所属（和/英） | 電気通信大学電気通信学研究科 Graduate School of Electro-Communications, The University of Electro-Communications |
| 第 2 著者 氏名（和/英） | 西野 哲朗 / Tetsuro NISHINO |
| 第 2 著者 所属（和/英） | 電気通信大学情報通信工学科 Department of Information and Communication Engineering, The University of Electro-Communications |
| 発表年月日 | 2001/9/7 |
| 資料番号 | COMP2001-35 |
| 巻番号（vol） | vol.101 |
| 号番号（no） | 307 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |