PaperlayerView exact revision on arXiv

Source-linked AI summary

A review of Quantum Cellular Automata

Terry Farrelly

arXiv:1904.13318v2quant-ph

TL;DR

The review surveys how quantum cellular automata formalize discrete quantum dynamics with strict locality, and synthesizes their roles in computation, Floquet phases, topological matter, and quantum field theory. It develops their algebraic and circuit-based structure, including index theory and higher-dimensional classifications, while identifying unresolved classification and representation limits.

  • Problem

    QCAs address how quantum systems can be modeled on discrete spacetime while enforcing a strict bound on information propagation, a need motivated by limitations of classical cellular automata for quantum physics.

  • Method

    The review synthesizes QCA definitions, circuit and algebraic constructions, index theory, Clifford classifications, and applications across quantum computation and physics.

  • Results

    QCA methods classify chiral phases of Floquet systems through a robust one-dimensional index, while higher-dimensional index classification is complete for two-dimensional qudit QCAs on finite lattices.

  • Takeaways & Limitations

    QCAs provide a framework connecting locality-preserving quantum dynamics with quantum computation, Floquet phases, topological matter, and discretized quantum field theory.

  • Takeaways & Limitations

    Complete QCA classification in dimensions greater than two remains open, and finite, unbounded configuration representations do not cover all translationally invariant QCAs without local ancillas.

Abstract

from arXiv · show

Discretizing spacetime is often a natural step towards modelling physical systems. For quantum systems, if we also demand a strict bound on the speed of information propagation, we get quantum cellular automata (QCAs). These originally arose as an alternative paradigm for quantum computation, though more recently they have found application in understanding topological phases of matter and have been proposed as models of periodically driven (Floquet) quantum systems, where QCA methods were used to classify their phases. QCAs have also been used as a natural discretization of quantum field theory, and some interesting examples of QCAs have been introduced that become interacting quantum field theories in the continuum limit. This review discusses all of these applications, as well as some other interesting results on the structure of quantum cellular automata, including the tensor-network unitary approach, the index theory and higher dimensional classifications of QCAs.

1 Introduction

QCAs extend cellular automata to quantum systems while preserving locality and discrete-time evolution. The review introduces their origins, basic constructions, and applications in computation, quantum field theory, Floquet systems, and topological phases.

  • Classical cellular automata: Classical cellular automata use uniform local update rules on discrete lattices and can efficiently simulate Turing machines.Rule 110 is a one-dimensional example whose updates depend on a bit and its two nearest neighbours.
  • From CAs to QCAs: QCAs provide a quantum alternative to cellular automata because classical automata cannot reproduce phenomena such as Bell inequality violation.The motivation is to retain discrete, local dynamics while describing quantum physics.
  • Quantum computation: Early QCA proposals supported universal quantum computation, including models that efficiently simulate a quantum Turing machine.Some proposals used classically controlled, translationally invariant global unitaries.
  • From CAs to QCAs: Constructing QCAs is nontrivial because linear extensions of classical rules can fail, and quantum systems cannot copy cell states because of the no-cloning theorem.Constructive approaches use finite-depth circuit layers and shifts; later axiomatic definitions captured the intended quantum and local structure.
  • Physics applications: QCAs offer discrete models of quantum field theory with a strict information-speed bound and a lattice cutoff, though their advantages remain uncertain.The review also discusses their use for Floquet systems, where QCA index theory classifies chiral phases and boundary dynamics.
  • Basic examples: A depth-two circuit applies alternating layers of two-qubit local unitaries over one timestep.The review contrasts these circuits with shifts, which move each subsystem one site and are important QCA building blocks.

2 Definition

