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.

The inability of classical computers to simulate large quantum systems is a hindrance to understanding the physics of QCA, but quantum computers offer an ideal simulation platform. If time allows, I will discuss our recent experimental realization of QCA on a digital quantum processor, simulating a one-dimensional Goldilocks rule on chains of up to 23 superconducting qubits. Employing low-overhead calibration and error mitigation techniques, we calculate population dynamics and complex network measures indicating the formation of small-world mutual information networks. Unlike random states, these networks decohere at fixed circuit depth independent of system size, the largest of which corresponds to 1,056 two-qubit gates. Such computations may open the door to the employment of QCA in applications like the simulation of strongly-correlated matter or beyond-classical computational demonstrations.

References:

1.LE Hillberry, MT Jones, DL Vargas, P Rall, N Yunger Halpern, N Bao, S Notarnicola, S Montangero, LD Carr, “Entangled quantum cellular automata, physical complexity, and Goldilocks rules,” Quantum Science and Technology, v. 6, p. 045017 (2021)

2. EB Jones, LE Hillberry, MT Jones, M Fasihi, P Roushan, Z Jiang, A Ho, C Neill, E Ostby, P Graf, E Kapit, and LD Carr, “Small-world complex network generation on a digital quantum processor,” Nature Communications in press, https://arxiv.org/abs/2111.00167 (2022)

3. LE Hillberry, M Fasihi, L Piroli, N Yunger Halpern, T Prosen, and LD Carr, “Thermodynamics, scrambling, chaos, and integrability in quantum cellular automata,” in preparation (2021)