Entangled quantum cellular automata, physical complexity, and Goldilocks rules
Logan Edward Hillberry, Matthew Timothy Jones, David L. Vargas, Patrick Rall, Nicole Yunger Halpern, Ning Bao, Simone Notarnicola, Simone Montangero, Lincoln D. Carr
Cellular automata are interacting classical bits that display diverse emergent behaviors, from fractals to random-number generators to Turing-complete computation. We discover that quantum cellular automata (QCA) can exhibit complexity in the sense of the complexity science that describes biology, sociology, and economics. QCA exhibit complexity when evolving under 'Goldilocks rules' that we define by balancing activity and stasis. Our Goldilocks rules generate robust dynamical features (entangled breathers), network structure and dynamics consistent with complexity, and persistent entropy fluctuations. Present-day experimental platforms- Rydberg arrays, trapped ions, and superconducting qubits- can implement our Goldilocks protocols, making testable the link between complexity science and quantum computation exposed by our QCA.
Cellular automata are interacting classical bits that display diverse emergent behaviors, from fractals to random-number generators to Turing-complete computation. We discover that quantum cellular automata (QCA) can exhibit complexity in the sense of the complexity science that describes biology, sociology, and economics. QCA exhibit complexity when evolving under 'Goldilocks rules' that we define by balancing activity and stasis. Our Goldilocks rules generate robust dynamical features (entangled breathers), network structure and dynamics consistent with complexity, and persistent entropy fluctuations. Present-day experimental platforms- Rydberg arrays, trapped ions, and superconducting qubits- can implement our Goldilocks protocols, making testable the link between complexity science and quantum computation exposed by our QCA.
Cellular automata are interacting classical bits that display diverse emergent behaviors, from fractals to random-number generators to Turing-complete computation. We discover that quantum cellular automata (QCA) can exhibit complexity in the sense of the complexity science that describes biology, sociology, and economics. QCA exhibit complexity when evolving under 'Goldilocks rules' that we define by balancing activity and stasis. Our Goldilocks rules generate robust dynamical features (entangled breathers), network structure and dynamics consistent with complexity, and persistent entropy fluctuations. Present-day experimental platforms—Rydberg arrays, trapped ions, and superconducting qubits—can implement our Goldilocks protocols, making testable the link between complexity science and quantum computation exposed by our QCA.
Complexity is an intuitively recognized feature of nature, but where does it come from? Is complexity only apparent at the classical level, or can it be found at the underlying quantum level as well? We approach these questions by exploring models consistent with basic quantum theory but which also hold promise for exhibiting complex behaviors – a set of models we call the quantum elementary cellular automata (QECA). Previously, various quantum cellular automata models have been studied for both their quantum information theoretic properties and their ability to simulate key physics equations like the Schrodinger and Dirac equations. We take the unique approach of analyzing QECA as complexity-generating systems. Doing so requires a more precise notion of what we mean by complex. This is done by proposing nine axes of complexity along which the complexity of any system may be quantified. When applied to QECA, we find evidence of complexity using three of these axes, namely diversity, persistent dynamical macrostates, and connectivity. The studies presented are numerical simulations done without approximation using highly optimized exact diagonalization code which supports a Hilbert space of up to 2^27 dimensions. The code is written entirely in the high-level open source programming language Python, making it easily expandable to future projects requiring exact simulation of quantum systems. A careful description of an algorithm critical to our method as well as our use of high performance computing resources on a cluster supercomputer is given. Powerful quantifiers of entanglement and connectivity such as von Neumann entropy and complex network measures computed on quantum mutual information adjacency matrices provide analysis tools for the simulations. Each network measure is defined then tested on well-characterized entangled states from quantum information theory, like the GHZ and W states and singlet state arrays. The network measures known as network density, clustering coefficient, and disparity are specifically considered. We find these network measures offer unique information regarding the structure of two point correlations in the states produced by QECA dynamics, as compared to each other and as quantified by a principal component analysis. Using such measures, we address the complexity of QECA models at three levels of specificity. First, a broad analysis of tens of thousands of simulations gives an overview of the variety of dynamics available to the models. We quantify the diversity of our simulations as the density of simulations which appear, on average, unlike typical entangled quantum states. Second, a more selective analysis identifies QECA by their complexity dynamics, in the frequency domain. A few QECA which exhibit persistent dynamical macrostates in the form of highly structured entanglement are also described. Entanglement dynamics are quantified by the distribution of changes in bond entropy (the von Neumann entropy of all bipartitionings of the QECA system). Finally, we take a detailed…
Quantum cellular automata (QCA) evolve qubits in a quantum circuit depending only on the states of their neighborhoods and model how rich physical complexity can emerge from a simple set of underlying dynamical rules. The inability of classical computers to simulate large quantum systems hinders the elucidation of quantum cellular automata, but quantum computers offer an ideal simulation platform. Here, we experimentally realize QCA on a digital quantum processor, simulating a one-dimensional Goldilocks rule on chains of up to 23 superconducting qubits. We calculate calibrated and error-mitigated population dynamics and complex network measures, which indicate the formation of small-world mutual information networks. These networks decohere at fixed circuit depth independent of system size, the largest of which corresponding to 1,056 two-qubit gates. Such computations may enable the employment of QCA in applications like the simulation of strongly-correlated matter or beyond-classical computational demonstrations.
One can think of some physical evolutions as being the emergent-effective result of a microscopic discrete model. Inspired by classical coarse-graining procedures, we provide a simple procedure to coarse-grain color-blind quantum cellular automata that follow the so-called Goldilocks rules. The procedure consists in (i) space-time grouping the quantum cellular automaton (QCA) in cells of size N; (ii) projecting the states of a cell onto its borders, connecting them with the fine dynamics; (iii) describing the overall dynamics by the border states, that we call signals; and (iv) constructing the coarse-grained dynamics for different sizes N of the cells. A by-product of this simple toy model is a general discrete analogous of the Stokes law. Moreover we prove that in the space-time limit, the automaton converges to a Dirac free Hamiltonian. The QCA we introduce here can be implemented by present-day quantum platforms, such as Rydberg arrays, trapped ions, and superconducting qubits. We hope our study can pave the way to a richer understanding of those systems with limited resolution.
This paper proposes a novel model utilizing Quantum Cellular Automata (QCA) to simulate complex system evolution. The core idea involves transforming classical Cellular Automata (CA) into QCA, incorporating quantum phenomena such as superposition and entanglement to model intricate dynamics. This approach offers a fresh perspective on complex system modeling by leveraging the principles of quantum mechanics. The model's design incorporates key QCA mechanisms, including the Bloch sphere representation of states and the application of unitary transformations to govern cell interactions. We present a foundational framework for QCA simulation and discuss potential applications in areas such as pattern formation, reaction-diffusion processes, and emergent behavior. The focus is on demonstrating the theoretical feasibility and outlining a methodology for future research, rather than presenting empirical experimental results. This work emphasizes the conceptual shift and potential computational advantages offered by QCA in understanding complex systems.
One can think of some physical evolutions as being the emergent-effective result of a microscopic discrete model. Inspired by classical coarse graining procedures, we provide a simple procedures to coarse-grain color-blind quantum cellular automata, following Goldilock rules. The procedure consists in (i) space-time grouping the quantum cellular automaton (QCA) in cells of size N, (ii) projecting the cells states onto its borders, connecting them with the fine dynamics, which is reminiscent of the edge-bulk correspondence in quantum field theory; (iii) describe the overall dynamics by the border states, that we call signals; (iv) construct the coarse-grained dynamics for different sizes N of the cells. A byproduct of this simple toy-model is a general discrete analogous of the Stokes law. Moreover, we proved that in the spacetime limit, the automaton converge to a Dirac free Hamiltonian. The QCA we introduced here, can be implemented by present-day quantum platforms, such as Rydberg arrays, trapped ions, and superconducting qbits. We hope our study can pave the way to a richer understanding of those systems with limited resolution.