Quantum-inspired identification of complex cellular automata

Matthew Ho, Andri Pradana, Thomas J. Elliott, Lock Yue Chew, Mile Gu

Research output: Contribution to journalArticlepeer-review

1 Downloads (Pure)


Elementary cellular automata (ECA) present iconic examples of complex systems. Though described only by one-dimensional strings of binary cells evolving according to nearest-neighbour update rules, certain ECA rules manifest complex dynamics capable of universal computation. Yet, the classification of precisely which rules exhibit complex behaviour remains somewhat an open debate. Here, we approach this question using tools from quantum stochastic modelling, where quantum statistical memory—the memory required to model a stochastic process using a class of quantum machines—can be used to quantify the structure of a stochastic process. By viewing ECA rules as transformations of stochastic patterns, we ask: Does an ECA generate structure as quantified by the quantum statistical memory, and can this be used to identify complex cellular automata? We illustrate how the growth of this measure over time correctly distinguishes simple ECA from complex counterparts. Moreover, it provides a spectrum on which we can rank the complexity of ECA, by the rate at which they generate structure.

Original languageEnglish
Article number540
JournalEuropean Physical Journal Plus
Issue number6
Publication statusPublished - Jun 2023


Dive into the research topics of 'Quantum-inspired identification of complex cellular automata'. Together they form a unique fingerprint.

Cite this