Small-world complex network generation on a digital quantum processor

The study of emergent complexity shows that simple underlying rules can give rise to rich phenomena across biology, sociology, and physics. Classical cellular automata demonstrate such emergence, including oscillatory and self-replicating structures and even Turing completeness. However, the fundamental laws of nature are quantum mechanical, motivating the investigation of quantum cellular automata (QCA) as models of emergent complexity. Goldilocks QCA are a class where local neighborhood trade-offs drive complex behavior, previously shown to generate mutual information networks with large clustering, short path lengths, and broad node-strength distributions reminiscent of classical small-world networks. QCA have also been proposed as discretizations for simulations of strongly correlated matter, quantum field theories, and gravity. A core challenge is that classical simulation of large quantum dynamics is intractable, limiting theoretical exploration of QCA. In contrast, universal, gate-model quantum processors have matured and provide an ideal platform to experimentally realize and study QCA and their complexity features.

The work contrasts with prior uses of complex networks in quantum information: in one-way (measurement-based) quantum computing, complex graph states are engineered via projective measurements, while in the envisioned quantum internet, network structure is imposed by geographic channels (fiber or satellite), with satellite-based photonic networks exhibiting small-world connectivity. Here, complex networks of correlations emerge dynamically under unitary QCA evolution without a notion of physical distance beyond local interactions and on a general-purpose gate-model processor subject to realistic noise. More broadly, complex network measures—clustering, path length, and node strength distributions—have been widely applied to mutual information networks to uncover structure-function relationships in neuroscience (EEG and fMRI), model seismicity, and optimize routing in wireless networks, and to detect quantum critical points in models such as the Ising and Bose–Hubbard systems. This prior literature motivates using these measures to diagnose physical complexity in QCA-generated mutual information networks.

The authors implement a one-dimensional Goldilocks totalistic three-site QCA rule T with fixed (0) boundary conditions on a Sycamore-class superconducting processor (Weber, 53 qubits). Chains of high-quality qubits of length up to L = 23 are embedded from the 2D hardware graph. The QCA cycle comprises neighborhood-local unitaries compiled to hardware-native gates: the local update uses two non-Clifford controlled-Hadamard (CH) gates that apply a Hadamard to the center qubit iff exactly one neighbor is in state |1⟩ (the Goldilocks trade-off). Initialization is a classical product state with a single central bit flip |0…010…0⟩; measurement is in the computational z-basis after t cycles. Compilation with moment alignment and spin-echo insertion yields per-cycle gate counts of 4×(L−1) √iSWAP two-qubit gates and 8×L single-qubit PhXZ(α,x,z) gates; the native two-qubit interaction is modeled as √iSWAP×CPHASE(φ) with parasitic φ=π/2. Device characteristics (typical): ε1≈0.1% single-qubit error, ε2≈1.4% two-qubit error, readout errors εr0≈2%, εr1≈7%, and T1≈15 μs. To optimize performance the team employs: moment alignment, spin-echo insertion, Floquet calibration, parasitic cphase compensation, and post-selection. For each depth t, the circuit is sampled N=100,000 times; outcomes (L-bit strings) are collected over four distinct 1D chains and used to compute local populations ⟨n_i⟩ and classical Shannon mutual information I_ij between all qubit pairs as an adjacency matrix defining a weighted network per cycle. Post-selection enforces a dynamical invariant of rule T: measurements whose eigenvalue under the Ising-like operator Σ_i Z_i Z_{i+1} + 1 differs from that of the initial state (i.e., domain wall count) are discarded. To contextualize results, the authors also construct a post-selected incoherent uniformly random state by removing basis states violating the invariant and renormalizing, and compute its network measures. Network analysis includes weighted clustering coefficient (local transitivity), weighted shortest path length (global traversability), and node strength distributions, following standard definitions. Emulations provide noise-free baselines for all measures across system sizes.

