Quantum-inspired identification of complex cellular automata
arXiv:2103.14053 · doi:10.1140/epjp/s13360-023-04160-5
Abstract
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 a significant challenge. 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 if so, how quickly? We illustrate how the growth of this measure over time correctly distinguishes simple ECA from complex counterparts. Moreover, it provides a more refined means for quantitatively identifying complex ECAs -- providing a spectrum on which we can rank the complexity of ECA by the rate in which they generate structure.
22 pages, 9 figures
References in corpus (20)
- Computational Mechanics: Pattern and Prediction, Structure and Simplicity
- Occam's Quantum Razor: How Quantum Mechanics can reduce the complexity of classical models
- A practical, unitary simulator for non-Markovian complex processes
- The Computational Structure of Spike Trains
- A Note on Elementary Cellular Automata Classification
- Extreme dimensionality reduction with quantum modelling
- Complexity analysis of the stock market
- Optimal stochastic modelling with unitary quantum dynamics
- A Full Computation-relevant Topological Dynamics Classification of Elementary Cellular Automata
- Extreme Quantum Advantage for Rare-Event Sampling
- Superior memory efficiency of quantum devices for the simulation of continuous-time stochastic processes
- Unbounded memory advantage in stochastic simulation using quantum mechanics
- How to make dull cellular automata complex by adding memory: Rule 126 case study
- The classical-quantum divergence of complexity in modelling spin chains
- Towards Quantifying Complexity with Quantum Mechanics
- Strong and Weak Optimizations in Classical and Quantum Models of Stochastic Processes
- Memory-efficient tracking of complex temporal and symbolic dynamics with quantum simulators
- Robust inference of memory structure for efficient quantum modelling of stochastic processes
- Quantum coarse-graining for extreme dimension reduction in modelling stochastic temporal dynamics
- Surveying structural complexity in quantum many-body systems