Quantum Chaos is Quantum

Lorenzo Leone1, Salvatore F. E. Oliviero1, You Zhou2,3, and Alioscia Hamma1

1Physics Department, University of Massachusetts Boston, 02125, USA
2School of Physical and Mathematical Sciences, Nanyang Technological University, 637371, Singapore
3Department of Physics, Harvard University, Cambridge, Massachusetts 02138, USA

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


It is well known that a quantum circuit on $N$ qubits composed of Clifford gates with the addition of $k$ non Clifford gates can be simulated on a classical computer by an algorithm scaling as $\text{poly}(N)\exp(k)$[1]. We show that, for a quantum circuit to simulate quantum chaotic behavior, it is both necessary and sufficient that $k=\Theta(N)$. This result implies the impossibility of simulating quantum chaos on a classical computer.

► BibTeX data

► References

[1] 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.

[2] A. Kitaev, Hidden correlations in the Hawking radiation and thermal noise, In Talk given at the Fundamental Physics Prize Symposium, vol. 10 (2014).

[3] 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.

[4] A. W. Harrow, L. Kong et al., A separation of out-of-time-ordered correlation and entanglement, arXiv (2020), [quant-ph/​1906.02219].

[5] A. Nahum, S. Vijay and J. Haah, Operator spreading in random unitary circuits, Physical Review X 8, 021014 (2018), 10.1103/​PhysRevX.8.021014.

[6] 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.

[7] 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.

[8] 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.

[9] P. Hosur, X. Qi et al., Chaos in quantum channels, Journal of High Energy Physics 2016(2), 4 (2016), 10.1007/​JHEP02(2016)004.

[10] L. Leone, S. F. Oliviero and A. Hamma, Isospectral twirling and quantum chaos, arXiv (2020), [quant-ph/​2011.06011].

[11] 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.

[12] 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].

[13] 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.

[14] A. W. Harrow and A. Montanaro, Quantum computational supremacy, Nature 549(7671), 203 (2017), 10.1038/​nature23458.

[15] 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.

[16] 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.

[17] 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.

[18] Z. Webb, The Clifford group forms a unitary 3-design, arXiv (2016), [quant-ph/​1510.02769].

[19] H. Zhu, Multiqubit Clifford groups are unitary 3-designs, Physical Review A 96, 062336 (2017), 10.1103/​PhysRevA.96.062336.

[20] 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.

[21] B. Collins and P. Śniady, 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.

[22] 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.

[23] 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.

[24] H. Zhu, R. Kueng et al., The Clifford group fails gracefully to be a unitary 4-design, arXiv (2016), [quant-ph/​1609.08172].

Cited by

[1] You Zhou and Alioscia Hamma, "Entanglement of random hypergraph states", Physical Review A 106 1, 012410 (2022).

[2] Lorenzo Leone, Salvatore F. E. Oliviero, Gianluca Esposito, and Alioscia Hamma, "Phase transition in stabilizer entropy and efficient purity estimation", Physical Review A 109 3, 032403 (2024).

[3] Joonho Kim, Yaron Oz, and Dario Rosa, "Quantum chaos and circuit parameter optimization", Journal of Statistical Mechanics: Theory and Experiment 2023 2, 023104 (2023).

[4] Lorenzo Leone, Salvatore F. E. Oliviero, and Alioscia Hamma, "Nonstabilizerness determining the hardness of direct fidelity estimation", Physical Review A 107 2, 022429 (2023).

[5] Lorenzo Leone, Salvatore F. E. Oliviero, and Alioscia Hamma, "Stabilizer Rényi Entropy", Physical Review Letters 128 5, 050402 (2022).

[6] Tom Farshi, Jonas Richter, Daniele Toniolo, Arijeet Pal, and Lluis Masanes, "Absence of Localization in Two-Dimensional Clifford Circuits", PRX Quantum 4 3, 030302 (2023).

