Single-qubit gate teleportation provides a quantum advantage

Libor Caha; Xavier Coiteux-Roy; Robert Koenig

doi:10.22331/q-2024-12-04-1548

Single-qubit gate teleportation provides a quantum advantage

Libor Caha, Xavier Coiteux-Roy, and Robert Koenig

School of Computation, Information and Technology, Technical University of Munich, Germany
Munich Center for Quantum Science and Technology, Munich, Germany

Published:	2024-12-04, volume 8, page 1548
Eprint:	arXiv:2209.14158v3
Doi:	https://doi.org/10.22331/q-2024-12-04-1548
Citation:	Quantum 8, 1548 (2024).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

Gate-teleportation circuits are arguably among the most basic examples of computations believed to provide a quantum computational advantage: In seminal work [1], Terhal and DiVincenzo have shown that these circuits elude simulation by efficient classical algorithms under plausible complexity-theoretic assumptions. Here we consider possibilistic simulation [2], 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.

Featured image: Quantum circuit providing a quantum advantage against shallow-depth classical circuits. It consists of a parallel application of gate teleportation.

Popular summary

We compare classical and quantum shallow-depth circuits and show that the latter are strictly more powerful computationally. To this end, we give a computational problem that can be solved by a shallow-depth quantum circuit but that cannot be solved by any shallow-depth classical circuit with bounded fan-in gates. This new unconditional proof of a quantum advantage has two distinguishing features: First, the quantum circuit we use is extremely simple. It is based on a parallel application of gate teleportation, a widely used primitive in quantum computing. Second, our proof technique relies on classical circuit complexity lower bounds rather than on the violation of Bell inequalities typical to previous works. Our work thus provides new insights into the origins of quantum computational power.

► BibTeX data

@article{Caha2024singlequbitgate,
  doi = {10.22331/q-2024-12-04-1548},
  url = {https://doi.org/10.22331/q-2024-12-04-1548},
  title = {Single-qubit gate teleportation provides a quantum advantage},
  author = {Caha, Libor and Coiteux-Roy, Xavier and Koenig, Robert},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {8},
  pages = {1548},
  month = dec,
  year = {2024}
}

► References

[1] Barbara M. Terhal and David P. DiVincenzo. Adaptive quantum computation, constant depth quantum circuits and Arthur-Merlin games. Quantum Information & Computation, 4(2):134–145, 2004. doi:10.26421/QIC4.2-5.
https://doi.org/10.26421/QIC4.2-5

[2] Daochen Wang. Possibilistic simulation of quantum circuits by classical circuits. Phys. Rev. A, 106:062430, Dec 2022. doi:10.1103/PhysRevA.106.062430.
https://doi.org/10.1103/PhysRevA.106.062430

[3] Daniel Gottesman and Isaac Chuang. Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations. Nature, 402(6760):390 – 393, 1999. doi:10.1038/46503.
https://doi.org/10.1038/46503

[4] Sergey Bravyi, David Gosset, and Robert König. Quantum advantage with shallow circuits. Science, 362(6412):308–311, oct 2018. doi:10.1126/science.aar3106.
https://doi.org/10.1126/science.aar3106

[5] Sergey Bravyi, David Gosset, Robert König, and Marco Tomamichel. Quantum advantage with noisy shallow circuits. Nature Physics, 16(10):1040–1045, 2020. doi:10.1038/s41567-020-0948-z.
https://doi.org/10.1038/s41567-020-0948-z

[6] Scott Aaronson. Quantum Computing, Postselection, and Probabilistic Polynomial-Time, Dec 2004. doi:10.48550/arXiv.quant-ph/0412187.
https://doi.org/10.48550/arXiv.quant-ph/0412187
arXiv:quant-ph/0412187

[7] Stephen Fenner, Frederic Green, Steven Homer, and Yong Zhang. Bounds on the Power of Constant-Depth Quantum Circuits. In Fundamentals of Computation Theory, pages 44–55, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg. doi:10.1007/11537311_5.
https://doi.org/10.1007/11537311_5

[8] Maarten Van Den Nes. Classical simulation of quantum computation, the Gottesman-Knill theorem, and slightly beyond. Quantum Information & Computation, 10(3):258–271, 2010. doi:10.26421/QIC10.3-4-6.
https://doi.org/10.26421/QIC10.3-4-6

[9] Michael J. Bremner, Richard Jozsa, and Dan J. Shepherd. Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 467(2126):459–472, 2011. doi:10.1098/rspa.2010.0301.
https://doi.org/10.1098/rspa.2010.0301

[10] Edward Farhi and Aram Wettroth Harrow. Quantum Supremacy through the Quantum Approximate Optimization Algorithm. Technical report: MIT/CTP-4771, 2016. doi:10.48550/arXiv.1602.07674.
https://doi.org/10.48550/arXiv.1602.07674

[11] Scott Aaronson and Alex Arkhipov. The Computational Complexity of Linear Optics. In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, STOC '11, page 333–342, New York, NY, USA, 2011. Association for Computing Machinery. doi:10.1145/1993636.1993682.
https://doi.org/10.1145/1993636.1993682

[12] Daniel Grier and Luke Schaeffer. The classification of Clifford gates over qubits. Quantum, 6:734, Jun 2022. doi:10.22331/q-2022-06-13-734.
https://doi.org/10.22331/q-2022-06-13-734

[13] Daniel Grier and Luke Schaeffer. Interactive shallow Clifford circuits: Quantum advantage against NC$^1$ and beyond. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 875–888, 2020. doi:10.1145/3357713.3384332.
https://doi.org/10.1145/3357713.3384332

[14] Adam Bene Watts, Robin Kothari, Luke Schaeffer, and Avishay Tal. Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, page 515–526, New York, NY, USA, 2019. Association for Computing Machinery. doi:10.1145/3313276.3316404.
https://doi.org/10.1145/3313276.3316404

[15] John F. Clauser, Michael A. Horne, Abner Shimony, and Richard A. Holt. Proposed experiment to test local hidden-variable theories. Physical Review Letters, 23(15):880, 1969. doi:10.1103/PhysRevLett.23.880.
https://doi.org/10.1103/PhysRevLett.23.880

[16] Adam Bene Watts and Natalie Parham. Unconditional Quantum Advantage for Sampling with Shallow Circuits, 2023. doi:10.48550/arXiv.2301.00995.
https://doi.org/10.48550/arXiv.2301.00995

[17] Marc-Olivier Renou, Elisa Bäumer, Sadra Boreiri, Nicolas Brunner, Nicolas Gisin, and Salman Beigi. Genuine quantum nonlocality in the triangle network. Physical Review Letters, 123(14):140401, 2019. doi:10.1103/PhysRevLett.123.140401.
https://doi.org/10.1103/PhysRevLett.123.140401

[18] Scott Aaronson and Daniel Gottesman. Identifying Stabilizer States, 2008. See http://pirsa.org/08080052/.
https://doi.org/10.48660/08080052
http://pirsa.org/08080052/

[19] Ashley Montanaro. Learning stabilizer states by Bell sampling, Jul 2017. doi:10.48550/arXiv.1707.04012.
https://doi.org/10.48550/arXiv.1707.04012

[20] Joe Kilian. Founding cryptography on oblivious transfer. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, STOC '88, page 20–31, New York, NY, USA, 1988. Association for Computing Machinery. doi:10.1145/62212.62215.
https://doi.org/10.1145/62212.62215

[21] David A. Barrington. Bounded-width polynomial-size branching programs recognize exactly those languages in $NC^1$. Journal of Computer and System Sciences, 38(1):150–164, Feb 1989. doi:10.1016/0022-0000(89)90037-8.
https://doi.org/10.1016/0022-0000(89)90037-8

[22] Alexander A. Razborov. Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Mathematical notes of the Academy of Sciences of the USSR, 41:333–338, 1987. doi:10.1007/BF01137685.
https://doi.org/10.1007/BF01137685

[23] Roman Smolensky. Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, STOC '87, page 77–82, New York, NY, USA, 1987. Association for Computing Machinery. doi:10.1145/28395.28404.
https://doi.org/10.1145/28395.28404

[24] David A. Barrington. Width-3 permutation branching programs, technical memorandum tm-293. Technical report, M.I.T. Laboratory for Computer Science, Dec 1985. URL: https://hdl.handle.net/1721.1/149102.
https://hdl.handle.net/1721.1/149102

Cited by

[1] Dilip Paneru, Francesco Di Colandrea, Alessio D'Errico, and Ebrahim Karimi, "Nonlocal transfer of high-dimensional unitary operations", Quantum 9, 1855 (2025).

[2] Libor Caha, Xavier Coiteux-Roy, and Robert Koenig, "3D-local noisy shallow quantum circuits defeat unbounded fan-in classical circuits", Nature Communications 17 1, 8174 (2026).

[3] Adam Bene Watts, David Gosset, Yinchen Liu, and Mehdi Soleimanifar, "Quantum Advantage from Measurement-Induced Entanglement in Random Shallow Circuits", PRX Quantum 6 1, 010356 (2025).

[4] Michael de Oliveira, Luís S. Barbosa, and Ernesto F. Galvão, "Quantum advantage in temporally flat measurement-based quantum computation", Quantum 8, 1312 (2024).

[5] Libor Caha, Xavier Coiteux-Roy, and Robert Koenig, "A colossal advantage: 3D-local noisy shallow quantum circuits defeat unbounded fan-in classical circuits", arXiv:2312.09209, (2023).

[6] Austin K. Daniel and Akimasa Miyake, "Quantum algorithms for classical Boolean functions via adaptive measurements: Exponential reductions in space-time resources", arXiv:2211.01252, (2022).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-17 15:24:35) and SAO/NASA ADS (last updated successfully 2026-08-16 03:23:49). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch ADS cited-by data during last attempt 2026-08-17 15:24:35: cURL error 28: Operation timed out after 10001 milliseconds with 0 bytes received

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.