The review defines QCAs on discrete quantum lattices through locality-preserving dynamics, treating finite and infinite systems with observable algebras. It also relates local rules to global automorphisms and explains the scope of finite, unbounded configuration representations.

  • Quantum lattice systems: QCAs act on discrete lattices whose sites contain finite-dimensional qudits or finitely many fermion modes.The review mainly considers finite or infinite lattices, including periodic finite systems.
  • Quasi-local algebras: For infinite lattices, the review uses quasi-local algebras because unrestricted infinite tensor products are not well-defined.This approach restricts observables to local operations and provides the framework used for infinite systems.
  • Dynamics: QCA dynamics are locality-preserving automorphisms: local operators evolve into operators supported within a nearby finite region.The Heisenberg-picture formulation makes this condition explicit.
  • Local and global rules: A local rule maps each site algebra into a neighbouring region, while compatibility conditions ensure that the resulting global map is an automorphism.The result extends from one-dimensional translationally invariant qudit QCAs to non-translationally invariant and higher-dimensional systems.
  • Finite, unbounded configurations: Finite, unbounded configuration QCAs can be represented through invariant states and are special cases of the quasi-local algebra formulation.This representation is useful for describing localized excitations above an invariant vacuum-like state.
  • Finite, unbounded configurations: The finite, unbounded configuration picture does not represent every translationally invariant QCA without adding local ancillas.The obstruction is that such QCAs need not possess an invariant pure product state.

3 More examples of QCAs

QCAs can be built by combining shifts, on-site unitaries, and finite-depth partitioned circuits. Clifford QCAs form a structured class with efficient classical simulation, distinct dynamical behaviors, and broad one-dimensional coverage.

  • Partitioning schemes: Partitioned QCAs apply local unitaries to non-overlapping supercells across one or more lattice partitions in sequence.Different layers commute internally because their unitaries act on disjoint regions.
  • Partitioning schemes: Watrous partitioned QCAs combine conditional partial shifts with products of on-site unitaries.Each site can contain left-moving, stationary, and right-moving subsystems.
  • Structure of examples: Many QCA constructions are trivial because, after adding ancillary degrees of freedom, they decompose into a finite-depth circuit followed by shifts.The review emphasizes that this technical label does not imply practical unimportance.
  • Clifford QCAs: Clifford QCAs preserve products of generalized Pauli operators and therefore admit efficient classical simulation, although they are not universal under standard assumptions.Their structure makes them useful for studying QCA dynamics and related quantum-information problems.
  • Clifford QCAs: Clifford QCAs on a line divide into glider, periodic, and fractal classes.Fractal examples are self-similar on large scales of spacetime diagrams.
  • Clifford QCAs: Equation (15), supplemented by on-site Clifford operations and shifts, generates all translationally invariant qubit Clifford QCAs in one dimension.For qudit Clifford QCAs, the fourth power of any translationally invariant example is trivial.

4 QCAs as quantum computers

QCAs were introduced as an alternative model of quantum computation and can efficiently simulate quantum Turing machines and circuits. Translationally invariant constructions encode program information into initial states, while one-dimensional universal QCAs address practical limitations of two-dimensional layouts.

  • Quantum-computational universality: QCAs can efficiently simulate quantum Turing machines with only constant slowdown using Watrous partitioned constructions.The circuit model can also efficiently simulate QCAs.
  • A QCA efficiently simulating quantum circuits: A translationally invariant QCA on a two-dimensional torus encodes program gates and input data in its initial state.Data columns move across program columns and encounter gates encoded there.
  • A QCA efficiently simulating quantum circuits: After r timesteps, the output can be read from column r, and the construction efficiently simulates any quantum circuit.The chosen local gates implement a universal gate set on the data qubits.
  • One-dimensional QCAs: The two-dimensional circuit-mapping method may be difficult to implement in a laboratory, motivating one-dimensional alternatives.A universal one-dimensional QCA was constructed with 12-dimensional quantum systems at each cell.
  • Intrinsic universality: Intrinsic universality asks whether regrouping cells lets one QCA simulate any other QCA, and n-dimensional examples have been found.This is distinct from simulating quantum circuits or quantum Turing machines.

5 Structure of QCAs

