Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

Operator Entanglement Growth Quantifies Complexity of Cellular Automata

Calvin C. Bakker, Wout Merbis

Published Jan 1, 2024• 2 citations
Publisher
DOI
10.1007/978-3-031-63749-0_3

Related papers

Quantum cellular automata part I: Entanglement, physical complexity, and Goldilocks rules

Logan Edward Hillberry, M. Jones, David L. Vargas +6 more

Bulletin of the American Physical Society•Mar 16, 2021•0 citations

Entanglement dynamics in quantum cellular automata

M. Andrecut

Physics Letters A•May 1, 2004•0 citations

Entanglement dynamics in quantum cellular automata

M. Andrecut, Mazhar Ali

Physics Letters A•May 13, 2004•5 citations

Quantum cellular automata part II: Robust complexity under analog and digital evolution in 1- and 2-dimensions

Matthew Jones, Logan Edward Hillberry, Eric Jones +5 more

Bulletin of the American Physical Society•Mar 16, 2021•0 citations

Operator entanglement growth quantifies complexity of cellular automata

Wout Merbis, Calvin C. Bakker

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.

arXiv:2406.04895•Jun 7, 2024•0 citations

Topological Lower Bound on Quantum Chaos by Entanglement Growth

Zongping Gong, Lorenzo Piroli, J. I. Cirac

A fundamental result in modern quantum chaos theory is the Maldacena-Shenker-Stanford upper bound on the growth of out-of-time-order correlators, whose infinite-temperature limit is related to the operator-space entanglement entropy of the evolution operator. Here we show that, for one-dimensional quantum cellular automata (QCA), there exists a lower bound on quantum chaos quantified by such entanglement entropy. This lower bound is equal to twice the index of the QCA, which is a topological invariant that measures the chirality of information flow, and holds for all the Rényi entropies, with its strongest Rényi-∞ version being tight. The rigorous bound rules out the possibility of any sublinear entanglement growth behavior, showing in particular that many-body localization is forbidden for unitary evolutions displaying nonzero index. Since the Rényi entropy is measurable, our findings have direct experimental relevance. Our result is robust against exponential tails which naturally appear in quantum dynamics generated by local Hamiltonians.

arXiv:2012.02772•Physical Review Letters•Apr 19, 2021•24 citations
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.
A fundamental result in modern quantum chaos theory is the Maldacena-Shenker-Stanford upper bound on the growth of out-of-time-order correlators, whose infinite-temperature limit is related to the operator-space entanglement entropy of the evolution operator. Here we show that, for one-dimensional quantum cellular automata (QCA), there exists a lower bound on quantum chaos quantified by such entanglement entropy. This lower bound is equal to twice the index of the QCA, which is a topological invariant that measures the chirality of information flow, and holds for all the Rényi entropies, with its strongest Rényi-∞ version being tight. The rigorous bound rules out the possibility of any sublinear entanglement growth behavior, showing in particular that many-body localization is forbidden for unitary evolutions displaying nonzero index. Since the Rényi entropy is measurable, our findings have direct experimental relevance. Our result is robust against exponential tails which naturally appear in quantum dynamics generated by local Hamiltonians.