Student or educator? Sign up with your school email and get 6 months of Pro free.
CoChat

The DOI matches its Crossref record; 167 of the 168 references it cites were found in a registry or an index, and 1 are not checked yet.

A review of Quantum Cellular Automata

Open access
Farrelly, Terry · 2020 · Quantum

Abstract

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.

Overview

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.22331/q-2020-11-30-368

Cites

167 of 168 references verified0 citation errors · 0 not checkable

Statistics

Figures

Figure 1 An example of a CA evolution for the rule 110 CA, with time going up. Bits with value 1 are represented by the blue squares, while 0 is represented by white squares.
Figure 1 An example of a CA evolution for the rule 110 CA, with time going up. Bits with value 1 are represented by the blue squares, while 0 is represented by white squares.CC-BY · From the PDF
Figure 2 A simple example of a QCA unitary. Qubits are represented by the yellow boxes, while the two-qubit local unitaries that implement the dynamics over one timestep are represented by the red and blue rectangles.
Figure 2 A simple example of a QCA unitary. Qubits are represented by the yellow boxes, while the two-qubit local unitaries that implement the dynamics over one timestep are represented by the red and blue rectangles.CC-BY · From the PDF
Figure 3 A simple but important example of a QCA is a shift along the line.
Figure 3 A simple but important example of a QCA is a shift along the line.CC-BY · From the PDF
Figure 4 A unitary or automorphism is locality preserving if it maps local operators to local operators (in the Heisenberg picture). At t = 0 an operator A is localized on four sites, but after one timestep the updated operator u ( A ) is localized on nine sites nearby.
Figure 4 A unitary or automorphism is locality preserving if it maps local operators to local operators (in the Heisenberg picture). At t = 0 an operator A is localized on four sites, but after one timestep the updated operator u ( A ) is localized on nine sites nearby.CC-BY · From the PDF
Figure 5 To define QCA dynamics it is often useful to partition the lattice into supercells by grouping sites together. (The supercells can have any shape as long as they are finite.) Then we apply unitaries to each system in the supercells. More generally we consider several different partitions and apply different unitaries to supercells in each partition in sequence to implement the QCA dynamics.
Figure 5 To define QCA dynamics it is often useful to partition the lattice into supercells by grouping sites together. (The supercells can have any shape as long as they are finite.) Then we apply unitaries to each system in the supercells. More generally we consider several different partitions and apply different unitaries to supercells in each partition in sequence to implement the QCA dynamics.CC-BY · From the PDF
Figure 6 A Watrous QCA shifts some subsystems left and some right while some remain stationary each timestep. On-site unitaries also get applied before or after the shift step. Each site has three qudits, represented by yellow boxes: B l n , B c n and B r n .
Figure 6 A Watrous QCA shifts some subsystems left and some right while some remain stationary each timestep. On-site unitaries also get applied before or after the shift step. Each site has three qudits, represented by yellow boxes: B l n , B c n and B r n .CC-BY · From the PDF
Figure 7 An example of Clifford QCA dynamics with update rule fully specified by X n → X n -1 ⊗ Y n ⊗ X n +1 and Z n → X n . Each square represents an element in a Pauli string: white represents ✶ , X is yellow, Y is blue and Z is green. Notice the fractal structure in the spacetime diagram (where time goes up).
Figure 7 An example of Clifford QCA dynamics with update rule fully specified by X n → X n -1 ⊗ Y n ⊗ X n +1 and Z n → X n . Each square represents an element in a Pauli string: white represents ✶ , X is yellow, Y is blue and Z is green. Notice the fractal structure in the spacetime diagram (where time goes up).CC-BY · From the PDF
Figure 8 The two different partitions used to define the QCA are 2 × 2 squares as shown in subfigure (a). The first is given by the squares with solid red lines (with upper left site having both coordinates even, e.g., (0 , 0) ), and the second corresponds to the green boxes with dotted lines (with upper left site having both coordinates odd). Subfigure (b) shows the simpler labelling of qubits in one of the supercells used to define the unitary in equation (20).
Figure 8 The two different partitions used to define the QCA are 2 × 2 squares as shown in subfigure (a). The first is given by the squares with solid red lines (with upper left site having both coordinates even, e.g., (0 , 0) ), and the second corresponds to the green boxes with dotted lines (with upper left site having both coordinates odd). Subfigure (b) shows the simpler labelling of qubits in one of the supercells used to define the unitary in equation (20).CC-BY · From the PDF
Figure 9 Visualization of even and odd algebras. Note that, e.g., R 2 n rarely equals A 2 n -1 ⊗A 2 n .
Figure 9 Visualization of even and odd algebras. Note that, e.g., R 2 n rarely equals A 2 n -1 ⊗A 2 n .CC-BY · From the PDF
Image 10
CC-BY · From the PDF
Figure 11 Subfigure (a) shows how two shifts in opposite directions (black arrows) are equivalent to a depth-two local circuit of swaps (red arrows). Subfigure (b) depicts dynamics involving many shifts in opposite directions. This is also equivalent to a depth-two local circuit, as long as there is a shift to the left for every shift to the right.
Figure 11 Subfigure (a) shows how two shifts in opposite directions (black arrows) are equivalent to a depth-two local circuit of swaps (red arrows). Subfigure (b) depicts dynamics involving many shifts in opposite directions. This is also equivalent to a depth-two local circuit, as long as there is a shift to the left for every shift to the right.CC-BY · From the PDF
Image 12
CC-BY · From the PDF
Image 13
CC-BY · From the PDF
Figure 14 In subfigure (a) we see the decomposition of the unitary map V n into a sum over γ of tensor products of maps ˜ X γ 2 m +1 ⊗ ˜ Y γ 2 m +2 . The thicker and thinner input and output lines highlight that the dimensions of the local vector spaces may be different. Subfigure (b) shows how the tensor building the matrix product unitary representation of the QCA unitary is put together. Note that the input and output indices act on two neighbouring qudits of the QCA.
Figure 14 In subfigure (a) we see the decomposition of the unitary map V n into a sum over γ of tensor products of maps ˜ X γ 2 m +1 ⊗ ˜ Y γ 2 m +2 . The thicker and thinner input and output lines highlight that the dimensions of the local vector spaces may be different. Subfigure (b) shows how the tensor building the matrix product unitary representation of the QCA unitary is put together. Note that the input and output indices act on two neighbouring qudits of the QCA.CC-BY · From the PDF
Figure 15 Subfigure (a) shows the Floquet dynamics on the infinite plane. The green swaps are applied first, orange are second, purple third and blue swaps are applied last. By following the path of a qudit, we see that the dynamics after all four swaps is the identity. In subfigure (b) however, a boundary has been introduced, and we can see that some of the qudits at the boundary have nontrivial dynamics.
Figure 15 Subfigure (a) shows the Floquet dynamics on the infinite plane. The green swaps are applied first, orange are second, purple third and blue swaps are applied last. By following the path of a qudit, we see that the dynamics after all four swaps is the identity. In subfigure (b) however, a boundary has been introduced, and we can see that some of the qudits at the boundary have nontrivial dynamics.CC-BY · From the PDF

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

