Abstract
Cellular automata (CA) exemplify systems where simple local interaction rules can lead to intricate and complex emergent phenomena at large scales. The various types of dynamical behavior of CA are usually categorized empirically into Wolfram’s complexity classes. Here, we propose a quantitative measure, rooted in quantum information theory, to categorize the complexity of classical deterministic cellular automata. Specifically, we construct a Matrix Product Operator (MPO) of the transition matrix on the space of all possible CA configurations. We find that the growth of entropy of the singular value spectrum of the MPO reveals the complexity of the CA and can be used to characterize its dynamical behavior. This measure defines the concept of operator entanglement entropy for CA, demonstrating that quantum information measures can be meaningfully applied to classical deterministic systems.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Here the value of 4 is a result of the \(\log _2 4 = 2\) bits of information which is exerted on each cell by its two direct neighbors..
- 2.
The analogy with quantum systems is more profound, as this measure is exactly the entanglement entropy \(S_{L/2}(t) = - \textrm{Tr} \left[ \hat{\rho }_{L/2}(t) \log _2 \hat{\rho }_{L/2}(t) \right] \) of a reduced density matrix \(\hat{\rho }_{L/2}(t)\), constructed from the partial trace over half the CA cells of the Gram matrix of the time evolution operator: \(\hat{\rho }(t) = (\hat{\mathcal {T}}^t)^T \hat{\mathcal {T}}^t\).
- 3.
Out of the 256 possible rules, many are related to each other by symmetry (left-right inversion, bit inversion or both), such that there are only 88 unique rules [5].
References
Alba, V., Dubail, J., Medenjak, M.: Operator entanglement in interacting integrable quantum systems: the case of the rule 54 chain. Phys. Rev. Lett. 122(25), 250603 (2019). https://doi.org/10.1103/PhysRevLett.122.250603
Arrighi, P.: An overview of quantum cellular automata. Nat. Comput. 18(4), 885–899 (2019). https://doi.org/10.1007/s11047-019-09762-6
Bleh, D., Calarco, T., Montangero, S.: Quantum game of life. Europhys. Lett. 97(2), 20012 (2012). https://doi.org/10.1209/0295-5075/97/20012
Buča, B., Garrahan, J.P., Prosen, T., Vanicat, M.: Exact large deviation statistics and trajectory phase transition of a deterministic boundary driven cellular automaton. Phys. Rev. E 100(2), 020103 (2019)
Cattaneo, G., Formenti, E., Margara, L., Mauri, G.: Transformations of the one-dimensional cellular automata rule space. Parallel Comput. 23(11), 1593–1611 (1997). https://doi.org/10.1016/S0167-8191(97)00076-8
Cattaneo, G., Formenti, E., Margara, L., Mauri, G.: On the dynamical behavior of chaotic cellular automata. Theor. Comput. Sci. 217(1), 31–51 (1999). https://doi.org/10.1016/S0304-3975(98)00149-2
Cook, M., et al.: Universality in elementary cellular automata. Compl. Syst. 15(1), 1–40 (2004)
Dubail, J.: Entanglement scaling of operators: a conformal field theory approach, with a glimpse of simulability of long-time dynamics in 1+ 1d. J. Phys. A: Math. Theor. 50(23), 234001 (2017). https://doi.org/10.1088/1751-8121/aa6f38
Hillberry, L.E., et al.: Entangled quantum cellular automata, physical complexity, and goldilocks rules. Quant. Sci. Technol. 6(4), 045017 (2021). https://doi.org/10.1088/2058-9565/ac1c41
Langton, C.G.: Computation at the edge of chaos: phase transitions and emergent computation. Physica D: Nonl. Phenom. 42(1–3), 12–37 (1990). https://doi.org/10.1016/0167-2789(90)90064-V
Langton, C.G.: Self-reproduction in cellular automata. Physica D 10(1–2), 135–144 (1984)
Ney, P.M., Notarnicola, S., Montangero, S., Morigi, G.: Entanglement in the quantum game of life. Phys. Rev. A 105(1), 012416 (2022). https://doi.org/10.1103/PhysRevA.105.012416
Orús, R.: A practical introduction to tensor networks: matrix product states and projected entangled pair states. Annal. Phys. 349, 117–158 (2014). https://doi.org/10.1016/j.aop.2014.06.013
Piroli, L., Cirac, J.I.: Quantum cellular automata, tensor networks, and area laws. Phys. Rev. Lett. 125(19), 190402 (2020). https://doi.org/10.1103/PhysRevLett.125.190402
Prosen, T., Pižorn, I.: Operator space entanglement entropy in a transverse ising chain. Phys. Rev. A 76(3), 032316 (2007). https://doi.org/10.1103/PhysRevA.76.032316
Prosen, T., Žnidarič, M.: Is the efficiency of classical simulations of quantum dynamics related to integrability? Phys. Rev. E 75(1), 015202 (2007). https://doi.org/10.1103/PhysRevE.75.015202
Schollwöck, U.: The density-matrix renormalization group in the age of matrix product states. Annal. Phys. 326(1), 96–192 (2011). https://doi.org/10.1016/j.aop.2010.09.012
Schuch, N., Wolf, M.M., Verstraete, F., Cirac, J.I.: Entropy scaling and simulability by matrix product states. Phys. Rev. Lett. 100(3), 030504 (2008). https://doi.org/10.1103/PhysRevLett.100.030504
Takahashi, S.: Cellular automata and multifractals: dimension spectra of linear cellular automata. Physica D: Nonl. Phenom. 45(1–3), 36–48 (1990). https://doi.org/10.1016/0167-2789(90)90172-L
Verstraete, F., Murg, V., Cirac, J.I.: Matrix product states, projected entangled pair states, and variational renormalization group methods for quantum spin systems. Adv. Phys. 57(2), 143–224 (2008). https://doi.org/10.1080/14789940801912366
Vispoel, M., Daly, A.J., Baetens, J.M.: Progress, gaps and obstacles in the classification of cellular automata. Physica D: Nonl. Phenom. 432, 133074 (2022). https://doi.org/10.1016/j.physd.2021.133074
Wolfram, S.: Statistical mechanics of cellular automata. Rev. Mod. Phys. 55(3), 601 (1983). https://doi.org/10.1103/RevModPhys.55.601
Wolfram, S.: Cellular automata as models of complexity. Nature 311(5985), 419–424 (1984). https://doi.org/10.1038/311419a0
Wolfram, S.: Universality and complexity in cellular automata. Physica D: Nonl. Phenom. 10(1–2), 1–35 (1984). https://doi.org/10.1016/0167-2789(84)90245-8
Zanardi, P.: Entanglement of quantum evolutions. Phys. Rev. A 63(4), 040304 (2001). https://doi.org/10.1103/PhysRevA.63.040304
Zhou, T., Luitz, D.J.: Operator entanglement entropy of the time evolution operator in chaotic systems. Phys. Rev. B 95(9), 094206 (2017)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Bakker, C., Merbis, W. (2024). Operator Entanglement Growth Quantifies Complexity of Cellular Automata. In: Franco, L., de Mulatier, C., Paszynski, M., Krzhizhanovskaya, V.V., Dongarra, J.J., Sloot, P.M.A. (eds) Computational Science – ICCS 2024. ICCS 2024. Lecture Notes in Computer Science, vol 14832. Springer, Cham. https://doi.org/10.1007/978-3-031-63749-0_3
Download citation
DOI: https://doi.org/10.1007/978-3-031-63749-0_3
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-63748-3
Online ISBN: 978-3-031-63749-0
eBook Packages: Computer ScienceComputer Science (R0)