  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.

Quantum Physics;Quantum Gases;Statistical Mechanics;Cellular Automata and Lattice Gases;Pattern Formation and Solitons