Renormalisation of Quantum Cellular Automata

Lorenzo Siro Trezzini; Alessandro Bisio; Paolo Perinotti

doi:10.22331/q-2025-05-28-1756

Renormalisation of Quantum Cellular Automata

Lorenzo Siro Trezzini, Alessandro Bisio, and Paolo Perinotti

Dipartimento di Fisica dell'Università di Pavia, via Bassi 6, 27100 Pavia
Istituto Nazionale di Fisica Nucleare, Gruppo IV, via Bassi 6, 27100 Pavia

Published:	2025-05-28, volume 9, page 1756
Editor:	Felix Huber
Eprint:	arXiv:2407.12652v2
Doi:	https://doi.org/10.22331/q-2025-05-28-1756
Citation:	Quantum 9, 1756 (2025).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

We study a coarse-graining procedure for quantum cellular automata on hypercubic lattices that consists in grouping neighboring cells into tiles and selecting a subspace within each tile. This is done in such a way that multiple evolution steps applied to this subspace can be viewed as a single evolution step of a new quantum cellular automaton, whose cells are the subspaces themselves. We derive a necessary and sufficient condition for renormalizability and use it to investigate the renormalization flow of cellular automata on a line, where the cells are qubits and the tiles are composed of two neighboring cells. The problem is exhaustively solved, and the fixed points of the renormalization flow are highlighted.

Popular summary

Quantum Cellular Automata (QCA) are discrete time evolutions of discrete lattices of quantum systems, and they recently attracted increasing interest both as “analog quantum computers'', with a natural application in quantum simulations, and as a possible microscopic model for relativistic quantum field theories. However, very little is known about their general structure, and many theoretical developments are yet to be accomplished. One of the most intriguing facets of QCAs is that their intrinsically discrete nature brings about fundamental questions about fundamental physical concepts such as energy and other related quantities in thermodynamics—temperature, thermodynamical potentials and so on.

In this study we pave the way to one of the crucial aspects of the statistical mechanics of QCAs: their renormalisation group. Renormalisation is, roughly speaking, a technique to erase microscopic details that become irrelevant to the dynamics of a system on larger scales, and renormalisable systems behave in a similar way at very large scales, except from a redefinition of their fundamental dynamical constants. The displacement of the values in the space of constants under a rescaling is known as “renormalisation flow'', and its fixed points are particularly important because they represent stable and reliable descriptions of the dynamics on a coarse-grained scale. Models of physical interest tend to gather in classes defined by the fact that their fixed points have universal properties, thus identifying very common features, transversal among apparently very different models. This is, incidentally, the reason why overly simplified theoretical models often lead to astonishingly reliable predictions. In this work, we formulate the problem of studying the renormalisation flow of quantum cellular automata, and provide easily checkable conditions for renormalisability. We then specialise the analysis to QCAs whose cells are qubits, and answer the general question as to what QCAs are renormalisable. We provide the full renormalisation flow for this case, and determine its fixed points.

► BibTeX data

