A review of Quantum Cellular Automata

1 Introduction

• QCAs are quantum extensions of cellular automata whose unitary dynamics preserve locality, overcoming classical limitations in describing entanglement and enabling universal quantum computation.Their locality-preserving definition captures discrete relativistic causality, and any such QCA can be represented by a local finite-depth circuit with local ancillas.Source: §1 · pp. 4–5
• QCAs provide discrete models of physics and quantum field theory with strict information-speed bounds and lattice cutoffs, while also supporting Floquet-phase classification through one-dimensional index theory [25].The review also discusses their use in quantum simulation and topological phases, including a three-dimensional model whose boundary behavior is tied to whether a disentangling QCA is trivial [27].Source: §1 · pp. 5–6

1.1 Two examples of QCAs

• A depth-two circuit of local two-qubit unitaries illustrates locality preservation, while the shift QCA shows that some QCAs cannot be expressed as constant-depth circuits.In the Heisenberg picture, the shift maps an operator at site n to site n−1 and spreads local operators only a finite distance.Source: §1.1 · pp. 6–7

1.2 Things that are not QCAs

• The review distinguishes QCAs from discrete-time quantum walks, quantum dot cellular automata, continuous-time Hamiltonian models, and classical cellular-automaton interpretations of quantum mechanics.These alternatives differ respectively in particle-sector scope, implementation paradigm, continuous-time evolution, or inability to reproduce entanglement correlations.Source: §1.2 · pp. 7–8

2.1 Systems

• Systems consist of finite-dimensional qudits or finitely many fermion modes on finite or infinite lattices, while truly bosonic local Hilbert spaces are excluded from the review.Infinite lattices are treated using quasi-local algebras because naive infinite tensor products are not well-defined; finite lattices suffice for many locality-preserving arguments.Source: §2.1 · pp. 8–9

2.2 Dynamics

• In the Heisenberg picture, QCA evolution maps observables by an automorphism or unitary, and locality preservation is determined by how single-site algebras spread to finite neighbourhoods.Translational invariance is optional, although it enables additional results; control spaces and families of QCAs provide an alternative to fixing one lattice.Source: §2.2 · pp. 9–10

2 Definition

• A QCA is a discrete-time locality-preserving automorphism or unitary on a finite or infinite discrete hypercubic lattice containing finite quantum systems at each site.Locality preservation requires a finite range l such that an operator at site n evolves within sites m satisfying |n−m|≤l.Source: §2.2 · p. 10

2.3 Global and local transition rules

• Local transition rules define a valid global QCA exactly when each local map is an isomorphism and images of distinct-site algebras commute; translational invariance reduces verification to finitely many overlapping neighbourhoods.The wrapping lemma gives a one-to-one correspondence between sufficiently large periodic finite-lattice QCAs and translationally invariant infinite-lattice QCAs, with a fermionic generalization [64].Source: §2.3 · pp. 11–12

2.4 Finite, unbounded configurations

• Finite, unbounded configuration QCAs are special cases of the quasi-local-algebra framework, but they require a quiescent reference state and cannot directly represent QCAs lacking an invariant pure product state.More generally, an invariant state yields a GNS representation with unitary dynamics; product states recover finite, unbounded configurations, whereas entangled vacua motivate finite, unbounded excitations [66].Source: §2.4 · pp. 12–13

3.1 Partitioning schemes

• Partitioned QCAs compose local unitaries on non-overlapping supercells across several lattice partitions, yielding manifestly unitary finite-depth circuit constructions.Their dynamics is u1 ◦...◦ uP, with commuting products within each partition; these constructions have been used to establish QCA universality for quantum computation.Source: §3.1 · pp. 13–14, §3 · p. 13
• Watrous partitioned QCAs combine partial shifts with on-site unitaries, propagating different subsystems while retaining automorphism structure and modeling particle interactions.Each site contains left-, center-, and right-moving subcells; these automata are a special case of quantum lattice gas automata.Source: §3.1 · p. 15, Figure 6 · p. 15
• The partitioning scheme makes constructing non-unitary QCAs straightforward by replacing local unitaries with local completely positive trace-preserving maps, including an irreversible QCA realizing a quantum version of classical rule 110.Source: §3.1 · p. 14

