{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,24]],"date-time":"2026-02-24T03:19:07Z","timestamp":1771903147676,"version":"3.50.1"},"reference-count":47,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2024,5,6]],"date-time":"2024-05-06T00:00:00Z","timestamp":1714953600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"ANR","award":["ANR-22-PETQ- 0006"],"award-info":[{"award-number":["ANR-22-PETQ- 0006"]}]},{"name":"ANR","award":["HQI ANR-22-PNCQ-0002"],"award-info":[{"award-number":["HQI ANR-22-PNCQ-0002"]}]},{"DOI":"10.13039\/100012950","name":"Inria","doi-asserted-by":"crossref","award":["Inria EQIP challenge."],"award-info":[{"award-number":["Inria EQIP challenge."]}],"id":[{"id":"10.13039\/100012950","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"Between NISQ (noisy intermediate scale quantum) approaches without any proof of robust quantum advantage and fully fault-tolerant quantum computation, we propose a scheme to achieve a provable superpolynomial quantum advantage (under some widely accepted complexity conjectures) that is robust to noise with minimal error correction requirements. We choose a class of sampling problems with commuting gates known as sparse IQP (Instantaneous Quantum Polynomial-time) circuits and we ensure its fault-tolerant implementation by introducing the tetrahelix code. This new code is obtained by merging several tetrahedral codes (3D color codes) and has the following properties: each sparse IQP gate admits a transversal implementation, and the depth of the logical circuit can be traded for its width. Combining those, we obtain a depth-1 implementation of any sparse IQP circuit up to the preparation of encoded states. This comes at the cost of a space overhead which is only polylogarithmic in the width of the original circuit. We furthermore show that the state preparation can also be performed in constant depth with a single step of feed-forward from classical computation. Our construction thus exhibits a robust superpolynomial quantum advantage for a sampling problem implemented on a constant depth circuit with a single round of measurement and feed-forward.<\/jats:p>","DOI":"10.22331\/q-2024-05-06-1337","type":"journal-article","created":{"date-parts":[[2024,5,6]],"date-time":"2024-05-06T14:25:22Z","timestamp":1715005522000},"page":"1337","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":8,"title":["Robust sparse IQP sampling in constant depth"],"prefix":"10.22331","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-3921-0404","authenticated-orcid":false,"given":"Louis","family":"Paletta","sequence":"first","affiliation":[{"name":"Laboratoire de Physique de l'Ecole normale sup\u00e9rieure, ENS-PSL, CNRS, Inria, Centre Automatique et Syst\u00e8mes (CAS), Mines Paris, Universit\u00e9 PSL, Sorbonne Universit\u00e9, Universit\u00e9 Paris Cit\u00e9, Paris, France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6707-1458","authenticated-orcid":false,"given":"Anthony","family":"Leverrier","sequence":"additional","affiliation":[{"name":"Inria Paris, France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5909-437X","authenticated-orcid":false,"given":"Alain","family":"Sarlette","sequence":"additional","affiliation":[{"name":"Laboratoire de Physique de l'Ecole normale sup\u00e9rieure, ENS-PSL, CNRS, Inria, Centre Automatique et Syst\u00e8mes (CAS), Mines Paris, Universit\u00e9 PSL, Sorbonne Universit\u00e9, Universit\u00e9 Paris Cit\u00e9, Paris, France"},{"name":"Department of Electronics and Information Systems, Ghent University, Belgium"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9471-6031","authenticated-orcid":false,"given":"Mazyar","family":"Mirrahimi","sequence":"additional","affiliation":[{"name":"Laboratoire de Physique de l'Ecole normale sup\u00e9rieure, ENS-PSL, CNRS, Inria, Centre Automatique et Syst\u00e8mes (CAS), Mines Paris, Universit\u00e9 PSL, Sorbonne Universit\u00e9, Universit\u00e9 Paris Cit\u00e9, Paris, France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3445-0179","authenticated-orcid":false,"given":"Christophe","family":"Vuillot","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France"}]}],"member":"9598","published-online":{"date-parts":[[2024,5,6]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Austin P Lund, Michael J Bremner, and Timothy C Ralph. ``Quantum sampling problems, bosonsampling and quantum supremacy''. npj Quantum Information 3, 1\u20138 (2017).","DOI":"10.1038\/s41534-017-0018-2"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Ramis Movassagh. ``The hardness of random quantum circuits''. Nature Physics 19, 1719\u20131724 (2023).","DOI":"10.1038\/s41567-023-02131-2"},{"key":"2","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. Pages 333\u2013342. (2011).","DOI":"10.1145\/1993636.1993682"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Adam Bouland, Bill Fefferman, Chinmay Nirkhe, and Umesh Vazirani. ``On the complexity and verification of quantum random circuit sampling''. Nature Physics 15, 159\u2013163 (2019).","DOI":"10.1038\/s41567-018-0318-2"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Dan Shepherd and Michael J Bremner. ``Temporally unstructured quantum computation''. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 465, 1413\u20131439 (2009).","DOI":"10.1098\/rspa.2008.0443"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Dorit Aharonov, Xun Gao, Zeph Landau, Yunchao Liu, and Umesh Vazirani. ``A polynomial-time classical algorithm for noisy random circuit sampling''. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing. Pages 945\u2013957. (2023).","DOI":"10.1145\/3564246.3585234"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Yiqing Zhou, E Miles Stoudenmire, and Xavier Waintal. ``What limits the simulation of quantum computers?''. Physical Review X 10, 041038 (2020).","DOI":"10.1103\/PhysRevX.10.041038"},{"key":"7","doi-asserted-by":"publisher","unstructured":"John C Napp, Rolando L La Placa, Alexander M Dalzell, Fernando GSL Brandao, and Aram W Harrow. ``Efficient classical simulation of random shallow 2d quantum circuits''. Physical Review X 12, 021021 (2022).","DOI":"10.1103\/PhysRevX.12.021021"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Xun Gao, Marcin Kalinowski, Chi-Ning Chou, Mikhail D Lukin, Boaz Barak, and Soonwon Choi. ``Limitations of linear cross-entropy as a measure for quantum advantage''. PRX Quantum 5, 010334 (2024).","DOI":"10.1103\/PRXQuantum.5.010334"},{"key":"9","unstructured":"Bill Fefferman, Soumik Ghosh, Michael Gullans, Kohdai Kuroiwa, and Kunal Sharma. ``Effect of non-unital noise on random circuit sampling'' (2023). arXiv:2306.16659."},{"key":"10","doi-asserted-by":"publisher","unstructured":"John Preskill. ``Quantum computing in the nisq era and beyond''. Quantum 2, 79 (2018).","DOI":"10.22331\/q-2018-08-06-79"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Bryan Eastin and Emanuel Knill. ``Restrictions on transversal encoded quantum gate sets''. Physical Review Letters 102, 110502 (2009).","DOI":"10.1103\/PhysRevLett.102.110502"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Rawad Mezher, Joe Ghalbouni, Joseph Dgheim, and Damian Markham. ``Fault-tolerant quantum speedup from constant depth quantum circuits''. Physical Review Research 2, 033444 (2020).","DOI":"10.1103\/PhysRevResearch.2.033444"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Craig Gidney and Martin Eker\u00e5. ``How to factor 2048 bit rsa integers in 8 hours using 20 million noisy qubits''. Quantum 5, 433 (2021).","DOI":"10.22331\/q-2021-04-15-433"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Sergey Bravyi, David Gosset, Robert Koenig, and Marco Tomamichel. ``Quantum advantage with noisy shallow circuits''. Nature Physics 16, 1040\u20131045 (2020).","DOI":"10.1038\/s41567-020-0948-z"},{"key":"15","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, 459\u2013472 (2011).","DOI":"10.1098\/rspa.2010.0301"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Michael J Bremner, Ashley Montanaro, and Dan J Shepherd. ``Average-case complexity versus approximate simulation of commuting quantum computations''. Physical Review Letters 117, 080501 (2016).","DOI":"10.1103\/PhysRevLett.117.080501"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Michael J Bremner, Ashley Montanaro, and Dan J Shepherd. ``Achieving quantum supremacy with sparse and noisy commuting quantum computations''. Quantum 1, 8 (2017).","DOI":"10.22331\/q-2017-04-25-8"},{"key":"18","doi-asserted-by":"publisher","unstructured":"Leslie Ann Goldberg and Heng Guo. ``The complexity of approximating complex-valued ising and tutte partition functions''. computational complexity 26, 765\u2013833 (2017).","DOI":"10.1007\/s00037-017-0162-2"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Keisuke Fujii and Tomoyuki Morimae. ``Commuting quantum circuits and complexity of ising partition functions''. New Journal of Physics 19, 033003 (2017).","DOI":"10.1088\/1367-2630\/aa5fdb"},{"key":"20","doi-asserted-by":"crossref","unstructured":"Daniel Gottesman. ``Fault-tolerant quantum computation with constant overhead'' (2014). arXiv:1310.2984.","DOI":"10.26421\/QIC14.15-16-5"},{"key":"21","doi-asserted-by":"publisher","unstructured":"Peter H\u00f8yer and Robert \u0160palek. ``Quantum fan-out is powerful''. Theory of computing 1, 81\u2013103 (2005).","DOI":"10.4086\/toc.2005.v001a005"},{"key":"22","doi-asserted-by":"publisher","unstructured":"Dorit Aharonov and Michael Ben-Or. ``Fault-tolerant quantum computation with constant error''. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing. Pages 176\u2013188. (1997).","DOI":"10.1137\/S0097539799359385"},{"key":"23","doi-asserted-by":"publisher","unstructured":"Emanuel Knill, Raymond Laflamme, and Wojciech H Zurek. ``Resilient quantum computation''. Science 279, 342\u2013345 (1998).","DOI":"10.1126\/science.279.5349.342"},{"key":"24","doi-asserted-by":"publisher","unstructured":"Hector Bombin and Miguel-Angel Martin-Delgado. ``Topological computation without braiding''. Physical Review Letters 98, 160502 (2007).","DOI":"10.1103\/PhysRevLett.98.160502"},{"key":"25","doi-asserted-by":"publisher","unstructured":"Aleksander Kubica and Michael E Beverland. ``Universal transversal gates with color codes: A simplified approach''. Physical Review A 91, 032330 (2015).","DOI":"10.1103\/PhysRevA.91.032330"},{"key":"26","doi-asserted-by":"publisher","unstructured":"A Robert Calderbank and Peter W Shor. ``Good quantum error-correcting codes exist''. Physical Review A 54, 1098 (1996).","DOI":"10.1103\/PhysRevA.54.1098"},{"key":"27","doi-asserted-by":"publisher","unstructured":"Andrew M Steane. ``Error correcting codes in quantum theory''. Physical Review Letters 77, 793 (1996).","DOI":"10.1103\/PhysRevLett.77.793"},{"key":"28","doi-asserted-by":"publisher","unstructured":"Clare Horsman, Austin G Fowler, Simon Devitt, and Rodney Van Meter. ``Surface code quantum computing by lattice surgery''. New Journal of Physics 14, 123011 (2012).","DOI":"10.1088\/1367-2630\/14\/12\/123011"},{"key":"29","doi-asserted-by":"publisher","unstructured":"Daniel Litinski. ``A game of surface codes: Large-scale quantum computing with lattice surgery''. Quantum 3, 128 (2019).","DOI":"10.22331\/q-2019-03-05-128"},{"key":"30","unstructured":"Andrew J. Landahl and Ciaran Ryan-Anderson. ``Quantum computing by color-code lattice surgery'' (2014). arXiv:1407.5103."},{"key":"31","doi-asserted-by":"publisher","unstructured":"H\u00e9ctor Bomb\u00edn. ``Single-shot fault-tolerant quantum error correction''. Physical Review X 5, 031043 (2015).","DOI":"10.1103\/PhysRevX.5.031043"},{"key":"32","doi-asserted-by":"publisher","unstructured":"H\u00e9ctor Bomb\u00edn. ``Gauge color codes: optimal transversal gates and gauge fixing in topological stabilizer codes''. New Journal of Physics 17, 083002 (2015).","DOI":"10.1088\/1367-2630\/17\/8\/083002"},{"key":"33","doi-asserted-by":"publisher","unstructured":"H Bombin and MA Martin-Delgado. ``Exact topological quantum order in d= 3 and beyond: Branyons and brane-net condensates''. Physical Review B 75, 075103 (2007).","DOI":"10.1103\/PhysRevB.75.075103"},{"key":"34","doi-asserted-by":"publisher","unstructured":"Hector Bombin and Miguel Angel Martin-Delgado. ``Topological quantum distillation''. Physical Review Letters 97, 180501 (2006).","DOI":"10.1103\/PhysRevLett.97.180501"},{"key":"35","doi-asserted-by":"publisher","unstructured":"Christophe Vuillot. ``Fault-tolerant quantum computation: Theory and practice''. PhD thesis. TU Delft. (2020).","DOI":"10.4233\/uuid:7cb715f4-eaf0-4526-8552-9f97cc864383"},{"key":"36","unstructured":"AH Boerdijk. ``Some remarks concerning close-packing of equal spheres''. Philips Research Reports 7, 303\u2013313 (1952)."},{"key":"37","doi-asserted-by":"publisher","unstructured":"HSM Coxeter and JM Wills. ``Regular complex polytopes''. Jahresbericht der Deutschen Mathematiker Vereinigung 96, 2\u20132 (1994).","DOI":"10.2307\/1575843"},{"key":"38","doi-asserted-by":"publisher","unstructured":"Christopher Chamberland, Aleksander Kubica, Theodore J Yoder, and Guanyu Zhu. ``Triangular color codes on trivalent graphs with flag qubits''. New Journal of Physics 22, 023019 (2020).","DOI":"10.1088\/1367-2630\/ab68fd"},{"key":"39","doi-asserted-by":"publisher","unstructured":"Kaavya Sahay and Benjamin J Brown. ``Decoder for the triangular color code by matching on a m\u00f6bius strip''. PRX Quantum 3, 010310 (2022).","DOI":"10.1103\/PRXQuantum.3.010310"},{"key":"40","doi-asserted-by":"publisher","unstructured":"Aleksander Kubica and Nicolas Delfosse. ``Efficient color code decoders in $d \\ge 2$ dimensions from toric code decoders''. Quantum 7, 929 (2023).","DOI":"10.22331\/q-2023-02-21-929"},{"key":"41","doi-asserted-by":"publisher","unstructured":"Michael E Beverland, Aleksander Kubica, and Krysta M Svore. ``Cost of universality: A comparative study of the overhead of state distillation and code switching with color codes''. PRX Quantum 2, 020341 (2021).","DOI":"10.1103\/PRXQuantum.2.020341"},{"key":"42","unstructured":"Hector Bombin. ``Transversal gates and error propagation in 3d topological codes'' (2018). arXiv:1810.09575."},{"key":"43","doi-asserted-by":"publisher","unstructured":"Dan Browne, Elham Kashefi, and Simon Perdrix. ``Computational depth complexity of measurement-based quantum computation''. In Theory of Quantum Computation, Communication, and Cryptography: 5th Conference, TQC 2010, Leeds, UK, April 13-15, 2010, Revised Selected Papers 5. Pages 35\u201346. Springer (2011).","DOI":"10.1007\/978-3-642-18073-6_4"},{"key":"44","unstructured":"Keisuke Fujii. ``Noise threshold of quantum supremacy'' (2016). arXiv:1610.03632."},{"key":"45","doi-asserted-by":"publisher","unstructured":"Dolev Bluvstein, Simon J Evered, Alexandra A Geim, Sophie H Li, Hengyun Zhou, Tom Manovitz, Sepehr Ebadi, Madelyn Cain, Marcin Kalinowski, Dominik Hangleiter, et al. ``Logical quantum processor based on reconfigurable atom arrays''. Nature 626, 58\u201365 (2024).","DOI":"10.1038\/s41586-023-06927-3"},{"key":"46","unstructured":"Gregoire de Gliniasty, Rawad Mezher, and Damian Markham. In preparation."}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-05-06-1337\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,5,6]],"date-time":"2024-05-06T14:25:30Z","timestamp":1715005530000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-05-06-1337\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,6]]},"references-count":47,"URL":"https:\/\/doi.org\/10.22331\/q-2024-05-06-1337","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,6]]},"article-number":"1337"}}