The review develops structural results for QCAs through locality-preserving dynamics, index theory, and classifications that depend on dimension and topology.

  • 5 Structure of QCAs: In one dimension, the index theory classifies when two QCAs can be smoothly deformed into one another while preserving locality.This provides a structural invariant for comparing one-dimensional QCA dynamics.
  • 5 Structure of QCAs: In two dimensions, all qudit QCAs can be classified using indices and the topology of the underlying space.The review presents this as a higher-dimensional structural classification.

5.1 Unitarity plus causality implies localizability

A locality-preserving unitary QCA can be converted into a finite-depth circuit after doubling the system and inserting local swaps. The construction also extends to settings with time-dependent neighbourhoods.

  • 5.1 Unitarity plus causality implies localizability: The proof duplicates the system, applies a global swap, and decomposes the joint dynamics using swaps conjugated by the QCA unitary.The duplicated system has matching qudits at corresponding lattice sites.
  • 5.1 Unitarity plus causality implies localizability: Conjugating a local swap by a locality-preserving unitary produces a unitary localized on the inverse neighbourhood.Locality of the inverse follows because the inverse unitary is also locality preserving.
  • 5.1 Unitarity plus causality implies localizability: The joint dynamics is implementable as a finite-depth circuit because swaps and non-overlapping conjugated swaps can be applied in parallel.The minimum depth is max_n |N_B(n)|+1.
  • 5.1 Unitarity plus causality implies localizability: The localizability result was later generalized to dynamical graphs whose QCA neighbourhood schemes change over time.This extension was motivated by discrete models of quantum gravity with time-dependent spatial geometry.

5.2 Index theory in one dimension

The one-dimensional index quantifies net quantum-information flow using local algebraic data and classifies QCAs up to finite-depth circuits and continuous deformation. For qudit QCAs it is a positive rational, with shifts and local circuits providing distinct index values.

  • Index construction: The index quantifies how much quantum information moves along a one-dimensional line and can be computed from local dynamics.The construction uses support algebras and even and odd algebras to track information moving left and right.
  • Index construction: Regrouping sites into larger cells makes the QCA nearest-neighbour without changing the index.For example, neighboring cell algebras can be grouped as B_n = A_2n ⊗ A_2n+1.
  • Index properties: For qudit QCAs, the index is a positive rational and is independent of the position used in its definition.The equivalent formulas follow from the dimensions of the relevant matrix algebras and the index is independent of regrouping.
  • Examples: A right shift of d-dimensional qudits has index d, a left shift has index 1/d, and every finite-depth circuit has index 1.These examples distinguish transport implemented by shifts from locally implementable dynamics.
  • Index properties: The index is multiplicative under composition and tensor products, and index 1 holds exactly for locally implementable QCAs.It is a group homomorphism into the strictly positive rationals.
  • Index properties: QCAs with the same cell structure have the same index exactly when they can be continuously deformed into one another, making the index robust to local unitaries and smooth deformations.This robustness supports its use in classifying chiral Floquet phases.
  • Fermionic extension: The fermionic extension requires semisimple support algebras with trivial graded center rather than the simple matrix-algebra structure used for qudits.A generalized Artin-Wedderburn theorem supplies the needed algebraic structure.
  • Fermionic extension: Fermionic QCAs extend the qudit index by allowing factors of square root of two, while qudit indices remain positive rational.Purely fermionic systems have indices 2^n/2, whereas hybrid systems can realize the values in the fermionic formula.

5.3 Index theory in higher dimensions

