| Presentation | 2019-10-25 Fine-grained quantum supremacy based on Orthogonal Vectors, 3-SUM and All-Pairs Shortest Paths Ryu Hayakawa, Tomoyuki Morimae, Suguru Tamaki, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Fine-grained quantum supremacy is a study of excluding possibilities of superpolynomial time classical simulations of quantum computing. We show that under conjectures on Orthogonal Vectors (OV), 3-SUM, All-Pairs Shortest Paths (APSP) and their variants, strong and weak classical simulations of quantum computing are impossible in certain exponential time of the number of qubits. Those conjectures are widely used in classical fine-grained complexity theory in which polynomial time hardnesses are conjectured. All previous results of fine-grained quantum supremacy are based on ETH, SETH, or their variants that are conjectures for SAT in which exponential time hardnesses are conjectured. We show that there exist quantum circuits which cannot be classically simulated in certain exponential time of the number of qubits first by considering the Quantum Random Access Memory (QRAM) based quantum computing model and next by considering the non-QRAM model quantum computation. In the case of the QRAM model, the size of quantum computing is linear in the number of qubits and in the case of the non-QRAM model, the size of the circuit is exponential in the number of qubits but the results are even non-trivial. We only give the proofs for the Theorems on OV on this paper due to the space limitations. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | fine-grained complexity / quantum computation / quantum supremacy |
| Paper # | COMP2019-28 |
| Date of Issue | 2019-10-18 (COMP) |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2019/10/25(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Sapporo Campus, Hokkaido University |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Toshihiro Fujito(Toyohashi Univ. of Tech.) |
| Vice Chair | Shinichi Nakano(Gunma Univ.) |
| Secretary | Shinichi Nakano(Kumamoto Univ) |
| Assistant | Kazuhisa Seto(Seikei Univ.) |
| Paper Information | |
| Registration To | Technical Committee on Theoretical Foundations of Computing |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Fine-grained quantum supremacy based on Orthogonal Vectors, 3-SUM and All-Pairs Shortest Paths |
| Sub Title (in English) | |
| Keyword(1) | fine-grained complexity |
| Keyword(2) | quantum computation |
| Keyword(3) | quantum supremacy |
| 1st Author's Name | Ryu Hayakawa |
| 1st Author's Affiliation | Yukawa Institute for Theoretical Physics, Kyoto University(YITP, Kyoto Univ.) |
| 2nd Author's Name | Tomoyuki Morimae |
| 2nd Author's Affiliation | Yukawa Institute for Theoretical Physics, Kyoto University(YITP, Kyoto Univ.) |
| 3rd Author's Name | Suguru Tamaki |
| 3rd Author's Affiliation | School of Social Information Science, University of Hyogo(School of Social Information Science, Univ. of Hyogo) |
| Date | 2019-10-25 |
| Paper # | COMP2019-28 |
| Volume (vol) | vol.119 |
| Number (no) | COMP-249 |
| Page | pp.pp.71-78(COMP), |
| #Pages | 8 |
| Date of Issue | 2019-10-18 (COMP) |