3.2 Clifford QCAs

• Clifford QCAs preserve products of generalized Pauli operators, enabling their dynamics to be represented by a classical nearest-neighbour cellular automaton and making them efficiently classically simulatable.On a line, their dynamics fall into glider, periodic, or fractal classes; the latter exhibit self-similar spacetime structure.Source: §3.2 · pp. 15–17
• Translationally invariant Clifford QCAs have strong structural classifications: one-dimensional qubit models are generated by standard families, while every such qudit QCA becomes trivial after its fourth power [69, 76].Nearest-neighbour qubit QCAs decompose into shifts, on-site unitaries, and controlled phase gates, and every two-dimensional QCA is known to be trivial [63] [76].Source: §3.2 · p. 17

4 QCAs as quantum computers

• QCAs were originally proposed for quantum computation and can efficiently simulate quantum Turing machines with only constant slowdown.Together with efficient circuit-model simulation of QCAs, this establishes computational equivalence between the models; the review restricts this section to translationally invariant QCAs.Source: §4 · pp. 17–18

4.1 A QCA efficiently simulating quantum circuits

• A translationally invariant two-dimensional QCA encodes program and input data in its initial state and efficiently simulates any quantum circuit using a universal gate set [79].Data moves across the torus, encountering program qubits, and the output is read from column r after r timesteps.Source: §4.1 · pp. 18–19

4.2 Other ideas

• A one-dimensional QCA with 12-dimensional cells can simulate quantum circuits universally and autonomously encode externally selected automorphisms in its initial state.This construction follows a proof that classically controlled QCAs can be simulated without external control, with a larger local state space.Source: §4.2 · p. 20
• Fermionic QCAs and qudit QCAs efficiently simulate one another directly, with constant slowdown in both directions [57].This provides a QCA analogue of the equivalence between fermionic and qubit quantum circuits.Source: §4.2 · p. 20

4.3 Implementations

• Periodic atomic-species schemes can implement universal computation, while proposals using endohedral fullerenes and ultracold Rydberg atoms suggest experimental and optimization applications [88] [94].These implementations rely on independently addressing species or tuning QCA dynamics; Rydberg proposals also target variational optimization and entangled steady-state engineering.Source: §4.3 · p. 20
• Despite requiring only global operations, QCAs lack a well-developed error-correction theory, while current hardware development emphasizes few-qubit addressability and circuit-model architectures.Two-dimensional constructions may also be difficult to implement in laboratories, motivating one-dimensional alternatives.Source: §4.2 · p. 19, §4.3 · pp. 20–21

5 Structure of QCAs

• QCA structure is characterized through one-dimensional index theory, two-dimensional index-and-topology classifications, finite-depth circuit representations with local ancillas, and tensor-network operators.In one dimension, index theory classifies when QCAs can be smoothly deformed while preserving locality; in two dimensions, qudit QCAs are classified using indices and the topology of the underlying space.Source: §5 · p. 21

5.1 Unitarity plus causality implies localizability

• A QCA and an identical copy evolving under inverse dynamics can be combined to decompose the joint evolution using local swaps.The inverse evolution preserves locality, so conjugated swaps remain localized on inverse neighbourhoods.Source: §5.1 · p. 21
• The localizability theorem was first established for qudit QCAs on infinite lattices without translational invariance and later extended to fermions and bosons.Source: §5.1 · p. 21
• The joint QCA dynamics therefore admits a finite-depth circuit implementation, with all swaps and non-overlapping conjugated swaps executed in parallel.The minimum depth is max_n |N_B(n)|+1, where N_B(n) is the neighbourhood under the copy’s unitary U_B.Source: §5.1 · p. 21
• The result was generalized to dynamical graphs [96], allowing QCA neighbourhoods to change over time for discrete quantum-gravity models with evolving spatial geometry.Source: §5.1 · p. 22