Higher-dimensional QCA classification combines one-dimensional indices obtained by dimensional reduction with the topology of the underlying spatial manifold. In two dimensions, the classification is complete for finite qudit lattices but is not expected to remain complete in higher dimensions.

  • 5.3 Index theory in higher dimensions: The two-dimensional qudit classification is complete on finite lattices and depends on the topology of the control space.The review does not expect this completeness to extend to higher-dimensional lattices.
  • Equivalence: Stable path equivalence permits local ancillas and continuous QCA paths while keeping the range bounded.It generalizes equivalence up to finite-depth circuits by allowing ancillas at each site.
  • Dimensional reduction: Dimensional reduction regroups all sites along one lattice direction into cells, producing a lower-dimensional QCA with larger cell Hilbert spaces.The resulting classification uses indices from reductions along different directions.
  • Topology: The higher-dimensional classification depends on one-dimensional indices together with the first homology group and torsion of the spatial manifold.These topological data capture noncontractible loops and orientation-related identifications.
  • Shift loops: On a torus, shift loops with the same index along the same direction can be related by finite-depth local circuits.A pair of opposite shifts can be represented by a depth-two circuit of swaps, enabling the contraction argument.
  • Topology: The same loop-contraction idea applies in the plane, but which loops are equivalent depends on the holes in the manifold.The topology therefore controls the equivalence of shift loops.

5.4 Group theory of QCAs

The group-theoretic structure of QCAs is organized by composition, coherent families, and equivalence modulo finite-depth circuits. In particular, the quotient group is abelian, while coherence imposes meaningful relations across changing system sizes.

  • Group structure: QCA composition forms a group, and the one-dimensional index is a homomorphism into the positive rationals for qudit systems.On infinite systems, composing finite-range QCAs yields another finite-range QCA.
  • Group structure: For finite systems, control-space families provide one way to define products while preserving the relevant finite-system structure.The finite-system case is more subtle than the infinite-system case because range constraints must be handled across families.
  • Coherent families: Coherent families require successive QCAs to be stably path equivalent with controlled range, linking dynamics across system refinements.A circle example relates successive shifts by adding ancillas and applying a finite-depth swap circuit.
  • Coherent families: Coherence excludes unrelated choices across family members, although it is not known whether every seemingly natural family is coherent.For toroidal control spaces, translationally invariant Clifford QCAs and translationally invariant three-dimensional QCAs define coherent families, possibly along an infinite subsequence.
  • Coherent families: Coherent families of states can likewise be defined, and these are entanglement renormalization group fixed points.
  • Quotient group: Modulo finite-depth quantum circuits, the group of QCAs is abelian in arbitrary dimensions, with ancillas removable for most reasonable control spaces.The general result may require appending ancillas, while stronger results remove that requirement in many cases.

5.5 Margolus partitioning

Generalized Margolus partitioning constructs one-dimensional QCAs from local unitary maps between subsystems, extending beyond constant-depth circuits. Every one-dimensional qudit QCA admits this form, although higher-dimensional universality fails.

  • 5.5 Margolus partitioning: Margolus partitioning uses local unitary maps between subsystems rather than unitaries acting directly on subsystems.This distinguishes the construction from local finite-depth circuit QCAs.
  • 5.5 Margolus partitioning: The construction groups neighboring sites into two-site supercells and introduces subalgebras B_n within the corresponding local algebras.For higher dimensions, the supercell becomes a larger cube.
  • 5.5 Margolus partitioning: The QCA is assembled by alternating unitary maps W_m and V_m associated with the introduced subalgebras.The maps connect subsystem spaces to ancillary systems and back to QCA subsystems.
  • 5.5 Margolus partitioning: Unlike constant-depth circuits, this partitioning scheme can represent QCAs such as the shift that are not expressible as local unitary circuits.The distinction is between unitaries on systems and more general unitary maps.
  • 5.5 Margolus partitioning: Every one-dimensional QCA with d-dimensional qudits has a Margolus-partitioned representation, but the corresponding higher-dimensional claim is disproved by a two-dimensional counterexample.Higher-dimensional QCAs can still be constructed using Margolus partitioning.

5.6 Tensor-network unitaries

