{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T03:40:53Z","timestamp":1780976453529,"version":"3.54.1"},"reference-count":24,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T00:00:00Z","timestamp":1620086400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSF","award":["2014000"],"award-info":[{"award-number":["2014000"]}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>It is well known that a quantum circuit on<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>N<\/mml:mi><\/mml:math>qubits composed of Clifford gates with the addition of<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>k<\/mml:mi><\/mml:math>non Clifford gates can be simulated on a classical computer by an algorithm scaling as<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mtext>poly<\/mml:mtext><mml:mo stretchy=\"false\">(<\/mml:mo><mml:mi>N<\/mml:mi><mml:mo stretchy=\"false\">)<\/mml:mo><mml:mi>exp<\/mml:mi><mml:mo>\u2061<\/mml:mo><mml:mo stretchy=\"false\">(<\/mml:mo><mml:mi>k<\/mml:mi><mml:mo stretchy=\"false\">)<\/mml:mo><\/mml:math>\\cite{bravyi2016improved}. We show that, for a quantum circuit to simulate quantum chaotic behavior, it is both necessary and sufficient that<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>k<\/mml:mi><mml:mo>=<\/mml:mo><mml:mi mathvariant=\"normal\">\u0398<\/mml:mi><mml:mo stretchy=\"false\">(<\/mml:mo><mml:mi>N<\/mml:mi><mml:mo stretchy=\"false\">)<\/mml:mo><\/mml:math>. This result implies the impossibility of simulating quantum chaos on a classical computer.<\/jats:p>","DOI":"10.22331\/q-2021-05-04-453","type":"journal-article","created":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T12:03:40Z","timestamp":1620129820000},"page":"453","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":94,"title":["Quantum Chaos is Quantum"],"prefix":"10.22331","volume":"5","author":[{"given":"Lorenzo","family":"Leone","sequence":"first","affiliation":[{"name":"Physics Department, University of Massachusetts Boston, 02125, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Salvatore F. E.","family":"Oliviero","sequence":"additional","affiliation":[{"name":"Physics Department, University of Massachusetts Boston, 02125, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"You","family":"Zhou","sequence":"additional","affiliation":[{"name":"School of Physical and Mathematical Sciences, Nanyang Technological University, 637371, Singapore"},{"name":"Department of Physics, Harvard University, Cambridge, Massachusetts 02138, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alioscia","family":"Hamma","sequence":"additional","affiliation":[{"name":"Physics Department, University of Massachusetts Boston, 02125, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"9598","published-online":{"date-parts":[[2021,5,4]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"S. Bravyi and D. Gosset, Improved classical simulation of quantum circuits dominated by Clifford gates, Physical Review Letters 116, 250501 (2016), 10.1103\/PhysRevLett.116.250501.","DOI":"10.1103\/PhysRevLett.116.250501"},{"key":"1","doi-asserted-by":"crossref","unstructured":"A. Kitaev, Hidden correlations in the Hawking radiation and thermal noise, In Talk given at the Fundamental Physics Prize Symposium, vol. 10 (2014).","DOI":"10.1063\/pt.5.7115"},{"key":"2","doi-asserted-by":"publisher","unstructured":"D. A. Roberts and B. Yoshida, Chaos and complexity by design, Journal of High Energy Physics 2017(4), 121 (2017), 10.1007\/JHEP04(2017)121.","DOI":"10.1007\/JHEP04(2017)121"},{"key":"3","doi-asserted-by":"crossref","unstructured":"A. W. Harrow, L. Kong et al., A separation of out-of-time-ordered correlation and entanglement, arXiv (2020), [quant-ph\/1906.02219].","DOI":"10.1103\/PRXQuantum.2.020339"},{"key":"4","doi-asserted-by":"publisher","unstructured":"A. Nahum, S. Vijay and J. Haah, Operator spreading in random unitary circuits, Physical Review X 8, 021014 (2018), 10.1103\/PhysRevX.8.021014.","DOI":"10.1103\/PhysRevX.8.021014"},{"key":"5","doi-asserted-by":"publisher","unstructured":"V. Khemani, A. Vishwanath and D. A. Huse, Operator spreading and the emergence of dissipative hydrodynamics under unitary evolution with conservation laws, Physical Review X 8, 031057 (2018), 10.1103\/PhysRevX.8.031057.","DOI":"10.1103\/PhysRevX.8.031057"},{"key":"6","doi-asserted-by":"publisher","unstructured":"S. F. E. Oliviero, L. Leone et al., Random Matrix Theory of the Isospectral twirling, SciPost Phys. 10, 76 (2021), 10.21468\/SciPostPhys.10.3.076.","DOI":"10.21468\/SciPostPhys.10.3.076"},{"key":"7","doi-asserted-by":"publisher","unstructured":"D. Ding, P. Hayden and M. Walter, Conditional mutual information of bipartite unitaries and scrambling, Journal of High Energy Physics 2016(12), 145 (2016), 10.1007\/JHEP12(2016)145.","DOI":"10.1007\/JHEP12(2016)145"},{"key":"8","doi-asserted-by":"publisher","unstructured":"P. Hosur, X. Qi et al., Chaos in quantum channels, Journal of High Energy Physics 2016(2), 4 (2016), 10.1007\/JHEP02(2016)004.","DOI":"10.1007\/JHEP02(2016)004"},{"key":"9","doi-asserted-by":"crossref","unstructured":"L. Leone, S. F. Oliviero and A. Hamma, Isospectral twirling and quantum chaos, arXiv (2020), [quant-ph\/2011.06011].","DOI":"10.3390\/e23081073"},{"key":"10","doi-asserted-by":"publisher","unstructured":"S. Zhou, Z. Yang et al., Single T gate in a Clifford circuit drives transition to universal entanglement spectrum statistics, SciPost Phys. 9, 87 (2020), 10.21468\/SciPostPhys.9.6.087.","DOI":"10.21468\/SciPostPhys.9.6.087"},{"key":"11","unstructured":"J. Haferkamp, F. Montealegre-Mora et al., Quantum homeopathy works: Efficient unitary designs with a system-size independent number of non-Clifford gates, arXiv (2020), [quant-ph\/2002.09524]."},{"key":"12","doi-asserted-by":"publisher","unstructured":"M. J. Bremner, R. Jozsa and D. 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 (2011), 10.1098\/rspa.2010.0301.","DOI":"10.1098\/rspa.2010.0301"},{"key":"13","doi-asserted-by":"publisher","unstructured":"A. W. Harrow and A. Montanaro, Quantum computational supremacy, Nature 549(7671), 203 (2017), 10.1038\/nature23458.","DOI":"10.1038\/nature23458"},{"key":"14","doi-asserted-by":"publisher","unstructured":"D. A. Roberts and B. Swingle, Lieb-Robinson bound and the butterfly effect in quantum field theories, Physical Review Letters 117, 091602 (2016), 10.1103\/PhysRevLett.117.091602.","DOI":"10.1103\/PhysRevLett.117.091602"},{"key":"15","doi-asserted-by":"publisher","unstructured":"C. Chamon, A. Hamma and E. R. Mucciolo, Emergent irreversibility and entanglement spectrum statistics, Physical Review Letters 112, 240501 (2014), 10.1103\/PhysRevLett.112.240501.","DOI":"10.1103\/PhysRevLett.112.240501"},{"key":"16","doi-asserted-by":"publisher","unstructured":"A. W. Harrow and R. A. Low, Random quantum circuits are approximate 2-designs, Communications in Mathematical Physics 291(1), 257 (2009), 10.1007\/s00220-009-0873-6.","DOI":"10.1007\/s00220-009-0873-6"},{"key":"17","doi-asserted-by":"crossref","unstructured":"Z. Webb, The Clifford group forms a unitary 3-design, arXiv (2016), [quant-ph\/1510.02769].","DOI":"10.26421\/QIC16.15-16-8"},{"key":"18","doi-asserted-by":"publisher","unstructured":"H. Zhu, Multiqubit Clifford groups are unitary 3-designs, Physical Review A 96, 062336 (2017), 10.1103\/PhysRevA.96.062336.","DOI":"10.1103\/PhysRevA.96.062336"},{"key":"19","doi-asserted-by":"publisher","unstructured":"A. Hamma, S. Santra and P. Zanardi, Ensembles of physical states and random quantum circuits on graphs, Physical Review A 86, 052324 (2012), 10.1103\/PhysRevA.86.052324.","DOI":"10.1103\/PhysRevA.86.052324"},{"key":"20","doi-asserted-by":"publisher","unstructured":"B. Collins and P. \u015aniady, Integration with respect to the Haar measure on unitary, orthogonal and symplectic group, Communications in Mathematical Physics 264(3), 773 (2006), 10.1007\/s00220-006-1554-3.","DOI":"10.1007\/s00220-006-1554-3"},{"key":"21","doi-asserted-by":"publisher","unstructured":"B. Collins, Moments and cumulants of polynomial random variables on unitary groups, the Itzykson-Zuber integral, and free probability, International Mathematics Research Notices 2003(17), 953 (2003), 10.1155\/S107379280320917X.","DOI":"10.1155\/S107379280320917X"},{"key":"22","doi-asserted-by":"publisher","unstructured":"I. Roth, R. Kueng et al., Recovering quantum gates from few average gate fidelities, Physical Review Letters 121, 170502 (2018), 10.1103\/PhysRevLett.121.170502.","DOI":"10.1103\/PhysRevLett.121.170502"},{"key":"23","unstructured":"H. Zhu, R. Kueng et al., The Clifford group fails gracefully to be a unitary 4-design, arXiv (2016), [quant-ph\/1609.08172]."}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2021-05-04-453\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,8,30]],"date-time":"2024-08-30T04:30:34Z","timestamp":1724992234000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2021-05-04-453\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,4]]},"references-count":24,"URL":"https:\/\/doi.org\/10.22331\/q-2021-05-04-453","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,5,4]]},"article-number":"453"}}