5.2 Index theory in one dimension

• The QCA index quantifies quantum information moving along a one-dimensional lattice and can be computed locally, even without translational invariance.For qudits, the index is a non-zero rational number; it is determined by how local operator algebras move left at each timestep.Source: §5.2 · p. 22

5.2.1 Qudit index theory

• Qudit index theory uses regrouping, support algebras, and even/odd algebras to define a position-independent index describing information moving right or left.A right shift has ind[s] = d, a left shift has ind[s−1] = 1/d, and finite-depth circuit QCAs have ind[u] = 1.Source: §5.2.1 · pp. 22–23

Properties of the index

• The index is invariant under regrouping, multiplicative under composition and tensor products, and equals one exactly for finite-depth circuit QCAs.It also classifies continuous deformations with fixed cell structure and remains unchanged under additional local unitaries, making it robust to these perturbations.Source: Properties of the index · p. 24

5.2.2 Another formula for the index

• A second index formula measures overlaps between subalgebras using the normalized trace and is useful for topological-phase applications and proofs of index properties.The review also notes a formulation using Jones indices for suitable type II1 factors [33].Source: §5.2.2 · pp. 24–25

5.2.3 Fermionic index theory

• Fermionic index theory extends the qudit construction with graded commutators but allows a factor of root two, yielding richer values and inequivalences than in qudit QCAs.Purely fermionic systems have ind[u] = 2^n/2, while hybrid systems can realize the broader values in equation (48); the Majorana shift is a square root of the fermionic shift, unlike qubit shifts.Source: §5.2.3 · pp. 25–26

Scope and status

• The classification of two-dimensional qudit QCAs on finite lattices is complete, without assuming translational invariance, but completeness is not expected for higher-dimensional lattices and fermionic applicability remains unclear [63].The classification depends on the topology of the control space.Source: §5.3 · p. 27

Equivalence relation

• Stable path equivalence permits locally adding ancillas and connecting QCAs by a continuous bounded-range path, generalizing equivalence up to finite-depth local circuits [63].Ancillas are treated as additional sites with a one-to-one correspondence between the compared systems.Source: §5.3 · p. 27

Classification mechanism

• Dimensional reduction regroups sites along a lattice direction, lowering the spatial dimension while increasing each cell’s Hilbert-space dimension, and applies one-dimensional indices along multiple directions [63].The resulting classification also depends on the first homology group and torsion of the underlying spatial manifold.Source: §5.3 · p. 27, Figure 10 · p. 27

Examples

• On a discrete torus, a shift along one coordinate line has index d under one reduction but index 1 along the other, whereas a diagonal shift has non-unit index under either reduction.These examples distinguish non-equivalence to the identity and demonstrate direction-dependent versus direction-independent index behavior.Source: §5.3 · p. 27

Topological structure

• The topology of the control manifold governs shift-loop equivalence: first homology tracks noncontractible loops, while torsion can contract apparently nontrivial loop pairs, as on a Klein bottle [63].On the plane, which loops are equivalent depends on the holes in the manifold.Source: §5.3 · pp. 27–28

• The one-dimensional index is a group homomorphism from QCAs to a subgroup of the reals, restricted to rationals for qudit QCAs.Source: §5.4 · pp. 28–29
• On infinite systems, composing QCAs preserves the QCA property because the composite range is at most the sum of the two finite ranges.For finite systems, repeated products can produce ranges comparable to system size, motivating control-space formulations.Source: §5.4 · p. 29
• Coherent families require successive QCAs to be stably path equivalent, linking their members through finite-depth local circuits.In the circle shift example, adding ancillas and applying neighboring swaps transforms ui ⊗1 into ui+1.Source: §5.4 · p. 29
• Coherence excludes unnatural families with unrelated members, while translationally invariant Clifford QCAs in any dimension and translationally invariant QCAs in three dimensions yield coherent families for suitable subsequences.It remains unclear whether every seemingly natural QCA family is coherent.Source: §5.4 · p. 29
• Modulo finite-depth quantum circuits, the group of QCAs is abelian, and ancilla removal often eliminates the need to append ancillary sites.The ancilla-removal construction may increase circuit depth and range by reorganizing a timestep into sub-timesteps and reusing temporarily inactive sites.Source: §5.4 · p. 29