Tensor-network methods represent QCAs through matrix product unitaries and related tensor-network unitaries. These representations connect locality preservation, indices, symmetries, fermionic extensions, and area-law entanglement.

  • 5.6 Tensor-network unitaries: Translationally invariant one-dimensional qudit QCAs are equivalent to matrix product unitaries, while non-translationally invariant MPUs need not be locality preserving.The converse holds for finite-bond-dimension MPUs in the translationally invariant setting.
  • 5.6 Tensor-network unitaries: A matrix product unitary contracts physical and bond indices across a chain, with bond dimension D controlling the auxiliary index range.The shift QCA has bond dimension equal to the qudit dimension.
  • 5.6 Tensor-network unitaries: Local QCA unitary maps can be decomposed into tensor products of maps on neighboring qudits, yielding the tensors used in the matrix product unitary representation.The input and output spaces may have different local dimensions while preserving the total dimension.
  • 5.6 Tensor-network unitaries: The matrix product unitary formulation provides a different derivation of the QCA index, and finite-bond-dimension MPUs are equivalent to QCAs when translational invariance is imposed.Without translational invariance, a generalized CNOT controlled from one site is not locality preserving.
  • 5.6 Tensor-network unitaries: One-dimensional MPUs with on-site unitary symmetries are classified by the QCA index and the cohomology class of the symmetry representation on bond indices.The classification permits adding ancillas transforming under arbitrary symmetry-group representations.
  • 5.6 Tensor-network unitaries: Fermionic QCAs require ancillary degrees of freedom in the fermionic matrix product-state framework to capture all cases, including the Majorana shift.This extension also re-derives the fermionic QCA index.
  • 5.6 Tensor-network unitaries: In any spatial dimension, qudit QCAs admit tensor-network-unitary representations with system-size-independent bond dimension when the tensors satisfy simplicity.This equivalence implies an area law for entanglement created by QCAs.

6 QCAs in physics

QCAs provide strictly locality-preserving discrete dynamics for Floquet systems, topological phases, and quantum field theories. Their applications include robust boundary-index classifications, higher-dimensional disentangling results, and continuum limits yielding relativistic and interacting field theories.

  • 6.1 QCAs vs Hamiltonian dynamics: Continuous-time local Hamiltonian dynamics lacks a strict propagation-speed bound, whereas discrete-time QCAs can enforce strict locality preservation.This motivates QCAs as discrete models of physics despite their distinct dynamical structure.
  • 6.2 Dynamical topological phases in Floquet systems: Lieb-Robinson bounds make QCA approximations effective models of periodically driven systems, enabling QCA techniques to analyze Floquet dynamics.The approximation improves when the QCA neighborhood covers the one-period Lieb-Robinson cone.
  • 6.2 Dynamical topological phases in Floquet systems: A four-swap two-dimensional QCA is trivial in the bulk but becomes a boundary shift, whose index classifies chiral propagation and topological phase.Layering opposite evolutions realizes boundary indices d1/d2 while retaining a trivial bulk.
  • 6.3 Understanding phases of matter: In three-dimensional Walker-Wang models, QCA disentanglers map locally flippable ground states to trivial separators, while the associated Clifford QCA is supported as nontrivial.The nontriviality is connected to the believed impossibility of realizing the same topological order with a two-dimensional commuting-projector Hamiltonian.
  • 6.5 Quantum field theory: Quantum walks defined by QCAs converge to relativistic equations such as the Weyl and Dirac equations in suitable continuum limits.Interacting extensions add on-site phases for double occupancy, producing the Thirring QCA.
  • 6.5 Quantum field theory: QCA discretizations preserve strict causality but break Lorentz symmetry, and their physical vacuum must reproduce continuum vacuum entanglement rather than the naive product state.Existing quantum-field-theory simulation proposals also identify initial-state preparation as a difficult part of the problem.

7 Outlook and open problems

