Quantum cellular automata part I: Entanglement, physical complexity, and Goldilocks rules*

Cellular automata are interacting classical bits that display diverse 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. Complexity-generating QCA, termed Goldilocks rules, exhibit not only rich entanglement, but also persistent entropy fluctuations as well as network structure and dynamics consistent with complexity. In this talk we outline our QCA models and complexity analysis results for 1 dimensional systems. In addition to intuition-building case studies, we examine the effects of initial condition and local interaction phase on the network structure of QCA-generated quantum states, as quantified by scalar functions of the two-point quantum mutual information. In later talks, we will demonstrate that such physical complexity leads to robust correlations, a computational resource, in noisy intermediate scale quantum devices.