Quantum-inspired identification of complex cellular automata
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914721239662592 |
|---|---|
| author | Ho, Matthew Pradana, Andri Elliott, Thomas J. Chew, Lock Yue Gu, Mile |
| author_facet | Ho, Matthew Pradana, Andri Elliott, Thomas J. Chew, Lock Yue Gu, Mile |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2103_14053 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Quantum-inspired identification of complex cellular automata Ho, Matthew Pradana, Andri Elliott, Thomas J. Chew, Lock Yue Gu, Mile Quantum Physics Statistical Mechanics Information Theory Cellular Automata and Lattice Gases 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. |
| title | Quantum-inspired identification of complex cellular automata |
| topic | Quantum Physics Statistical Mechanics Information Theory Cellular Automata and Lattice Gases |
| url | https://arxiv.org/abs/2103.14053 |