The review closes by identifying open problems spanning QCA computation, classification, locality, irreversibility, algebraic structure, symmetries, invariant states, and continuum limits.

  • Quantum computation: A comprehensive theory of quantum computation using QCAs, including error correction and the role of global operations, remains open.The review questions when QCA computation is preferable to circuit or measurement-based models and whether a complete framework exists.
  • Classification: Fully classifying QCAs in dimensions greater than two remains open, including identifying additional invariants and clarifying equivalence notions.The two-dimensional classification by index and control-space topology motivates questions about higher-dimensional invariants and ancilla conventions.
  • Locality and irreversibility: It remains unknown which structural results survive when strictly locality-preserving dynamics are replaced by approximately locality-preserving dynamics with decaying tails.This question is directly relevant to QCA models of Floquet topological phases.
  • Locality and irreversibility: Irreversible QCAs lack a physically motivated axiomatization that also supports useful structure theorems.Constructive examples exist through finite-depth circuits of local completely positive trace-preserving maps, but broader foundations remain unresolved.
  • Algebraic structure: Higher-dimensional boundary algebras of QCAs produce nontrivial decompositions of quasi-local algebras, suggesting deeper connections with infinite-lattice operator structure.The review presents quasi-local algebra structure as an open direction beyond the established use of boundary algebras for the one-dimensional index.
  • Further directions: Open questions also concern symmetry-protected classifications, invariant low-entanglement states, and continuum limits beyond currently integrable models.The review specifically asks about tenfold-way symmetries, systematic invariant-state constructions, and analogues of critical phenomena for QCA continuum limits.

A Infinite systems and quasi-local algebras

The appendix formulates infinite quantum lattice systems through quasi-local C*-algebras, states, representations, and automorphisms, while highlighting distinctions that arise in infinite dimensions.

  • C*-algebra basics: A C*-algebra is a complete normed complex algebra equipped with an involution satisfying the stated algebraic properties.The appendix uses this structure as the foundation for infinite spin-lattice systems.
  • Quasi-local algebras: A quantum lattice system assigns finite-dimensional C*-algebras to lattice sites and tensor-product algebras to finite regions.The full lattice algebra is obtained by completing local elements in norm.
  • Quasi-local algebras: The quasi-local algebra contains finite-support local elements and norm limits of such elements, called quasi-local elements.This completion is essential for describing the entire infinite lattice rather than only finite regions.
  • States: A state is a positive, normalized linear functional, and finite-dimensional states recover the density-matrix expression ρ(A) = tr[ρA].For infinite systems, compatible density operators on finite regions provide an equivalent description of states.
  • Representations: The GNS construction turns any state into a cyclic representation, unique up to unitary equivalence.The construction uses the state to define an inner product and a Hilbert space representation.
  • Automorphisms: Automorphisms can be implemented by unitaries in a state’s cyclic representation, but some infinite-system automorphisms are not unitarily implementable there.Applying Pauli X at every site provides an example whose global spin flip lies outside the representation’s Hilbert space.

B QCAs with fermions

Fermionic QCAs replace site qudits with fermionic modes and require graded algebraic structures to encode anticommutation, parity, and locality.

  • Fermionic systems: Fermionic QCAs assign fermionic modes to lattice sites, with creation and annihilation operators obeying fermionic algebraic relations.Hybrid QCAs may combine qudits and fermion modes at each site.
  • Fermionic systems: Each fermionic mode can contain at most one fermion because the squared creation operator vanishes.The occupation-number eigenvalues are 0 and 1.
  • Infinite fermionic systems: Infinite fermion systems are constructed from regional fermionic algebras, whose operators anticommute across different regions or modes.Apart from this anticommutation difference, the quasi-local algebra construction parallels the qudit case.
  • Grading: Graded algebras divide operators into even and odd sectors, corresponding to parity-preserving and parity-changing behavior.The fermion algebra is naturally graded, with number-preserving examples even and annihilation operators odd.
  • Grading: The graded commutator and graded tensor product encode the modified commutation rules required for fermionic systems.Algebras graded-commute when their graded commutator vanishes for every pair of elements.
Loading 1904.13318v2…