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] Salvatore F. E. Oliviero, Lorenzo Leone, and Alioscia Hamma, "Transitions in entanglement complexity in random quantum circuits by measurements", arXiv:2103.07481.

The above citations are from SAO/NASA ADS (last updated successfully 2021-05-07 00:06:31). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2021-05-07 00:06:29).