5.5 Margolus partitioning

• Margolus partitioning constructs QCAs from local unitary maps between subsystems rather than unitaries acting directly on subsystems, and applies on finite or infinite lattices.This distinguishes the method from local finite-depth circuit QCAs.Source: §5.5 · p. 30
• The construction groups neighboring sites into supercells and alternates unitary maps W_m and V_m after commuting subalgebras generate each supercell algebra.For one-dimensional qudits, the supercell contains two sites; higher dimensions use larger cubes.Source: §5.5 · p. 30
• The scheme represents shift QCAs that cannot be expressed as local unitary circuits, so Margolus-partitioned QCAs need not be implementable by constant-depth quantum circuits.The distinction arises because Margolus constructions use unitary maps between systems, whereas circuit descriptions use unitaries on systems.Source: §5.5 · p. 30
• Every one-dimensional QCA with d-dimensional qudits admits a Margolus-partitioned form, but this universality fails in higher dimensions because of a two-dimensional counterexample [65].Higher-dimensional QCAs can nevertheless be constructed using Margolus partitioning, with applications including.Source: §5.5 · p. 30

Matrix product unitaries

• Translationally invariant one-dimensional qudit QCAs are equivalent to finite-bond-dimension matrix product unitaries, and the converse also holds.The tensor-network construction rewrites local QCA maps into local tensors and also provides a different derivation of the QCA index [105].Source: §5.6 · pp. 30, 32
• Without translational invariance, a matrix product unitary need not be a QCA because it may fail to preserve locality, as shown by a generalized CNOT controlled from one lattice site.The example is defined by only two position-dependent tensors but is not locality preserving.Source: §5.6 · pp. 30, 32, 33

Symmetry classification

• With on-site unitary symmetries, one-dimensional matrix product unitaries are completely classified by the QCA index and the bond-index representation’s cohomology class.The classification allows ancillas transforming under arbitrary symmetry-group representations; restricted ancilla choices yield a refinement that remains incomplete.Source: §5.6 · p. 33

Fermionic QCAs

• Fermionic matrix-product-state definitions initially miss some fermionic QCAs, including the Majorana shift, but ancillary degrees of freedom yield tensor networks containing all fermionic QCAs [110].This extended framework also re-derives the fermionic QCA index.Source: §5.6 · p. 33

Higher-dimensional and non-unitary extensions

• In any spatial dimension, qudit QCAs admit tensor-network-unitary descriptions with system-size-independent bond dimension when tensors satisfy simplicity, implying an area law for QCA-generated entanglement [62].The formalism extends to completely positive trace-preserving dynamics, although system-size-independent bond dimension is not always sufficient there.Source: §5.6 · p. 33

6 QCAs in physics

• QCAs arise as effective models or simulators for Floquet and other physical systems because they impose a strict maximum propagation speed.This speed may correspond to the speed of light, speed of sound, or a Lieb-Robinson velocity, depending on the system being approximated.Source: §6 · p. 33

6.1 QCAs vs Hamiltonian dynamics

• Continuous-time Hamiltonian evolution cannot be strictly locality preserving: information spreads immediately, although its amplitude outside the initial region may be very small.This motivates discrete time when strictly locality-preserving lattice dynamics are required.Source: §6.1 · p. 34
• QCAs approximate periodically driven systems using Lieb-Robinson bounds, while associated Hamiltonians may be nonunique and nonlocal, and QCAs lack a natural ground-state energy ordering.The effective Floquet unitary is generally not strictly locality preserving, but can be approximated well by a QCA.Source: §6.1 · pp. 34–35

