Quantum Cellular Automata, Black Hole Thermodynamics and the Laws of Quantum Complexity
Ruhi Shah
University of Waterloo
200 University Avenue W
Waterloo, ON N2L 3G1, Canada
r57shah@uwaterloo.ca
Jonathan Gorard
King’s College, University of Cambridge
CB2 1ST, Cambridge, England
jg865@cam.ac.uk
Algorithms R&D Group, Wolfram Research, Inc.
100 Trade Center Drive
Champaign, IL 61820-7237, USA
jonathang@wolfram.com
Abstract
This paper introduces a new formalism for quantum cellular automata (QCAs), based on evolving tensor products of qubits using local unitary operators. It subsequently uses this formalism to analyze and validate several conjectures, stemming from a formal analogy among quantum computational complexity theory and classical thermodynamics, that have arisen recently in the context of black hole physics. In particular, the apparent resonance and thermalization effects present within such QCAs are investigated, and it is demonstrated that the expected exponential relationships among the quantum circuit complexity of the evolution operator, the classical entropy of the equilibrium QCA state and the characteristic equilibration time of the QCA all hold within this new model. Finally, a rigorous explanation for this empirical relationship is provided, as well as for the relationship with black hole thermodynamics, by drawing an explicit mathematical connection with the mean ergodic theorem and the ergodicity of k-local quantum systems.
Keywords: cellular automata; quantum cellular automata; quantum computing; quantum information theory; complexity theory; ergodic theory; black hole thermodynamics
Cite this publication as:
R. Shah and J. Gorard, “Quantum Cellular Automata, Black Hole Thermodynamics and the Laws of Quantum Complexity,” Complex Systems, 28(4), 2019 pp. 393–410.
https://doi.org/10.25088/ComplexSystems.28.4.393