[7] Salvatore F. E. Oliviero, Lorenzo Leone, Alioscia Hamma, and Seth Lloyd, "Measuring magic on a quantum processor", npj Quantum Information 8 1, 148 (2022).

[8] J. Haferkamp, F. Montealegre-Mora, M. Heinrich, J. Eisert, D. Gross, and I. Roth, "Efficient Unitary Designs with a System-Size Independent Number of Non-Clifford Gates", Communications in Mathematical Physics 397 3, 995 (2023).

[9] J. Odavić, G. Torre, N. Mijić, D. Davidović, F. Franchini, and S. M. Giampaolo, "Random unitaries, Robustness, and Complexity of Entanglement", Quantum 7, 1115 (2023).

[10] Ritam Basu, Anirban Ganguly, Souparna Nath, and Onkar Parrikar, "Complexity growth and the Krylov-Wigner function", Journal of High Energy Physics 2024 5, 264 (2024).

[11] Lorenzo Leone, Salvatore F. E. Oliviero, Seth Lloyd, and Alioscia Hamma, "Learning efficient decoders for quasichaotic quantum scramblers", Physical Review A 109 2, 022429 (2024).

[12] Sivaprasad Omanakuttan, Karthik Chinni, Philip Daniel Blocher, and Pablo M. Poggi, "Scrambling and quantum chaos indicators from long-time properties of operator distributions", Physical Review A 107 3, 032418 (2023).

[13] Salvatore F. E. Oliviero, Lorenzo Leone, Seth Lloyd, and Alioscia Hamma, "Unscrambling Quantum Information with Clifford Decoders", Physical Review Letters 132 8, 080402 (2024).

[14] Emanuele Tirrito, Poetri Sonya Tarabunga, Gugliemo Lami, Titas Chanda, Lorenzo Leone, Salvatore F. E. Oliviero, Marcello Dalmonte, Mario Collura, and Alioscia Hamma, "Quantifying nonstabilizerness through entanglement spectrum flatness", Physical Review A 109 4, L040401 (2024).

[15] Neil Dowling, Pavel Kos, and Kavan Modi, "Scrambling Is Necessary but Not Sufficient for Chaos", Physical Review Letters 131 18, 180403 (2023).

[16] Neil Dowling and Kavan Modi, "Operational Metric for Quantum Chaos and the Corresponding Spatiotemporal-Entanglement Structure", PRX Quantum 5 1, 010314 (2024).

[17] Xhek Turkeshi, Marco Schirò, and Piotr Sierant, "Measuring nonstabilizerness via multifractal flatness", Physical Review A 108 4, 042408 (2023).

[18] Lorenzo Leone, Salvatore F. E. Oliviero, and Alioscia Hamma, "Isospectral Twirling and Quantum Chaos", Entropy 23 8, 1073 (2021).

[19] Lorenzo Leone, Salvatore F. E. Oliviero, Stefano Piemontese, Sarah True, and Alioscia Hamma, "Retrieving information from a black hole using quantum machine learning", Physical Review A 106 6, 062434 (2022).

[20] Sarah True and Alioscia Hamma, "Transitions in Entanglement Complexity in Random Circuits", Quantum 6, 818 (2022).

[21] Troy J. Sewell and Christopher David White, "Mana and thermalization: Probing the feasibility of near-Clifford Hamiltonian simulation", Physical Review B 106 12, 125130 (2022).

[22] Filipa C R Peres, Rafael Wagner, and Ernesto F Galvão, "Non-stabilizerness and entanglement from cat-state injection", New Journal of Physics 26 1, 013051 (2024).

[23] Tobias Haug and Lorenzo Piroli, "Quantifying nonstabilizerness of matrix product states", Physical Review B 107 3, 035148 (2023).

[24] Jose Carrasco, Matteo Votto, Vittorio Vitale, Christian Kokail, Antoine Neven, Peter Zoller, Benoît Vermersch, and Barbara Kraus, "Entanglement phase diagrams from partial transpose moments", Physical Review A 109 1, 012422 (2024).