6.2 Dynamical topological phases in Floquet systems

• In interacting Floquet systems, a four-step swap QCA has trivial bulk evolution but chiral boundary propagation whose QCA index classifies the dynamical topological phase.Layering opposite evolutions realizes any boundary index d1/d2; many-body localization is required for stability against bulk perturbations, and the boundary unitary is classified through Y = (Ulc)†Udyn.Source: §6.2 · pp. 36–37

6.3 Understanding phases of matter

• The three-dimensional 3-fermion Walker-Wang model yields a Clifford QCA disentangler that is nontrivial, suggesting that realizing its boundary topological order with a two-dimensional commuting-projector Hamiltonian is impossible.The theorem that any locally flippable separator can be mapped to a trivial separator by a QCA supplies the disentangling mechanism for the model’s ground state.Source: §6.3 · pp. 38–39
• A 4+1-dimensional Z2-symmetric model realizes a nontrivial boundary QCA outside cohomology classification and inequivalent to any finite-depth circuit.The QCA effectively realizes the symmetry on a 3+1-dimensional boundary.Source: §6.3 · p. 39

6.4 QCAs and particles

• Discrete-time quantum walks restrict lattice particles to bounded hopping and can converge to relativistic dynamics, with classified symmetry-protected topological phases,.They also have applications in quantum computing.Source: §6.4 · p. 40
• The one-dimensional walk converges on smooth low-momentum states to the Dirac equation H = Pσz + mσx, while the three-dimensional construction converges to the Weyl equation H = P⃗·σ and extends to massive Dirac dynamics.These models support analyses including mass-induced chirality mixing and Zitterbewegung [38], with rigorous convergence results for the three-dimensional case.Source: §6.4 · pp. 40–41

6.4.1 Lattice gases

• Quantum lattice gases combine propagation with on-site scattering, and their interaction phase can mix left- and right-moving particles while preserving the empty state.The interaction phase applied when both particle types are present provides an on-site interaction while retaining the original single-particle walk.Source: §6.4.1 · pp. 41–42

6.4.2 Fermions

• Fermionic second quantization yields locality-preserving QCAs whose added on-site phase produces the interacting Thirring QCA.The construction reproduces the single-particle walk in the one-particle sector, and the interaction phase acts when two particles occupy one site.Source: §6.4.2 · p. 43

6.5 Quantum field theory

• QCAs provide strictly causal discrete models for QFTs, including interacting examples, but discretization breaks Lorentz symmetry and requires an entangled vacuum rather than the naive empty state [162–164].The QCA vacuum can converge to the quantum-field vacuum for the one-dimensional massless Dirac model [57], while a QCA theory of light recovers Maxwell’s equations but has unclear local coupling to matter.Source: §6.5 · pp. 43–45

Future prospects

• Future QFT discretizations may extend from existing QCA representations of Dirac fermions to non-abelian gauge theories and potentially the Standard Model, but fermion doubling remains a major obstacle.Several efforts are already pursuing QFT discretizations in terms of QCAs.Source: §7 · p. 45
• Combining QCA disentanglers with tensor-network representations could advance the study and classification of topological phases, building on the higher-dimensional matrix-product-unitary/QCA correspondence solved in [62].Tensor networks are emphasized as useful for understanding symmetry roles in phase classifications.Source: §7 · p. 45

Open problems