@article{Trezzini2025renormalisationof,
  doi = {10.22331/q-2025-05-28-1756},
  url = {https://doi.org/10.22331/q-2025-05-28-1756},
  title = {Renormalisation of {Q}uantum {C}ellular {A}utomata},
  author = {Trezzini, Lorenzo Siro and Bisio, Alessandro and Perinotti, Paolo},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {9},
  pages = {1756},
  month = may,
  year = {2025}
}

► References

[1] Richard P. Feynman. ``Simulating physics with computers''. International Journal of Theoretical Physics 21, 467–488 (1982).
https://doi.org/10.1007/BF02650179

[2] John Von Neumann and Arthur W. Burks. ``Theory of self-reproducing automata''. University of Illinois Press. USA, (1966).

[3] K.P. Hadeler and J. Müller. ``Cellular automata: Analysis and applications''. Springer Monographs in Mathematics. Springer International Publishing. (2017). url: https://books.google.it/books?id=L4olDwAAQBAJ.
https://books.google.it/books?id=L4olDwAAQBAJ

[4] Gerhard Grössing and Anton Zeilinger. ``Quantum cellular automata''. Complex Syst. 2, 197–208, (1988).

[5] J. Watrous. ``On one-dimensional quantum cellular automata''. In Proceedings of IEEE 36th Annual Foundations of Computer Science. Pages 528–537. (1995).
https://doi.org/10.1109/SFCS.1995.492583

[6] Christoph Dürr, Huong Lê Thanh, and Miklos Santha. ``A decision procedure for well-formed linear quantum cellular automata''. In Claude Puech and Rüdiger Reischuk, editors, STACS 96. Pages 281–292. Berlin, Heidelberg (1996).
https://doi.org/10.48550/arXiv.cs/9906024

[7] Christoph Dürr and Miklos Santha. ``A decision procedure for unitary linear quantum cellular automata''. SIAM Journal on Computing 31, 1076–1089 (2002).
https://doi.org/10.1137/S0097539797327702

[8] Jozef Gruska. ``Quantum computing''. Pages 2297–2310. John Wiley & Sons, Ltd. (2009).
https://doi.org/10.1002/9780470050118.ecse720

[9] B. Schumacher and R. F. Werner. ``Reversible quantum cellular automata''. quant-ph/0405174 (2004).
https://doi.org/10.48550/arXiv.quant-ph/0405174
arXiv:quant-ph/0405174

[10] Pablo Arrighi, Vincent Nesme, and Reinhard Werner. ``One-dimensional quantum cellular automata over finite, unbounded configurations''. In Carlos Martín-Vide, Friedrich Otto, and Henning Fernau, editors, Language and Automata Theory and Applications. Pages 64–75. Berlin, Heidelberg (2008).
https://doi.org/10.1007/978-3-540-88282-4_8

[11] D. J. Shepherd, T. Franz, and R. F. Werner. ``Universally programmable quantum cellular automaton''. Phys. Rev. Lett. 97, 020502 (2006).
https://doi.org/10.1103/PhysRevLett.97.020502

[12] Pablo Arrighi, Renan Fargetton, and Zizhu Wang. ``Intrinsically universal one-dimensional quantum cellular automata in two flavours''. Fundamenta Informaticae 91, 197–230 (2009).
https://doi.org/10.3233/FI-2009-0041

[13] Giacomo Mauro D'Ariano and Paolo Perinotti. ``Derivation of the dirac equation from principles of information processing''. Phys. Rev. A 90, 062106 (2014).
https://doi.org/10.1103/PhysRevA.90.062106

[14] Alessandro Bisio, Giacomo Mauro D'Ariano, and Paolo Perinotti. ``Quantum cellular automaton theory of light''. Annals of Physics 368, 177–190.
https://doi.org/10.1016/j.aop.2016.02.009

[15] Arindam Mallick and C. M. Chandrashekar. ``Dirac cellular automaton from split-step quantum walk''. Scientific Reports 6, 25779 (2016).
https://doi.org/10.1038/srep25779

[16] Pablo Arrighi, Cédric Bény, and Terry Farrelly. ``A quantum cellular automaton for one-dimensional qed''. Quantum Information Processing 19, 88 (2020).
https://doi.org/10.1007/s11128-019-2555-4

[17] Alessandro Bisio, Giacomo Mauro D'Ariano, Paolo Perinotti, and Alessandro Tosini. ``Thirring quantum cellular automaton''. Physical Review A 97, 032132.
https://doi.org/10.1103/PhysRevA.97.032132

[18] Alessandro Bisio, Nicola Mosco, and Paolo Perinotti. ``Scattering and perturbation theory for discrete-time dynamics''. Physical Review Letters 126, 250503.
https://doi.org/10.1103/PhysRevLett.126.250503

[19] Nathanaël Eon, Giuseppe Di Molfetta, Giuseppe Magnifico, and Pablo Arrighi. ``A relativistic discrete spacetime formulation of 3+1 QED''. Quantum 7, 1179 (2023).
https://doi.org/10.22331/q-2023-11-08-1179

[20] Lorenzo Piroli and J. Ignacio Cirac. ``Quantum cellular automata, tensor networks, and area laws''. Phys. Rev. Lett. 125, 190402 (2020).
https://doi.org/10.1103/PhysRevLett.125.190402

[21] Alexander Jahn, Zoltán Zimborás, and Jens Eisert. ``Tensor network models of AdS/qCFT''. Quantum 6, 643 (2022).
https://doi.org/10.22331/q-2022-02-03-643

[22] Logan E. Hillberry, Lorenzo Piroli, Eric Vernier, Nicole Yunger Halpern, Tomaž Prosen, and Lincoln D. Carr. ``Integrability of goldilocks quantum cellular automata'' (2024). https://doi.org/10.48550/arXiv.2404.02994.
https://doi.org/10.48550/arXiv.2404.02994

[23] David T Stephen, Hendrik Poulsen Nautrup, Juani Bermejo-Vega, Jens Eisert, and Robert Raussendorf. ``Subsystem symmetries, quantum cellular automata, and computational phases of quantum matter''. Quantum 3, 142.
https://doi.org/10.22331/q-2019-05-20-142

[24] Hoi Chun Po, Lukasz Fidkowski, Takahiro Morimoto, Andrew C Potter, and Ashvin Vishwanath. ``Chiral floquet phases of many-body localized bosons''. Physical Review X 6, 041070.
https://doi.org/10.1103/PhysRevX.6.041070

[25] Lukasz Fidkowski, Hoi Chun Po, Andrew C Potter, and Ashvin Vishwanath. ``Interacting invariants for floquet phases of fermions in two dimensions''. Physical Review B 99, 085115.
https://doi.org/10.1103/PhysRevB.99.085115

[26] Alexei Kitaev and John Preskill. ``Topological entanglement entropy''. Physical review letters 96, 110404.
https://doi.org/10.1103/PhysRevLett.96.110404

[27] Paolo Perinotti. ``Cellular automata in operational probabilistic theories''. Quantum 4, 294 (2020).
https://doi.org/10.22331/q-2020-07-09-294

[28] Jean Zinn-Justin. ``Phase Transitions and Renormalization Group''. Oxford University Press. (2007).
https://doi.org/10.1093/acprof:oso/9780199227198.001.0001

[29] Leo P. Kadanoff. ``Scaling laws for ising models near ${T}_{c}$''. Physics Physique Fizika 2, 263–272 (1966).
https://doi.org/10.1103/PhysicsPhysiqueFizika.2.263

[30] Kenneth G. Wilson. ``Renormalization group and critical phenomena. i. renormalization group and the kadanoff scaling picture''. Phys. Rev. B 4, 3174–3183 (1971).
https://doi.org/10.1103/PhysRevB.4.3174

[31] Kenneth G. Wilson. ``Renormalization group and critical phenomena. ii. phase-space cell analysis of critical behavior''. Phys. Rev. B 4, 3184–3205 (1971).
https://doi.org/10.1103/PhysRevB.4.3184

[32] Navot Israeli and Nigel Goldenfeld. ``Computational irreducibility and the predictability of complex physical systems''. Phys. Rev. Lett. 92, 074105 (2004).
https://doi.org/10.1103/PhysRevLett.92.074105

[33] Navot Israeli and Nigel Goldenfeld. ``Coarse-graining of cellular automata, emergence, and the predictability of complex systems''. Phys. Rev. E 73, 026203 (2006).
https://doi.org/10.1103/PhysRevE.73.026203

[34] O. Duranthon and Giuseppe Di Molfetta. ``Coarse-grained quantum cellular automata''. Physical Review A 103 (2021).
https://doi.org/10.1103/physreva.103.032224

[35] Stefan Boettcher, Stefan Falkner, and Renato Portugal. ``Renormalization and scaling in quantum walks''. Phys. Rev. A 90, 032324 (2014).
https://doi.org/10.1103/PhysRevA.90.032324

[36] Pierre-Gabriel Rozon, Michael J. Gullans, and Kartiek Agarwal. ``Constructing quantum many-body scar hamiltonians from floquet automata''. Phys. Rev. B 106, 184304 (2022).
https://doi.org/10.1103/PhysRevB.106.184304

[37] John Preskill. ``Quantum Computing in the NISQ era and beyond''. Quantum 2, 79 (2018).
https://doi.org/10.22331/q-2018-08-06-79

[38] T. L. M. Guedes, D. Winter, and M. Müller. ``Quantum cellular automata for quantum error correction and density classification''. Phys. Rev. Lett. 133, 150601 (2024).
https://doi.org/10.1103/PhysRevLett.133.150601

[39] Wim van Dam. ``Quantum cellular automata''. Master's Thesis, Computer Science Institute, University of Nijmegen, The Netherlands, (1996).

[40] Mauro Faccin, Michael T Schaub, and Jean-Charles Delvenne. ``Entrograms and coarse graining of dynamics on complex networks''. Journal of Complex Networks 6, 661–678 (2017).
https://doi.org/10.1093/comnet/cnx055

[41] D. Gross, V. Nesme, H. Vogts, and R. F. Werner. ``Index theory of one dimensional quantum walks and cellular automata''. Communications in Mathematical Physics 310, 419–454 (2012).
https://doi.org/10.1007/s00220-012-1423-1

[42] Pablo Arrighi, S. Martiel, and V. Nesme. ``Cellular automata over generalized Cayley graphs''. Mathematical Structures in Computer Science 18, 340–383 (2018). url: https://hal.science/hal-01785458.
https://hal.science/hal-01785458

[43] Giacomo Mauro D'Ariano and Paolo Perinotti. ``Quantum cellular automata and free quantum field theory''. Frontiers of Physics 12, 120301 (2016).
https://doi.org/10.1007/s11467-016-0616-z

[44] O. Bratteli and D.W. Robinson. ``Operator algebras and quantum statistical mechanics 1: C*- and w*-algebras. symmetry groups. decomposition of states''. Operator Algebras and Quantum Statistical Mechanics. Springer. (1987). url: https://books.google.it/books?id=YuR4VQOQQUIC.
https://books.google.it/books?id=YuR4VQOQQUIC

[45] R. Haag. ``Local quantum physics: Fields, particles, algebras''. R.Balian, W.Beiglbock, H.Grosse. Springer-Verlag. (1992). url: https://books.google.it/books?id=Op_vAAAAMAAJ.
https://books.google.it/books?id=Op_vAAAAMAAJ

[46] Paolo Zanardi. ``Stabilizing quantum information''. Phys. Rev. A 63, 012301 (2000).
https://doi.org/10.1103/PhysRevA.63.012301

[47] Jean-Luc Brylinski and Ranee Brylinski. ``Universal quantum gates''. In Mathematics of quantum computation. Pages 117–134. Chapman and Hall/CRC (2002).

[48] Alexander Stottmeister, Vincenzo Morinelli, Gerardo Morsella, and Yoh Tanimoto. ``Operator-algebraic renormalization and wavelets''. Phys. Rev. Lett. 127, 230601 (2021).
https://doi.org/10.1103/PhysRevLett.127.230601

[49] Tobias J. Osborne and Alexander Stottmeister. ``Conformal field theory from lattice fermions''. Communications in Mathematical Physics 398, 219–289 (2023).
https://doi.org/10.1007/s00220-022-04521-8

[50] Lauritz van Luijk, Alexander Stottmeister, and Reinhard F. Werner. ``Convergence of dynamics on inductive systems of banach spaces''. Annales Henri Poincaré 25, 4931–4986 (2024).
https://doi.org/10.1007/s00023-024-01413-6

[51] Alexander Stottmeister and Tobias J. Osborne. ``On the renormalization group fixed point of the two-dimensional ising model at criticality''. Scientific Reports 13, 14859 (2023).
https://doi.org/10.1038/s41598-023-42005-4

[52] Pablo Arrighi, Stefano Facchini, and M. Forets. ``Discrete lorentz covariance for quantum walks and quantum cellular automata''. New Journal of Physics 16 (2014). url: https://api.semanticscholar.org/CorpusID:3944811.
https://doi.org/10.1088/1367-2630/16/9/093007
https://api.semanticscholar.org/CorpusID:3944811

[53] Antonio F. Rotundo, Paolo Perinotti, and Alessandro Bisio. ``Effective dynamics from minimising dissipation'' (2024). arXiv:2412.10216.
arXiv:2412.10216

Cited by

[1] Antonio F. Rotundo, Paolo Perinotti, and Alessandro Bisio, "Effective dynamics from minimizing dissipation", Physical Review Research 7 4, 043019 (2025).

[2] Chaitanya Gupta and Anthony J. Short, "Fermion doubling in Dirac quantum walks", Physical Review A 114 1, 012208 (2026).

[3] Andrea Pizzamiglio, Alessandro Bisio, and Paolo Perinotti, "Classification of Qubit Cellular Automata on Hypercubic Lattices", Physical Review Letters 134 24, 240601 (2025).

[4] Alessandro Bisio, Paolo Perinotti, Andrea Pizzamiglio, and Saverio Rota, "A Perturbative Approach to the Solution of the Thirring Quantum Cellular Automaton", Entropy 27 2, 198 (2025).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-12 02:34:01) and SAO/NASA ADS (last updated successfully 2026-08-12 02:34:02). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.