| Presentation | 2001/9/7 On Quantum Algorithms for the Collision Problem Seiya OKUBO, Tetsuro NISHINO, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | collision problem / quantum algorithm / Grover's algorithm / quantum complexity |
| Paper # | COMP2001-35 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2001/9/7(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | On Quantum Algorithms for the Collision Problem |
| Sub Title (in English) | |
| Keyword(1) | collision problem |
| Keyword(2) | quantum algorithm |
| Keyword(3) | Grover's algorithm |
| Keyword(4) | quantum complexity |
| 1st Author's Name | Seiya OKUBO |
| 1st Author's Affiliation | Graduate School of Electro-Communications, The University of Electro-Communications() |
| 2nd Author's Name | Tetsuro NISHINO |
| 2nd Author's Affiliation | Department of Information and Communication Engineering, The University of Electro-Communications |
| Date | 2001/9/7 |
| Paper # | COMP2001-35 |
| Volume (vol) | vol.101 |
| Number (no) | 307 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |