{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,12]],"date-time":"2025-09-12T19:32:52Z","timestamp":1757705572417,"version":"3.37.3"},"reference-count":24,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2024,12,4]],"date-time":"2024-12-04T00:00:00Z","timestamp":1733270400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000780","name":"European Commission","doi-asserted-by":"crossref","award":["101001976"],"award-info":[{"award-number":["101001976"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001711","name":"Swiss National Science Foundation","doi-asserted-by":"crossref","award":["211123"],"award-info":[{"award-number":["211123"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>Gate-teleportation circuits are arguably among the most basic examples of computations believed to provide a quantum computational advantage: In seminal work \\cite{TerhalDiVincenzo04}, Terhal and DiVincenzo have shown that these circuits elude simulation by efficient classical algorithms under plausible complexity-theoretic assumptions. Here we consider possibilistic simulation \\cite{wang2021possibilistic}, 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.<\/jats:p>","DOI":"10.22331\/q-2024-12-04-1548","type":"journal-article","created":{"date-parts":[[2024,12,4]],"date-time":"2024-12-04T14:33:56Z","timestamp":1733322836000},"page":"1548","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":2,"title":["Single-qubit gate teleportation provides a quantum advantage"],"prefix":"10.22331","volume":"8","author":[{"given":"Libor","family":"Caha","sequence":"first","affiliation":[{"name":"School of Computation, Information and Technology, Technical University of Munich, Germany"},{"name":"Munich Center for Quantum Science and Technology, Munich, Germany"}]},{"given":"Xavier","family":"Coiteux-Roy","sequence":"additional","affiliation":[{"name":"School of Computation, Information and Technology, Technical University of Munich, Germany"},{"name":"Munich Center for Quantum Science and Technology, Munich, Germany"}]},{"given":"Robert","family":"Koenig","sequence":"additional","affiliation":[{"name":"School of Computation, Information and Technology, Technical University of Munich, Germany"},{"name":"Munich Center for Quantum Science and Technology, Munich, Germany"}]}],"member":"9598","published-online":{"date-parts":[[2024,12,4]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Barbara M. Terhal and David P. DiVincenzo. Adaptive quantum computation, constant depth quantum circuits and Arthur-Merlin games. Quantum Information & Computation, 4(2):134\u2013145, 2004. doi:10.26421\/QIC4.2-5.","DOI":"10.26421\/QIC4.2-5"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Daochen Wang. Possibilistic simulation of quantum circuits by classical circuits. Phys. Rev. A, 106:062430, Dec 2022. doi:10.1103\/PhysRevA.106.062430.","DOI":"10.1103\/PhysRevA.106.062430"},{"key":"2","doi-asserted-by":"publisher","unstructured":"Daniel Gottesman and Isaac Chuang. Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations. Nature, 402(6760):390 \u2013 393, 1999. doi:10.1038\/46503.","DOI":"10.1038\/46503"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Sergey Bravyi, David Gosset, and Robert K\u00f6nig. Quantum advantage with shallow circuits. Science, 362(6412):308\u2013311, oct 2018. doi:10.1126\/science.aar3106.","DOI":"10.1126\/science.aar3106"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Sergey Bravyi, David Gosset, Robert K\u00f6nig, and Marco Tomamichel. Quantum advantage with noisy shallow circuits. Nature Physics, 16(10):1040\u20131045, 2020. doi:10.1038\/s41567-020-0948-z.","DOI":"10.1038\/s41567-020-0948-z"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Scott Aaronson. Quantum Computing, Postselection, and Probabilistic Polynomial-Time, Dec 2004. doi:10.48550\/arXiv.quant-ph\/0412187.","DOI":"10.48550\/arXiv.quant-ph\/0412187"},{"key":"6","doi-asserted-by":"publisher","unstructured":"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\u201355, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg. doi:10.1007\/11537311_5.","DOI":"10.1007\/11537311_5"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Maarten Van Den Nes. Classical simulation of quantum computation, the Gottesman-Knill theorem, and slightly beyond. Quantum Information & Computation, 10(3):258\u2013271, 2010. doi:10.26421\/QIC10.3-4-6.","DOI":"10.26421\/QIC10.3-4-6"},{"key":"8","doi-asserted-by":"publisher","unstructured":"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\u2013472, 2011. doi:10.1098\/rspa.2010.0301.","DOI":"10.1098\/rspa.2010.0301"},{"key":"9","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.48550\/arXiv.1602.07674"},{"key":"10","doi-asserted-by":"publisher","unstructured":"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 &apos;11, page 333\u2013342, New York, NY, USA, 2011. Association for Computing Machinery. doi:10.1145\/1993636.1993682.","DOI":"10.1145\/1993636.1993682"},{"key":"11","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.22331\/q-2022-06-13-734"},{"key":"12","doi-asserted-by":"publisher","unstructured":"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\u2013888, 2020. doi:10.1145\/3357713.3384332.","DOI":"10.1145\/3357713.3384332"},{"key":"13","doi-asserted-by":"publisher","unstructured":"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\u2013526, New York, NY, USA, 2019. Association for Computing Machinery. doi:10.1145\/3313276.3316404.","DOI":"10.1145\/3313276.3316404"},{"key":"14","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevLett.23.880"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Adam Bene Watts and Natalie Parham. Unconditional Quantum Advantage for Sampling with Shallow Circuits, 2023. doi:10.48550\/arXiv.2301.00995.","DOI":"10.48550\/arXiv.2301.00995"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Marc-Olivier Renou, Elisa B\u00e4umer, 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.","DOI":"10.1103\/PhysRevLett.123.140401"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Scott Aaronson and Daniel Gottesman. Identifying Stabilizer States, 2008. See http:\/\/pirsa.org\/08080052\/.","DOI":"10.48660\/08080052"},{"key":"18","doi-asserted-by":"publisher","unstructured":"Ashley Montanaro. Learning stabilizer states by Bell sampling, Jul 2017. doi:10.48550\/arXiv.1707.04012.","DOI":"10.48550\/arXiv.1707.04012"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Joe Kilian. Founding cryptography on oblivious transfer. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, STOC &apos;88, page 20\u201331, New York, NY, USA, 1988. Association for Computing Machinery. doi:10.1145\/62212.62215.","DOI":"10.1145\/62212.62215"},{"key":"20","doi-asserted-by":"publisher","unstructured":"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\u2013164, Feb 1989. doi:10.1016\/0022-0000(89)90037-8.","DOI":"10.1016\/0022-0000(89)90037-8"},{"key":"21","doi-asserted-by":"publisher","unstructured":"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\u2013338, 1987. doi:10.1007\/BF01137685.","DOI":"10.1007\/BF01137685"},{"key":"22","doi-asserted-by":"publisher","unstructured":"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 &apos;87, page 77\u201382, New York, NY, USA, 1987. Association for Computing Machinery. doi:10.1145\/28395.28404.","DOI":"10.1145\/28395.28404"},{"key":"23","unstructured":"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."}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-12-04-1548\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,12,4]],"date-time":"2024-12-04T14:34:21Z","timestamp":1733322861000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-12-04-1548\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,4]]},"references-count":24,"URL":"https:\/\/doi.org\/10.22331\/q-2024-12-04-1548","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"type":"electronic","value":"2521-327X"}],"subject":[],"published":{"date-parts":[[2024,12,4]]},"article-number":"1548"}}