• A comprehensive theory of QCA quantum computation remains open, including meaningful error correction and justification for using QCAs rather than circuit or measurement-based models.The question becomes especially important when computation requires many distinct single- or two-qubit gates instead of a small set of global operations.Source: §7 · pp. 45–46
• Fully classifying QCAs beyond two dimensions remains open, including identifying extra invariants and determining how classifications depend on allowed equivalences such as appended ancillas.Two-dimensional classification by index and control-space topology is described as elegant and complete.Source: §7 · p. 46
• Open locality questions ask which results survive for essentially local QCAs with approximately locality-preserving dynamics and suitably decaying tails, especially in Floquet-phase models.These systems contrast with the review’s strictly locality-preserving QCAs.Source: §7 · p. 46
• Irreversible QCAs lack a physically motivated axiomatization and useful structure theorems, although tensor-network methods have enabled general investigations and may support classification [52] [62].Finite-depth circuits of local completely positive trace-preserving maps provide constructive examples, while even probabilistic classical cellular automata are difficult to axiomatize.Source: §7 · p. 46
• Further open directions concern quasi-local algebra structure, invariant low-entanglement states, and symmetry-protected classifications of QCAs, with boundary algebras, local constraints, and matrix-product-unitary methods offering starting points [52] [76].One-dimensional progress already covers some unitary and antiunitary symmetries, while higher-dimensional boundary algebras yield nontrivial quasi-local decompositions.Source: §7 · p. 46
• Taking continuum limits beyond currently integrable QCA models remains unresolved, including whether second-order phase transitions have an analogue and how path-integral or general-limit frameworks may help [22] [184].Coherent families [103] and abstract QCA generalizations [185] are also identified as potentially relevant.Source: §7 · p. 46

Representations

• The abstract C*-algebra is essential because infinite systems can have inequivalent Hilbert-space representations, a phenomenon related to superselection sectors.The review cites [59] for C*-algebra basics and for superselection sectors.Source: A Infinite systems and quasi-local… · p. 47

Quasi-local algebra

• A quantum lattice assigns finite-dimensional C*-algebras to sites and finite regions, whose tensor products embed into a completed algebra containing local and quasi-local elements.Finite-region norms agree with corresponding operator norms, while quasi-local elements are norm-approximable by sums of local elements.Source: A Infinite systems and quasi-local… · p. 47

States

• States are positive normalized functionals; for quasi-local systems they can equivalently be specified by finite-region density operators satisfying consistency under restriction.For finite-dimensional algebras, this recovers the density-matrix expression ρ(A) = tr[ρA].Source: A Infinite systems and quasi-local… · p. 48

GNS construction

• The GNS construction turns any state into a cyclic Hilbert-space representation, unique up to unitary equivalence among cyclic representations.The construction uses the state to define an inner product and realizes algebra elements as operators on the resulting Hilbert space.Source: A Infinite systems and quasi-local… · p. 48

Automorphisms

• Although every automorphism is unitarily implementable in its associated cyclic representation, applying Pauli X at every lattice site is not implementable in the all-up spin representation.Flipping every spin from up to down produces a state outside the Hilbert space, so the global operation cannot be represented by an allowed unitary there.Source: A Infinite systems and quasi-local… · p. 49

• Fermionic QCAs assign fermionic modes to lattice sites, with creation and annihilation operators obeying anticommutation relations; hybrid qudit–fermion systems are also possible.The operator label can range over lattice indices such as Z^d or, for simplicity, Z.Source: B QCAs with fermions · p. 49
• Anticommutation implies that each mode has occupation number 0 or 1, so a†_α|0⟩ represents a single fermion and no mode can contain more than one.The empty state |0⟩ serves as the vacuum, including through a positive normalized functional for infinite lattices.Source: B QCAs with fermions · p. 50
• Fermionic systems can equivalently use self-adjoint Majorana operators or quasi-local fermionic algebras, whose operators in distinct regions anticommute rather than commute.The quasi-local construction otherwise parallels the qudit case by assigning algebras to lattice regions.Source: B QCAs with fermions · p. 50
• Graded algebras classify operators and states as even or odd according to fermion-number parity, with even operators preserving parity and odd operators exchanging the even and odd subspaces.This grading also extends to hybrid qudit–fermion systems.Source: B QCAs with fermions · p. 50
• The graded commutator reduces to the ordinary commutator when either operator is even, while graded tensor products compose graded Hilbert spaces and algebras with parity-sensitive commutation.Two algebras graded commute when their graded commutator vanishes for every pair of elements.Source: B QCAs with fermions · p. 50