• Population dynamics: Noise-free emulation shows coherent, non-equilibrating local populations forming characteristic diamond patterns over 30 cycles for L=21. On hardware, raw populations decohere by t≈10 due to photon loss, gate, and SPAM errors. Post-selection restores coherence in populations beyond t=10, with noticeable alignment to emulation up to about t≈15, though observables degrade at different rates.
• Clustering (local transitivity): Emulated clustering remains intermediate-to-large and slightly increases with system size (e.g., stabilizing around C≈0.3 for larger L). Raw hardware clustering briefly rises then decays toward zero (incoherent uniform limit) by t≈12 for L=15–19. Post-selected clustering tracks emulation closely until t≈6 and remains significantly above post-selected uniform randomness until t≈12, largely independent of L. There is a coherence window across sizes approximately 4≤t≤12 in which non-random complex networks are observed.
• Path length (global traversability): Cycle-and-chain-averaged weighted shortest path length l, within the coherence window and for L=5–23, is large and growing with L for raw data, while post-selected data closely matches emulation, trends downward with L, and is 1–2 orders of magnitude smaller than raw. Post-selected l is also comparable to that of the post-selected random benchmark but, together with elevated clustering, indicates small-world structure beyond post-selected randomness.
• Node strength distribution: Size-normalized node strengths P[g/(L−1)] for emulation and post-selected data are relatively flat across roughly 1×10^−2 to 2×10^−1, indicative of broad connectivity and hubs, unlike raw data which is biased to much smaller strengths, and distinct from the peaked profile of post-selected randomness.
• Scale and depth: The coherence window endpoint at t=12 for L=23 corresponds to 1,056 √iSWAP gates, showing a fixed-depth decoherence threshold largely independent of system size for these circuits.
• Proxy validity: Classical (Shannon) mutual information computed in the z-basis serves as a reliable proxy for quantum (von Neumann) mutual information for this QCA (shown in Supplementary), enabling post-selection-compatible network analysis on hardware.

The experiments demonstrate that a simple, local-update QCA rule can dynamically generate mutual information networks with hallmarks of small-world complexity—high clustering, short weighted paths, and broad node strengths—despite realistic noise on a gate-model processor. Post-selection based on a conserved domain-wall invariant is crucial to extend observable coherence and recover complex network features that otherwise vanish under decoherence. The observed coherence window, approximately independent of system size for the tested range, highlights a noise-limited but scalable depth for revealing emergent structure. Together, the elevated clustering beyond post-selected randomness and the low path length strongly support the emergence of nontrivial, traversable correlation networks rather than artifacts of post-selection or measurement bias. These findings substantiate QCA as a practical model for studying emergent quantum complexity on current hardware and suggest utility for simulating strongly correlated phenomena or demonstrating beyond-classical dynamics using network-level diagnostics.

The work realizes a one-dimensional Goldilocks QCA on a Sycamore-class superconducting processor and, through calibrated, error-mitigated measurements and complex network analysis, shows the formation of small-world mutual information networks within a fixed-depth coherence window. The approach combines efficient compilation, device calibrations, and invariant-based post-selection to recover coherent dynamics across system sizes up to L=23 and depths corresponding to over one thousand two-qubit gates. This establishes a template for experimentally probing QCA and their emergent complexity on near-term quantum hardware. Future directions include exploring other QCA rules and higher-dimensional automata, extending system sizes and depths with improved hardware fidelity, incorporating direct quantum mutual information and entanglement measures, reducing reliance on post-selection through error-corrected or error-suppressed operations, and applying QCA to simulate strongly correlated and field-theoretic models.

• Results rely on post-selection using a conserved domain-wall invariant; without it, observables rapidly decohere, and network measures collapse toward randomness by t≈10–12.
• Classical Shannon mutual information is used as a proxy for quantum mutual information; although justified for this QCA in Supplementary material, it does not capture all quantum correlations.
• Different observables (populations, clustering, etc.) degrade on different timescales; beyond t≈12, even post-selected network features diminish.
• Finite-size effects are present for smaller chains (L≤11), affecting averaged network measures.
• The study is limited to 1D chains and a specific Goldilocks rule with fixed boundary conditions and z-basis measurements, potentially restricting generality.
• Device noise (gate, readout, decoherence) constrains depth and necessitates error mitigation rather than error correction.