Single-qubit gate teleportation provides a quantum advantage
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912143991898112 |
|---|---|
| author | Caha, Libor Coiteux-Roy, Xavier Koenig, Robert |
| author_facet | Caha, Libor Coiteux-Roy, Xavier Koenig, Robert |
| contents | Gate-teleportation circuits are arguably among the most basic examples of computations believed to provide a quantum computational advantage: In seminal work [Quantum Inf. Comput., 4(2):134--145], Terhal and DiVincenzo have shown that these circuits elude simulation by efficient classical algorithms under plausible complexity-theoretic assumptions. Here we consider possibilistic simulation [Phys. Rev. A 106, 062430 (2022)], a particularly weak form of this task where the goal is to output any string appearing with non-zero probability in the output distribution of the circuit. We show that even for single-qubit Clifford-gate-teleportation circuits this simulation problem cannot be solved by constant-depth classical circuits with bounded fan-in gates. Our results are unconditional and are obtained by a reduction to the problem of computing the parity, a well-studied problem in classical circuit complexity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2209_14158 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Single-qubit gate teleportation provides a quantum advantage Caha, Libor Coiteux-Roy, Xavier Koenig, Robert Quantum Physics Gate-teleportation circuits are arguably among the most basic examples of computations believed to provide a quantum computational advantage: In seminal work [Quantum Inf. Comput., 4(2):134--145], Terhal and DiVincenzo have shown that these circuits elude simulation by efficient classical algorithms under plausible complexity-theoretic assumptions. Here we consider possibilistic simulation [Phys. Rev. A 106, 062430 (2022)], a particularly weak form of this task where the goal is to output any string appearing with non-zero probability in the output distribution of the circuit. We show that even for single-qubit Clifford-gate-teleportation circuits this simulation problem cannot be solved by constant-depth classical circuits with bounded fan-in gates. Our results are unconditional and are obtained by a reduction to the problem of computing the parity, a well-studied problem in classical circuit complexity. |
| title | Single-qubit gate teleportation provides a quantum advantage |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2209.14158 |