Chaos and complexity by design

By Daniel A. Roberts, B. Yoshida. 2016

474 citations recorded by the source corpus.

A bstractWe study the relationship between quantum chaos and pseudorandomness by developing probes of unitary design. A natural probe of randomness is the “frame poten-tial,” which is minimized by unitary k-designs and measures the 2-norm distance between the Haar random unitary ensemble and another ensemble. A natural probe of quantum chaos is out-of-time-order (OTO) four-point correlation functions. We show that the norm squared of a generalization of out-of-time-order 2k-point correlators is proportional to the kth frame potential, providing a quantitative connection between chaos and pseudorandomness. Additionally, we prove that these 2k-point correlators for Pauli operators completely determine the k-fold channel of an ensemble of unitary operators. Finally, we use a counting argument to obtain a lower bound on the quantum circuit complexity in terms of the frame potential. This provides a direct link between chaos, complexity, and randomness.

Subfields: Artificial Intelligence, Atomic and Molecular Physics, and Optics, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/9adac0b106bb2877ad2762f0ec98e4db64315d2a

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Atomic and Molecular Physics, and Optics

In Statistical and Nonlinear Physics

Citations in the corpus

A semiclassical ramp in SYK and in gravity (2018, methodology): “Our discussion builds on the standard approach to Haar integrals over unitary matrices described in [66, 67, 68].”
Diffusive Hydrodynamics of Out-of-Time-Ordered Correlators with Charge Conservation (2017, background): “12, if μ is sufficiently large, indicating that the scrambling time [28,61] associated to FIG.”
Second law of quantum complexity (2017, background): “We’d also like to thank Andy Albrecht, Beni Yoshida, Dan Roberts, Daniel Harlow, Douglas Stanford, Henry Lin, Hrant Gharibyan, Nicole Yunger Halpern, Simeon Hellerman, and Ying Zhao.”
Efficient decoding for the Hayden-Preskill protocol (2017, unknown): “[14, 15]: To handle the general case, we will devise some new notation.”
Emergent Quantum State Designs from Individual Many-Body Wave Functions (2021, result): “This observation is consistent with the idea that typical quantum states from higher k-designs are more complex and hence more difficult to prepare [52,57,58].”
Measurement-Induced Phase Transitions in the Dynamics of Entanglement (2018, background): “) How is the membrane picture for entanglement growth [9, 14, 23] modified by weak breaking of unitarity? Finally, one could also ask how the ‘complexity’ of the evolving state (the minimal number of local operations required to generate it from a product state [81–92]) behaves as the entangling-dis”
Barren plateaus in quantum neural network training landscapes (2018, background): “Whereas a unitary 2-design will exhibit the correct variance [43, 46], a unitary 1-design will exhibit the correct average value, but not necessarily the variance.”
Entanglement Membrane in Chaotic Many-Body Systems (2019, background): “[81] Daniel A Roberts and Beni Yoshida.”
Linear growth of quantum circuit complexity (2021, background): “Further evidence for the conjecture arises from counting arguments [49].”
Complexity of formation in holography (2016, methodology): “The interested reader may also look at appendix E of [15], which suggests some ways of bounding complexity in thermal states.”
Unitary designs from statistical mechanics in random quantum circuits. (2019, background): “Speciﬁcally, [25] related the frame potential to both averaged out-of-time-ordered correlators and measures of complexity, and [26] computed the frame potentials for random Hamiltonian evolution.”
Black holes and random matrices (2016, background): “Recent discussion of a connection between chaotic systems and random ensembles, including observables generalizing 〈|Z(β, t)|(2)〉, appears in [35].”