{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T01:43:33Z","timestamp":1787017413867,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":31,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100014718","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1122374"],"award-info":[{"award-number":["1122374"]}],"id":[{"id":"10.13039\/100014718","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384332","type":"proceedings-article","created":{"date-parts":[[2020,6,6]],"date-time":"2020-06-06T21:45:25Z","timestamp":1591479925000},"page":"875-888","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Interactive shallow Clifford circuits: Quantum advantage against NC\u00b9 and beyond"],"prefix":"10.1145","author":[{"given":"Daniel","family":"Grier","sequence":"first","affiliation":[{"name":"University of Waterloo, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Luke","family":"Schaeffer","sequence":"additional","affiliation":[{"name":"University of Waterloo, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993682"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/800057.808715"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/48014.63138"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316404"},{"key":"e_1_3_2_1_5_1","first-page":"96","volume":"10","author":"Bennett Charles H.","unstructured":"Charles H. Bennett and John Gill . Relative to a random oracle A, PA, NPA , coNPA with probability 1. SIAM Journal on Computing , 10 ( 1 ): 96 - 113 , 1981. Charles H. Bennett and John Gill. Relative to a random oracle A, PA, NPA, coNPA with probability 1. SIAM Journal on Computing, 10 ( 1 ): 96-113, 1981.","journal-title":"Computing"},{"key":"e_1_3_2_1_6_1","volume-title":"Characterizing quantum supremacy in near-term devices. Nature Physics, 14 ( 6 ): 595","author":"Boixo Sergio","year":"2018","unstructured":"Sergio Boixo , Sergei V Isakov , Vadim N Smelyanskiy , Ryan Babbush , Nan Ding , Zhang Jiang , Michael J Bremner , John M Martinis , and Hartmut Neven . Characterizing quantum supremacy in near-term devices. Nature Physics, 14 ( 6 ): 595 , 2018 . Sergio Boixo, Sergei V Isakov, Vadim N Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, Michael J Bremner, John M Martinis, and Hartmut Neven. Characterizing quantum supremacy in near-term devices. Nature Physics, 14 ( 6 ): 595, 2018."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.aar3106"},{"key":"e_1_3_2_1_8_1","volume-title":"Quantum advantage with noisy shallow circuits in 3D. arXiv e-prints, page arXiv","author":"Bravyi Sergey","year":"1904","unstructured":"Sergey Bravyi , David Gosset , Robert K\u00f6nig , and Marco Tomamichel . Quantum advantage with noisy shallow circuits in 3D. arXiv e-prints, page arXiv : 1904 .01502, Apr 2019. Sergey Bravyi, David Gosset, Robert K\u00f6nig, and Marco Tomamichel. Quantum advantage with noisy shallow circuits in 3D. arXiv e-prints, page arXiv: 1904.01502, Apr 2019."},{"key":"e_1_3_2_1_9_1","first-page":"459","volume":"467","author":"Bremner Michael J","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 - 472 , 2010. 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, 2010.","journal-title":"Engineering Sciences"},{"key":"e_1_3_2_1_10_1","volume-title":"Interacting quantum observables: categorical algebra and diagrammatics. New Journal of Physics, 13 ( 4 ): 043016","author":"Coecke Bob","year":"2011","unstructured":"Bob Coecke and Ross Duncan . Interacting quantum observables: categorical algebra and diagrammatics. New Journal of Physics, 13 ( 4 ): 043016 , 2011 . Bob Coecke and Ross Duncan. Interacting quantum observables: categorical algebra and diagrammatics. New Journal of Physics, 13 ( 4 ): 043016, 2011."},{"key":"e_1_3_2_1_11_1","volume-title":"Trading locality for time: certiifable randomness from low-depth circuits. arXiv e-prints, page arXiv","author":"Coudron Matthew","year":"1810","unstructured":"Matthew Coudron , Jalex Stark , and Thomas Vidick . Trading locality for time: certiifable randomness from low-depth circuits. arXiv e-prints, page arXiv : 1810 .04233, Oct 2018. Matthew Coudron, Jalex Stark, and Thomas Vidick. Trading locality for time: certiifable randomness from low-depth circuits. arXiv e-prints, page arXiv: 1810.04233, Oct 2018."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-53414-8_35"},{"key":"e_1_3_2_1_13_1","volume-title":"Symmetric groups as maximal subgroups of orthogonal and symplectic groups over the field of two elements. Journal of the London Mathematical Society, s2-20 ( 2 ): 227-237","author":"Dye Roger H.","year":"1979","unstructured":"Roger H. Dye . Symmetric groups as maximal subgroups of orthogonal and symplectic groups over the field of two elements. Journal of the London Mathematical Society, s2-20 ( 2 ): 227-237 , 1979 . Roger H. Dye. Symmetric groups as maximal subgroups of orthogonal and symplectic groups over the field of two elements. Journal of the London Mathematical Society, s2-20 ( 2 ): 227-237, 1979."},{"key":"e_1_3_2_1_14_1","volume-title":"Interactive shallow Cliford circuits: quantum advantage against NC1 and beyond. arXiv preprint arXiv","author":"Grier Daniel","year":"1911","unstructured":"Daniel Grier and Luke Schaefer . Interactive shallow Cliford circuits: quantum advantage against NC1 and beyond. arXiv preprint arXiv : 1911 .02555, 2019. Daniel Grier and Luke Schaefer. Interactive shallow Cliford circuits: quantum advantage against NC1 and beyond. arXiv preprint arXiv: 1911.02555, 2019."},{"key":"e_1_3_2_1_16_1","volume-title":"Quantum fan-out is powerful. Theory of computing, 1 ( 1 ): 81-103","author":"H\u00f8yer Peter","year":"2005","unstructured":"Peter H\u00f8yer and Robert \u0160palek . Quantum fan-out is powerful. Theory of computing, 1 ( 1 ): 81-103 , 2005 . Peter H\u00f8yer and Robert \u0160palek. Quantum fan-out is powerful. Theory of computing, 1 ( 1 ): 81-103, 2005."},{"key":"e_1_3_2_1_17_1","volume-title":"Forging quantum data: classically defeating an IQP-based quantum test. arXiv preprint arXiv:1912.05547","author":"Kahanamoku-Meyer Gregory D","year":"2019","unstructured":"Gregory D Kahanamoku-Meyer . Forging quantum data: classically defeating an IQP-based quantum test. arXiv preprint arXiv:1912.05547 , 2019 . Gregory D Kahanamoku-Meyer. Forging quantum data: classically defeating an IQP-based quantum test. arXiv preprint arXiv:1912.05547, 2019."},{"key":"e_1_3_2_1_18_1","volume-title":"8th Innovations in Theoretical Computer Science Conference (ITCS 2017 ). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik","author":"Kerenidis Iordanis","year":"2017","unstructured":"Iordanis Kerenidis and Anupam Prakash . Quantum recommendation systems . In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017 ). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik , 2017 . Iordanis Kerenidis and Anupam Prakash. Quantum recommendation systems. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017 ). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 2017."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62215"},{"key":"e_1_3_2_1_20_1","volume-title":"34th Computational Complexity Conference (CCC 2019 ). Schloss Dagstuhl-LeibnizZentrum fuer Informatik","author":"Gall Fran\u00e7ois Le","year":"2019","unstructured":"Fran\u00e7ois Le Gall . Average-case quantum advantage with shallow circuits . In 34th Computational Complexity Conference (CCC 2019 ). Schloss Dagstuhl-LeibnizZentrum fuer Informatik , 2019 . Fran\u00e7ois Le Gall. Average-case quantum advantage with shallow circuits. In 34th Computational Complexity Conference (CCC 2019 ). Schloss Dagstuhl-LeibnizZentrum fuer Informatik, 2019."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.65.3373"},{"key":"e_1_3_2_1_22_1","volume-title":"Proceedings of the Royal Society A, 463 ( 2088 )","author":"Montanaro Ashley","year":"2007","unstructured":"Ashley Montanaro . Learning stabilizer states by bell sampling . Proceedings of the Royal Society A, 463 ( 2088 ) , 2007 . Ashley Montanaro. Learning stabilizer states by bell sampling. Proceedings of the Royal Society A, 463 ( 2088 ), 2007."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799355053"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0375-9601(90)90172-K"},{"key":"e_1_3_2_1_25_1","volume":"86","author":"Raussendorf Robert","unstructured":"Robert Raussendorf and Hans J Briegel . A one-way quantum computer. Physical Review Letters , 86 ( 22 ): 5188, 2001. Robert Raussendorf and Hans J Briegel. A one-way quantum computer. Physical Review Letters, 86 ( 22 ): 5188, 2001.","journal-title":"Physical Review Letters"},{"key":"e_1_3_2_1_26_1","volume-title":"Measurement-based quantum computation on cluster states. Physical review A, 68 ( 2 ): 022312","author":"Raussendorf Robert","year":"2003","unstructured":"Robert Raussendorf , Daniel E Browne , and Hans J Briegel . Measurement-based quantum computation on cluster states. Physical review A, 68 ( 2 ): 022312 , 2003 . Robert Raussendorf, Daniel E Browne, and Hans J Briegel. Measurement-based quantum computation on cluster states. Physical review A, 68 ( 2 ): 022312, 2003."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01137685"},{"key":"e_1_3_2_1_28_1","first-page":"1413","volume":"465","author":"Dan Shepherd and Michael J Bremner. Temporally unstructured quantum computation. Proceedings of the Royal Society A: Mathematical, Physical and","unstructured":"Dan Shepherd and Michael J Bremner. Temporally unstructured quantum computation. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences , 465 ( 2105 ): 1413 - 1439 , 2009. Dan Shepherd and Michael J Bremner. Temporally unstructured quantum computation. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 465 ( 2105 ): 1413-1439, 2009.","journal-title":"Engineering Sciences"},{"key":"e_1_3_2_1_29_1","first-page":"1484","volume":"26","author":"Shor Peter W.","unstructured":"Peter W. Shor . Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing , 26 ( 5 ): 1484 - 1509 , 1997. Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26 ( 5 ): 1484-1509, 1997.","journal-title":"Computing"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28404"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-016-0140-0"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316310"}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA","acronym":"STOC '20","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384332","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384332","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:32:57Z","timestamp":1750185177000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384332"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":31,"alternative-id":["10.1145\/3357713.3384332","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384332","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}