Show all 158 references

Research works printed but not linked: 19

  1. J. von Neumann. Theory of Self-Reproducing Automata. University of Illinois Press, Champaign, Illinois, 1966.
  2. B. Schumacher and R. F. Werner. Reversible Quantum Cellular Automata. arXiv:quant-ph/0405174, 2004. · arXiv
  3. J. Haah, L. Fidkowski, and M. B. Hastings. Nontrivial Quantum Cellular Automata in Higher Dimensions. arXiv:1812.01625, 2018. · arXiv
  4. B. Aoun and M. Tarifi. Introduction to Quantum Cellular Automata. arXiv:quant-ph/0401123, 2004. · arXiv
  5. J. Horowitz. An introduction to quantum cellular automata, 2008. https://www.semanticscholar.org/paper/An-Introduction-to-Quantum-Cellular-Automata-Horowitz/ef054a8924386b885628eb5402d2998093871381.
  6. W. van Dam. Quantum cellular automata. Master's thesis, University of Nijmegen, 1996.
  7. P. Arrighi. Quantum cellular automata. Habilitation thesis, Université de Grenoble, 2009.
  8. J. Gütschow. Quantum information processing with Clifford quantum cellular automata. PhD thesis, Leibniz Universität Hannover, 2012.
  9. C. A. Pérez-Delgado and D. Cheung. Models of Quantum Cellular Automata. arXiv:quant-ph/0508164, 2005. · arXiv
  10. C. A. Pérez-Delgado and D. Cheung. Local unitary quantum cellular automata. Phys. Rev. A, 76: 032320, 2007. https://doi.org/10.1103/PhysRevA.76.032320. · DOI
  11. N. Margolus. Parallel quantum computation. In W. H. Zurek, editor, Complexity, Entropy, and the Physics of Information, page 273, Redwood City, CA, 1991. Addison Wesley.
  12. P. Arrighi and V. Nesme. Quantization of cellular automata. JAC 2008, pages 204–215, 2008.
  13. A. Shakeel. Quantum Cellular Automata: Schrödinger and Heisenberg Pictures. arXiv:1807.01192v1, 2018. · arXiv
  14. J. Haah. Clifford quantum cellular automata: Trivial group in 2d and Witt group in 3d. arXiv:1907.02075, 2019. · arXiv
  15. M. Freedman, J. Haah, and M. B. Hastings. The group structure of quantum cellular automata. arXiv:1910.07998, 2019. · arXiv
  16. A. H. Werner H. Wilming. Finite group velocity implies locality of interactions. arXiv:2006.10062, 2020. · arXiv
  17. Z. Zimborás, T. Farrelly, S. Farkas, and L. Masanes. Does causal dynamics imply local interactions? arXiv:2006.10707, 2020. · arXiv
  18. M. Creutz. Quarks, Gluons and Lattices. Cambridge Monographs on Mathematical Physics. Cambridge University Press, 1983.
  19. M. McGuigan. Quantum Cellular Automata from Lattice Field Theories. arXiv:quant-ph/0307176, 2003. · arXiv

