| Presentation | 2021-12-03 Computational Power of Shallow Quantum Circuits with Fan-out Gates Ryoga Araki, Akinori Kawachi, Francois Le Gall, Ansis Rosmanis, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Quantum computers are expected to solve some problems much faster than classical computers. However, today's quantum computers have some error probabilities in the execution. It is desirable to implement the algorithm by shallow quantum circuits to correctly execute them with high probability. Hoyer and Spalek showed the shallow quantum circuits with Fan-out gates are unexpectedly powerful so that they can compute the $n$-bit OR function with bounded Fan-in gates in constant depth.Takahashi and Tani showed that the functions computed by constant-depth quantum threshold circuits are equivalent with those of constant-depth quantum circuits with the Fan-out gates by constructing a circuit computing the Hamming weight of the inputs. We can compute every symmetric function by combining their circuit and the standard method. We propose quantum circuits of smaller size for every symmetric function and consider the expansion to computing multilinear polynomials and determinants of the matrices. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | shallow quantum circuits / Fan-out gates / symmetric functions / determinant |
| Paper # | COMP2021-26 |
| Date of Issue | 2021-11-26 (COMP) |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2021/12/3(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Kanazawa Chamber of Commerce and Industry |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Toshimitsu Masuzawa(Osaka Univ.) |
| Vice Chair | Hirotaka Ono(Nagoya Univ) |
| Secretary | Hirotaka Ono(NAIST) |
| Assistant | Yota Otachi(Nagoya 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) | Computational Power of Shallow Quantum Circuits with Fan-out Gates |
| Sub Title (in English) | |
| Keyword(1) | shallow quantum circuits |
| Keyword(2) | Fan-out gates |
| Keyword(3) | symmetric functions |
| Keyword(4) | determinant |
| 1st Author's Name | Ryoga Araki |
| 1st Author's Affiliation | Mie University(Mie Univ.) |
| 2nd Author's Name | Akinori Kawachi |
| 2nd Author's Affiliation | Mie University(Mie Univ.) |
| 3rd Author's Name | Francois Le Gall |
| 3rd Author's Affiliation | Nagoya University(Nagoya Univ.) |
| 4th Author's Name | Ansis Rosmanis |
| 4th Author's Affiliation | Nagoya University(Nagoya Univ.) |
| Date | 2021-12-03 |
| Paper # | COMP2021-26 |
| Volume (vol) | vol.121 |
| Number (no) | COMP-285 |
| Page | pp.pp.24-29(COMP), |
| #Pages | 6 |
| Date of Issue | 2021-11-26 (COMP) |