https://doi.org/10.1140/epjp/s13360-023-04160-5
Regular Article
Quantum-inspired identification of complex cellular automata
1
Institute of High Performance Computing (IHPC), Agency for Science, Technology and Research (A*STAR), 1 Fusionopolis Way, #16-16 Connexis, 138632, Singapore, Republic of Singapore
2
Nanyang Quantum Hub, School of Physical and Mathematical Sciences, Nanyang Technological University, 637371, Singapore, Singapore
3
Complexity Institute, Nanyang Technological University, 637335, Singapore, Singapore
4
Department of Physics and Astronomy, University of Manchester, M13 9PL, Manchester, UK
5
Department of Mathematics, University of Manchester, M13 9PL, Manchester, UK
6
Department of Mathematics, Imperial College London, SW7 2AZ, London, UK
7
Centre for Quantum Technologies, National University of Singapore, 3 Science Drive 2, 117543, Singapore, Singapore
8
MajuLab, CNRS-UNS-NUS-NTU, International Joint Research Unit UMI 3654, Singapore, Singapore
Received:
16
October
2022
Accepted:
4
June
2023
Published online:
19
June
2023
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.
Copyright comment Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
© The Author(s), under exclusive licence to Società Italiana di Fisica and Springer-Verlag GmbH Germany, part of Springer Nature 2023. Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