Cited by

See all 196

Metadata

Authors
Farrelly, T.
Affiliations
Leibniz University Hannover (DE)
Corresponding author
Farrelly, Terry
Venue
Quantum
Published
2020-11-30
Volume
4
Pages
368
ISSN
2521-327X (ISSN-L)
OpenAlex
W2943005320
Cited by
138
References
158
Citations by year
2026: 21 · 2025: 32 · 2024: 20 · 2023: 21 · 2022: 25 · 2021: 15 · 2020: 2
FWCI
6.41
Type
journal article
Language
en
Open access
Locations
  • Quantum (publishedVersion, cc-by)
  • arXiv (Cornell University) (submittedVersion)
  • DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion, cc-by-sa)
  • arXiv (Cornell University)
Funders
Australian Research Council (CE170100009, EQUS CE170100009)
Topics
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Cellular Automata and Applications
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
Keywords
quantum cellular automata, quantum computing, topological phases, periodically driven systems, periodically driven quantum systems, interacting quantum field theory, index theory

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

How to cite

Cite CoChat for the checks on this page, and the paper for its own findings.

This page
CoChat. (2026). Citation check: A review of Quantum Cellular Automata. https://app.cochat.ai/papers/10.22331/q-2020-11-30-368
The paper
Farrelly, T. (2020). A review of Quantum Cellular Automata. Quantum. https://doi.org/10.22331/q-2020-11-30-368

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.