[25] Stefano Piemontese, Tommaso Roscilde, and Alioscia Hamma, "Entanglement complexity of the Rokhsar-Kivelson-sign wavefunctions", Physical Review B 107 13, 134202 (2023).

[26] Piotr Dulian and Adam Sawicki, "A Random Matrix Model for Random Approximate t-Designs", IEEE Transactions on Information Theory 70 4, 2637 (2024).

[27] Salvatore F. E. Oliviero, Lorenzo Leone, and Alioscia Hamma, "Magic-state resource theory for the ground state of the transverse-field Ising model", Physical Review A 106 4, 042426 (2022).

[28] Arash Ahmadi and Eliska Greplova, "Quantifying non-stabilizerness via information scrambling", SciPost Physics 16 2, 043 (2024).

[29] Junjie Chen, Yuxuan Yan, and You Zhou, "Magic of quantum hypergraph states", Quantum 8, 1351 (2024).

[30] Kanato Goto, Tomoki Nosaka, and Masahiro Nozaki, "Probing chaos by magic monotones", Physical Review D 106 12, 126009 (2022).

[31] Tobias Haug and M.S. Kim, "Scalable Measures of Magic Resource for Quantum Computers", PRX Quantum 4 1, 010301 (2023).

[32] Jonas Haferkamp, "Random quantum circuits are approximate unitary t-designs in depth O(nt5+o(1))", Quantum 6, 795 (2022).

[33] You Zhou and Qing Liu, "Performance analysis of multi-shot shadow estimation", Quantum 7, 1044 (2023).

[34] Roy J. Garcia, Kaifeng Bu, and Arthur Jaffe, "Quantifying scrambling in quantum neural networks", Journal of High Energy Physics 2022 3, 27 (2022).

[35] Davide Rattacaso, Lorenzo Leone, Salvatore F. E. Oliviero, and Alioscia Hamma, "Stabilizer entropy dynamics after a quantum quench", Physical Review A 108 4, 042407 (2023).

[36] Sudip Sinha, Sayak Ray, and Subhasis Sinha, "Classical route to ergodicity and scarring in collective quantum systems", Journal of Physics Condensed Matter 36 16, 163001 (2024).

[37] Junjie Chen, Yuxuan Yan, and You Zhou, "Magic of quantum hypergraph states", arXiv:2308.01886, (2023).

[38] Andi Gu, Salvatore F. E. Oliviero, and Lorenzo Leone, "Doped stabilizer states in many-body physics and where to find them", arXiv:2403.14912, (2024).

[39] Cahit Kargi, Juan Pablo Dehollain, Lukas M. Sieberer, Fabio Henriques, Tobias Olsacher, Philipp Hauke, Markus Heyl, Peter Zoller, and Nathan K. Langford, "Quantum Chaos and Universal Trotterisation Behaviours in Digital Quantum Simulations", arXiv:2110.11113, (2021).

[40] Salvatore F. E. Oliviero, Lorenzo Leone, and Alioscia Hamma, "Transitions in entanglement complexity in random quantum circuits by measurements", Physics Letters A 418, 127721 (2021).

[41] ChunJun Cao, Gong Cheng, Alioscia Hamma, Lorenzo Leone, William Munizzi, and Savatore F. E. Oliviero, "Gravitational back-reaction is magical", arXiv:2403.07056, (2024).

[42] Piotr Dulian and Adam Sawicki, "A random matrix model for random approximate $t$-designs", arXiv:2210.07872, (2022).

[43] Ágoston Kaposi, Zoltán Kolarovszki, Adrián Solymos, and Zoltán Zimborás, "Generalized group designs: overcoming the 4-design-barrier and constructing novel unitary 2-designs in arbitrary dimensions", arXiv:2405.00919, (2024).

The above citations are from Crossref's cited-by service (last updated successfully 2024-05-25 05:48:04) and SAO/NASA ADS (last updated successfully 2024-05-25 05:48:05). The list may be incomplete as not all publishers provide suitable and complete citation data.