Quantum Chaos is Quantum

Lorenzo Leone; Salvatore F. E. Oliviero; You Zhou; Alioscia Hamma

doi:10.22331/q-2021-05-04-453

Quantum Chaos is Quantum

Lorenzo Leone¹, Salvatore F. E. Oliviero¹, You Zhou^2,3, and Alioscia Hamma¹

¹Physics Department, University of Massachusetts Boston, 02125, USA
²School of Physical and Mathematical Sciences, Nanyang Technological University, 637371, Singapore
³Department of Physics, Harvard University, Cambridge, Massachusetts 02138, USA

Published:	2021-05-04, volume 5, page 453
Eprint:	arXiv:2102.08406v3
Doi:	https://doi.org/10.22331/q-2021-05-04-453
Citation:	Quantum 5, 453 (2021).

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

Abstract

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.

Featured image: $\mathit{Left}$ : Scheme of the $4$-Doped Clifford circuit. $\mathit{Right}$ : Detail of $K_{C_{4}}$, a unitary single-qubit non Clifford gate $K$ evolved adjointly by a Clifford circuit $C_{4}$. Note that the set formed by these circuits is equivalent to the set of doped Clifford circuits, i.e circuits composed by Clifford unitaries $C_{i}$ interspersed with single-qubit non Clifford gates $K_{i}$.

► BibTeX data

@article{Leone2021quantumchaosis,
  doi = {10.22331/q-2021-05-04-453},
  url = {https://doi.org/10.22331/q-2021-05-04-453},
  title = {Quantum {C}haos is {Q}uantum},
  author = {Leone, Lorenzo and Oliviero, Salvatore F. E. and Zhou, You and Hamma, Alioscia},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {5},
  pages = {453},
  month = may,
  year = {2021}
}

► 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.
https://doi.org/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.
https://doi.org/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].
arXiv: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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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].
arXiv: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.
https://doi.org/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].
arXiv: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.
https://doi.org/10.1098/rspa.2010.0301

[14] A. W. Harrow and A. Montanaro, Quantum computational supremacy, Nature 549(7671), 203 (2017), 10.1038/nature23458.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/10.1007/s00220-009-0873-6

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

[19] H. Zhu, Multiqubit Clifford groups are unitary 3-designs, Physical Review A 96, 062336 (2017), 10.1103/PhysRevA.96.062336.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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.
https://doi.org/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].
arXiv:1609.08172

Cited by

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[25] Lorenzo Leone, Salvatore F. E. Oliviero, Seth Lloyd, and Alioscia Hamma, "Learning efficient decoders for quasi-chaotic quantum scramblers", arXiv:2212.11338, (2022).

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

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

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

The above citations are from Crossref's cited-by service (last updated successfully 2023-12-07 09:43:28) and SAO/NASA ADS (last updated successfully 2023-12-07 09:43:29). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.