A review of Quantum Cellular Automata

Terry Farrelly

Institut für Theoretische Physik, Leibniz Universität Hannover, 30167 Hannover, Germany
ARC Centre for Engineered Quantum Systems, School of Mathematics and Physics, University of Queensland, Brisbane, QLD 4072, Australia

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


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.

► BibTeX data

► References

[1] J. von Neumann. Theory of Self-Reproducing Automata. University of Illinois Press, Champaign, Illinois, 1966.

[2] A. W. Burks, editor. Essays on Cellular Automata. University of Illinois Press, Champaign, Illinois, 1970.

[3] M. Delorme. An introduction to cellular automata. In J. Mazoyer M. Delorme, editor, Cellular Automata: a Parallel Model, pages 5–49. Springer, Netherlands, 1999. https:/​/​doi.org/​10.1007/​978-94-015-9153-9_1.

[4] E. R. Berlekamp, J. H. Conway, and R. K. Guy. Winning Ways for Your Mathematical Plays, volume 2. Academic Press, London, 1982. https:/​/​doi.org/​10.1201/​9780429487323.

[5] S. Wolfram. Statistical mechanics of cellular automata. Rev. Mod. Phys., 55: 601–644, 1983. https:/​/​doi.org/​10.1103/​RevModPhys.55.601.

[6] M. Cook. Universality in elementary cellular automata. Complex Systems, 15: 1 – 40, 2004.

[7] T. Neary and D. Woods. P-completeness of cellular automaton rule 110. In M. Bugliesi, B. Preneel, V. Sassone, and I. Wegener, editors, Automata, Languages and Programming, pages 132–143, Berlin, Heidelberg, 2006. Springer. https:/​/​doi.org/​10.1007/​11786986_13.

[8] B. Chopard. Cellular Automata Modeling of Physical Systems, pages 407–433. Springer, New York, 2012. https:/​/​doi.org/​10.1007/​978-1-4939-8700-9_57.

[9] S. Succi. The Lattice Boltzmann Equation For Fluid Dynamics and Beyond. Clarendon Press, Oxford, 2001.

[10] D. A. Wolf‐Gladrow. Lattice‐Gas Cellular Automata and Lattice Boltzmann Models: an Introduction, volume 1725 of Lecture Notes in Mathematics. Springer, Berlin, 2000. https:/​/​doi.org/​10.1007/​b72010.

[11] P. Arrighi and J. Grattage. The quantum game of life. Physics World, 25 (06): 23, 2012a. https:/​/​doi.org/​10.1088/​2058-7058/​25/​06/​37.

[12] R. P. Feynman. Simulating physics with computers. International Journal of Theoretical Physics, 21: 467–488, 1982. https:/​/​doi.org/​10.1007/​bf02650179.

[13] A. Trabesinger. Quantum simulation. Nature Physics, 8: 263, 2012. https:/​/​doi.org/​10.1038/​nphys2258.

[14] N. Margolus. Quantum computation. Annals of the New York Academy of Sciences, 480 (1): 487–497, 1986. https:/​/​doi.org/​10.1111/​j.1749-6632.1986.tb12451.x.

[15] S. Lloyd. A potentially realizable quantum computer. Science, 261 (5128): 1569–1571, 1993. https:/​/​doi.org/​10.1126/​science.261.5128.1569.

[16] J. Watrous. On one-dimensional quantum cellular automata. Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science, pages 528–537, 1995. https:/​/​doi.org/​10.1109/​sfcs.1995.492583.

[17] M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, Cambridge, 2000. https:/​/​doi.org/​10.1017/​cbo9780511976667.

[18] G. K. Brennen and J. E. Williams. Entanglement dynamics in one-dimensional quantum cellular automata. Phys. Rev. A, 68: 042311, 2003. https:/​/​doi.org/​10.1103/​PhysRevA.68.042311.

[19] B. Schumacher and R. F. Werner. Reversible Quantum Cellular Automata. arXiv:quant-ph/​0405174, 2004.

[20] P. Arrighi, V. Nesme, and R. F. Werner. Unitarity plus causality implies localizability. Journal of Computer and System Sciences, 77 (2): 372–378, 2011a. https:/​/​doi.org/​10.1016/​j.jcss.2010.05.004.

[21] D. Tong. The unquantum quantum. Scientific American, 307: 46–49, 2012. https:/​/​doi.org/​10.1038/​scientificamerican1212-46.

[22] T. Farrelly and J. Streich. Discretizing quantum field theories for quantum simulation. arXiv:2002.02643, 2020.

[23] K. Wilson. The renormalization group and critical phenomena. In Nobel Lectures, Physics 1981-1990. World Scientific, 1993.

[24] E. H. Lieb and D. W. Robinson. The finite group velocity of quantum spin systems. Communications in Mathematical Physics, 28 (3): 251–257, 1972. https:/​/​doi.org/​10.1007/​bf01645779.

[25] H. C. Po, L. Fidkowski, T. Morimoto, A. C. Potter, and A. Vishwanath. Chiral Floquet phases of many-body localized bosons. Phys. Rev. X, 6: 041070, 2016. https:/​/​doi.org/​10.1103/​PhysRevX.6.041070.

[26] L. Fidkowski, H. C. Po, A. C. Potter, and A. Vishwanath. Interacting invariants for Floquet phases of fermions in two dimensions. Phys. Rev. B, 99: 085115, 2019. https:/​/​doi.org/​10.1103/​PhysRevB.99.085115.

[27] J. Haah, L. Fidkowski, and M. B. Hastings. Nontrivial Quantum Cellular Automata in Higher Dimensions. arXiv:1812.01625, 2018.

[28] B. Aoun and M. Tarifi. Introduction to Quantum Cellular Automata. arXiv:quant-ph/​0401123, 2004.

[29] J. Horowitz. An introduction to quantum cellular automata, 2008. https:/​/​www.semanticscholar.org/​paper/​An-Introduction-to-Quantum-Cellular-Automata-Horowitz/​ef054a8924386b885628eb5402d2998093871381.

[30] K. Wiesner. Quantum cellular automata. In Encyclopedia of Complexity and Systems Science, pages 7154–7164. Springer, 2009. https:/​/​doi.org/​10.1007/​978-3-642-27737-5_426-4.

[31] W. van Dam. Quantum cellular automata. Master's thesis, University of Nijmegen, 1996.

[32] C. A. Pérez Delgado. Quantum Cellular Automata: Theory and Applications. PhD thesis, University of Waterloo, 2007.

[33] H. Vogts. Discrete time quantum lattice systems. PhD thesis, Technische Universität Braunschweig, 2009.

[34] P. Arrighi. Quantum cellular automata. Habilitation thesis, Université de Grenoble, 2009.

[35] J. Gütschow. Quantum information processing with Clifford quantum cellular automata. PhD thesis, Leibniz Universität Hannover, 2012.

[36] P. Arrighi. An overview of quantum cellular automata. Nat Comput, 18: 885–899, 2019. https:/​/​doi.org/​10.1007/​s11047-019-09762-6.

[37] I. Bialynicki-Birula. Weyl, Dirac, and Maxwell equations on a lattice as unitary cellular automata. Phys. Rev. D, 49: 6920–6927, 1994. https:/​/​doi.org/​10.1103/​PhysRevD.49.6920.

[38] F. W. Strauch. Relativistic quantum walks. Phys. Rev. A, 73: 054302, 2006. https:/​/​doi.org/​10.1103/​PhysRevA.73.054302.

[39] C. Cedzich, T. Rybár, A. H. Werner, A. Alberti, M. Genske, and R. F. Werner. Propagation of quantum walks in electric fields. Phys. Rev. Lett., 111: 160601, 2013. https:/​/​doi.org/​10.1103/​PhysRevLett.111.160601.

[40] G. Grössing and A. Zeilinger. Quantum cellular automata. Complex Systems, 2 (2): 197–208, 1988.

[41] D. A. Meyer. On the absence of homogeneous scalar unitary cellular automata. Physics Letters A, 223 (5): 337–340, 1996a. https:/​/​doi.org/​10.1016/​s0375-9601(96)00745-1.

[42] D. A. Meyer. From quantum cellular automata to quantum lattice gases. Journal of Statistical Physics, 85: 551–574, 1996b. https:/​/​doi.org/​10.1007/​bf02199356.

[43] C. S. Lent, P. D. Tougaw, W. Porod, and G. H. Bernstein. Quantum cellular automata. Nanotechnology, 4 (1): 49, 1993. https:/​/​doi.org/​10.1088/​0957-4484/​4/​1/​004.

[44] P. D. Tougaw and C. S. Lent. Logical devices implemented using quantum cellular automata. Journal of Applied Physics, 75 (3): 1818–1825, 1994. https:/​/​doi.org/​10.1063/​1.356375.

[45] G. Tóth and C. S. Lent. Quantum computing with quantum-dot cellular automata. Phys. Rev. A, 63: 052315, 2001. https:/​/​doi.org/​10.1103/​PhysRevA.63.052315.

[46] C. A. Pérez-Delgado and D. Cheung. Models of Quantum Cellular Automata. arXiv:quant-ph/​0508164, 2005.

[47] D. Nagaj and P. Wocjan. Hamiltonian quantum cellular automata in one dimension. Phys. Rev. A, 78: 032311, 2008. https:/​/​doi.org/​10.1103/​PhysRevA.78.032311.

[48] K. G. H. Vollbrecht and J. I. Cirac. Quantum simulators, continuous-time automata, and translationally invariant systems. Phys. Rev. Lett., 100: 010501, 2008. https:/​/​doi.org/​10.1103/​PhysRevLett.100.010501.

[49] G. 't Hooft. The Cellular Automaton Interpretation of Quantum Mechanics. Springer, New York, 2016. https:/​/​www.doi.org/​10.1007/​978-3-319-41285-6.

[50] S. Wolfram. A new kind of science. (Self-published) Wolfram Media Inc., 2002.

[51] S. Aaronson. Limits on Efficient Computation in the Physical World. PhD thesis, University of California, Berkeley, 2004.

[52] S. Richter and R. F. Werner. Ergodicity of quantum cellular automata. Journal of Statistical Physics, 82 (3): 963–998, 1996. https:/​/​doi.org/​10.1007/​BF02179798.

[53] 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.

[54] 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.

[55] P. Arrighi and V. Nesme. Quantization of cellular automata. JAC 2008, pages 204–215, 2008.

[56] P. Arrighi, V. Nesme, and R. F. Werner. Bounds on the speedup in quantum signaling. Phys. Rev. A, 95: 012331, 2017. https:/​/​doi.org/​10.1103/​PhysRevA.95.012331.

[57] T. C. Farrelly. Insights from Quantum Information into Fundamental Physics. PhD thesis, University of Cambridge, 2015. arXiv:1708.08897.

[58] O. Krüger and R. F. Werner. Gaussian quantum cellular automata. In N. Cerf, G. Leuchs, and E. S. Polzik, editors, Quantum Information with Continuous Variables of Atoms and Light. Imperial College Press, London, 2007. https:/​/​doi.org/​10.1142/​9781860948169_0005.

[59] P. Naaijkens. Quantum spin systems on infinite lattices. arXiv:1311.2717, 2013. https:/​/​doi.org/​10.1007/​978-3-319-51458-1.

[60] O. Bratteli and D. Robinson. Operator Algebras and Quantum Statistical Mechanics, volumes 1 and 2. Springer, Berlin, 1997. https:/​/​doi.org/​10.1007/​978-3-662-03444-6.

[61] T. C. Farrelly and A. J. Short. Causal fermions in discrete space-time. Phys. Rev. A, 89: 012302, 2014a. https:/​/​doi.org/​10.1103/​PhysRevA.89.012302.

[62] L. Piroli and J. I. Cirac. Quantum cellular automata, tensor networks, and area laws. arXiv:2007.15371, 2020. https:/​/​doi.org/​10.1103/​PhysRevLett.125.190402.

[63] M. Freedman and M.B. Hastings. Classification of quantum cellular automata. Communications in Mathematical Physics, 376: 1171–1222, 2020. https:/​/​doi.org/​10.1007/​s00220-020-03735-y.

[64] P. Perinotti and L. Poggiali. Scalar fermionic cellular automata on finite Cayley graphs. arXiv:1807.08695, 2018. https:/​/​doi.org/​10.1103/​PhysRevA.98.052337.

[65] P. Arrighi, V. Nesme, and R. F. Werner. One-dimensional quantum cellular automata over finite, unbounded configurations. In Language and Automata Theory and Applications, volume 5196 of Lecture Notes in Computer Science, pages 64–75. Springer, 2008. https:/​/​doi.org/​10.1007/​978-3-540-88282-4_8.

[66] A. Shakeel. Quantum Cellular Automata: Schrödinger and Heisenberg Pictures. arXiv:1807.01192v1, 2018.

[67] S. J. Summers and R. Werner. The vacuum violates Bell's inequalities. Physics Letters A, 110 (5): 257 – 259, 1985. http:/​/​doi.org/​10.1016/​0375-9601(85)90093-3.

[68] A. Shakeel and P. J. Love. When is a quantum cellular automaton (QCA) a quantum lattice gas automaton (QLGA)? Journal of Mathematical Physics, 54 (9): 092203, 2013. https:/​/​doi.org/​10.1063/​1.4821640.

[69] D. M. Schlingemann, H. Vogts, and R. F. Werner. On the structure of Clifford quantum cellular automata. Journal of Mathematical Physics, 49 (11): 112104, 2008. https:/​/​doi.org/​10.1063/​1.3005565.

[70] J. Gütschow, S. Uphoff, R. F. Werner, and Z. Zimborás. Time asymptotics and entanglement generation of Clifford quantum cellular automata. Journal of Mathematical Physics, 51 (1): 015203, 2010a. http:/​/​doi.org/​10.1063/​1.3278513.

[71] J. Gütschow. Entanglement generation of Clifford quantum cellular automata. Applied Physics B, 98 (4): 623–633, 2010. https:/​/​doi.org/​10.1007/​s00340-009-3840-1.

[72] J. Gütschow, V. Nesme, and R. F. Werner. The fractal structure of cellular automata on abelian groups. Discrete Mathematics & Theoretical Computer Science, DMTCS Proceedings vol. AL, Automata 2010 - 16th Intl. Workshop on CA and DCS, 2010b.

[73] J. Haah. Algebraic methods for quantum codes on lattices. Revista Colombiana de Matemáticas, 50: 299 – 349, 2016. https:/​/​doi.org/​10.15446/​recolma.v50n2.62214.

[74] S. Gopalakrishnan and B. Zakirov. Facilitated quantum cellular automata as simple models with non-thermal eigenstates and dynamics. Quantum Science and Technology, 3 (4): 044004, 2018. https:/​/​doi.org/​10.1088/​2058-9565/​aad759.

[75] H. Kim, T. N. Ikeda, and D. A. Huse. Testing whether all eigenstates obey the eigenstate thermalization hypothesis. Phys. Rev. E, 90: 052105, 2014. https:/​/​doi.org/​10.1103/​PhysRevE.90.052105.

[76] J. Haah. Clifford quantum cellular automata: Trivial group in 2d and Witt group in 3d. arXiv:1907.02075, 2019.

[77] 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.

[78] A. Molina and J. Watrous. Revisiting the simulation of quantum Turing machines by quantum circuits. Proc. R. Soc. A., 475: 20180767, 2019. https:/​/​doi.org/​10.1098/​rspa.2018.0767.

[79] R. Raussendorf. Quantum cellular automaton for universal quantum computation. Phys. Rev. A, 72: 022301, 2005a. https:/​/​doi.org/​10.1103/​PhysRevA.72.022301.

[80] 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.

[81] K. G. H. Vollbrecht and J. I. Cirac. Reversible universal quantum computation within translation-invariant systems. Phys. Rev. A, 73: 012324, 2006. https:/​/​doi.org/​10.1103/​PhysRevA.73.012324.

[82] P. Arrighi, R. Fargetton, and Z. 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.

[83] P. Arrighi and J. Grattage. A simple n-dimensional intrinsically universal quantum cellular automaton. In A. Dediu, H. Fernau, and C. Martín-Vide, editors, Language and Automata Theory and Applications, pages 70–81, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg. https:/​/​doi.org/​10.1007/​978-3-642-13089-2_6.

[84] P. Arrighi and J. Grattage. Intrinsically universal n-dimensional quantum cellular automata. Journal of Computer and System Sciences, 78 (6): 1883 – 1898, 2012b. https:/​/​doi.org/​10.1016/​j.jcss.2011.12.008.

[85] P. Arrighi and J. Grattage. Partitioned quantum cellular automata are intrinsically universal. Natural Computing, 11 (1): 13–22, 2012c. https:/​/​doi.org/​10.1007/​s11047-011-9277-6.

[86] S. Bravyi and A. Kitaev. Fermionic quantum computation. Annals of Physics, 298 (1): 210 – 226, 2002. https:/​/​doi.org/​10.1006/​aphy.2002.6254.

[87] M. Steudtner and S. Wehner. Fermion-to-qubit mappings with varying resource requirements for quantum simulation. New Journal of Physics, 20 (6): 063010, 2018. https:/​/​doi.org/​10.1088/​1367-2630/​aac54f.

[88] S. C. Benjamin. Schemes for parallel quantum computation without local control of qubits. Phys. Rev. A, 61: 020301, 2000. https:/​/​doi.org/​10.1103/​PhysRevA.61.020301.

[89] R. Raussendorf. Quantum computation via translation-invariant operations on a chain of qubits. Phys. Rev. A, 72: 052301, 2005b. https:/​/​doi.org/​10.1103/​PhysRevA.72.052301.

[90] J. A. Jones. Quantum computing with NMR. Progress in Nuclear Magnetic Resonance Spectroscopy, 59 (2): 91 – 120, 2011. https:/​/​doi.org/​10.1016/​j.pnmrs.2010.11.001.

[91] S. C. Benjamin. Quantum computing without local control of qubit-qubit interactions. Phys. Rev. Lett., 88: 017904, 2001. https:/​/​doi.org/​10.1103/​PhysRevLett.88.017904.

[92] S. C. Benjamin and S. Bose. Quantum computing in arrays coupled by ``always-on'' interactions. Phys. Rev. A, 70: 032314, 2004. https:/​/​doi.org/​10.1103/​PhysRevA.70.032314.

[93] J. Twamley. Quantum-cellular-automata quantum computing with endohedral fullerenes. Phys. Rev. A, 67: 052318, 2003. https:/​/​doi.org/​10.1103/​PhysRevA.67.052318.

[94] S. C. Benjamin, A. Ardavan, G. A. D. Briggs, D. A. Britz, D. Gunlycke, J. Jefferson, M. A. G. Jones, D. F. Leigh, B. W. Lovett, A. N. Khlobystov, S. A. Lyon, J. J. L. Morton, K. Porfyrakis, M. R. Sambrook, and A. M. Tyryshkin. Towards a fullerene-based quantum computer. Journal of Physics: Condensed Matter, 18 (21): S867, 2006. https:/​/​doi.org/​10.1088/​0953-8984/​18/​21/​S12.

[95] T. M. Wintermantel, Y. Wang, G. Lochead, S. Shevate, G. K. Brennen, and S. Whitlock. Unitary and nonunitary quantum cellular automata with Rydberg arrays. Phys. Rev. Lett., 124: 070503, 2020. https:/​/​doi.org/​10.1103/​PhysRevLett.124.070503.

[96] P. Arrighi and S. Martiel. Quantum causal graph dynamics. Phys. Rev. D, 96: 024026, 2017. https:/​/​doi.org/​10.1103/​PhysRevD.96.024026.

[97] A. Kitaev. Anyons in an exactly solved model and beyond. Annals of Physics, 321 (1): 2 – 111, 2006. https:/​/​doi.org/​10.1016/​j.aop.2005.10.005.

[98] P. Zanardi. Stabilizing quantum information. Phys. Rev. A, 63: 012301, 2000. https:/​/​doi.org/​10.1103/​PhysRevA.63.012301.

[99] V. Jones and V. S. Sunder. Introduction to Subfactors. London Mathematical Society Lecture Note Series. Cambridge University Press, 1997. https:/​/​doi.org/​10.1017/​CBO9780511566219.

[100] P. Jordan and E. Wigner. Über das Paulische Äquivalenzverbot. Z. Physik, 47: 631–651, 1928. https:/​/​doi.org/​10.1007/​BF01331938.

[101] M.A. Nielsen. The fermionic canonical commutation relations and the Jordan-Wigner transform, 2005. http:/​/​michaelnielsen.org/​blog/​archive/​notes/​fermions_and_jordan_wigner.pdf.

[102] J. Baez. The Ten-Fold Way (Part 3), blog post at ``The n-Category Café'', 2014. https:/​/​golem.ph.utexas.edu/​category/​2014/​08/​the_tenfold_way_part_3.html.

[103] M. Freedman, J. Haah, and M. B. Hastings. The group structure of quantum cellular automata. arXiv:1910.07998, 2019.

[104] T. Toffoli and N. H. Margolus. Invertible cellular automata: A review. Physica D: Nonlinear Phenomena, 45 (1): 229 – 253, 1990. https:/​/​doi.org/​10.1016/​0167-2789(90)90185-R.

[105] J. I. Cirac, D. Perez-Garcia, N. Schuch, and F. Verstraete. Matrix product unitaries: structure, symmetries, and topological invariants. Journal of Statistical Mechanics: Theory and Experiment, 2017 (8): 083105, 2017. https:/​/​doi.org/​10.1088/​1742-5468/​aa7e55.

[106] M. B. Şahinoğlu, S. K. Shukla, F. Bi, and X. Chen. Matrix product representation of locality preserving unitaries. Phys. Rev. B, 98: 245122, 2018. https:/​/​doi.org/​10.1103/​PhysRevB.98.245122.

[107] J. C. Bridgeman and C. T. Chubb. Hand-waving and interpretive dance: an introductory course on tensor networks. Journal of Physics A: Mathematical and Theoretical, 50 (22): 223001, 2017. https:/​/​doi.org/​10.1088/​1751-8121/​aa6dc3.

[108] Z. Gong, C. Sünderhauf, N. Schuch, and J. I. Cirac. Classification of Matrix-Product Unitaries with Symmetries. Phys. Rev. Lett., 124: 100402, 2020. https:/​/​doi.org/​10.1103/​PhysRevLett.124.100402.

[109] M. B. Hastings. Classifying quantum phases with the Kirby torus trick. Phys. Rev. B, 88: 165114, 2013. https:/​/​doi.org/​10.1103/​PhysRevB.88.165114.

[110] L. Piroli, A. Turzillo, S. K. Shukla, and J. I. Cirac. Fermionic quantum cellular automata and generalized matrix product unitaries. arXiv:2007.11905, 2020.

[111] H. F. Trotter. On the product of semi-groups of operators. Proceedings of the American Mathematical Society, 10 (4): 545–551, 1959. https:/​/​doi.org/​10.2307/​2033649.

[112] M. Suzuki. Fractal decomposition of exponential operators with applications to many-body theories and Monte Carlo simulations. Physics Letters A, 146 (6): 319 – 323, 1990. https:/​/​doi.org/​10.1016/​0375-9601(90)90962-N.

[113] T. J. Osborne. Efficient approximation of the dynamics of one-dimensional quantum spin systems. Phys. Rev. Lett., 97: 157202, 2006. https:/​/​doi.org/​10.1103/​PhysRevLett.97.157202.

[114] M. Holzäpfel and M. B. Plenio. Efficient certification and simulation of local quantum many-body Hamiltonians. arXiv:1712.04396, 2017.

[115] A. H. Werner H. Wilming. Finite group velocity implies locality of interactions. arXiv:2006.10062, 2020.

[116] B. C. Hall. Lie groups, Lie algebras, and representations: an elementary introduction. Springer, New York, 2003. ISBN 0387401229. https:/​/​doi.org/​10.1007/​978-1-4614-7116-5_16.

[117] Z. Zimborás, T. Farrelly, S. Farkas, and L. Masanes. Does causal dynamics imply local interactions? arXiv:2006.10707, 2020.

[118] T. Dittrich, P. Hänggi, G.-L. Ingold, B. Kramer, G. Schön, and W. Zwerger. Quantum Transport and Dissipation. Wiley-VCH, Windheim, 1998.

[119] X.-G. Wen. Colloquium: Zoo of quantum-topological phases of matter. Rev. Mod. Phys., 89: 041004, 2017. https:/​/​doi.org/​10.1103/​RevModPhys.89.041004.

[120] D. Tong. Lectures on the Quantum Hall Effect. arXiv:1606.06687, 2016.

[121] T. Kitagawa, E. Berg, M. Rudner, and E. Demler. Topological characterization of periodically driven quantum systems. Phys. Rev. B, 82: 235114, 2010a. https:/​/​doi.org/​10.1103/​PhysRevB.82.235114.

[122] M. S. Rudner, N. H. Lindner, E. Berg, and M. Levin. Anomalous edge states and the bulk-edge correspondence for periodically driven two-dimensional systems. Phys. Rev. X, 3: 031005, 2013. https:/​/​doi.org/​10.1103/​PhysRevX.3.031005.

[123] P. Titum, N. H. Lindner, M. C. Rechtsman, and G. Refael. Disorder-induced Floquet topological insulators. Phys. Rev. Lett., 114: 056801, 2015. https:/​/​doi.org/​10.1103/​PhysRevLett.114.056801.

[124] P. Titum, E. Berg, M. S. Rudner, G. Refael, and N. H. Lindner. Anomalous Floquet-Anderson insulator as a nonadiabatic quantized charge pump. Phys. Rev. X, 6: 021013, 2016. https:/​/​doi.org/​10.1103/​PhysRevX.6.021013.

[125] B. R. Duschatko, P. T. Dumitrescu, and A. C. Potter. Tracking the quantized information transfer at the edge of a chiral Floquet phase. Phys. Rev. B, 98: 054309, 2018. https:/​/​doi.org/​10.1103/​PhysRevB.98.054309.

[126] M. A. Levin and X.-G. Wen. String-net condensation: A physical mechanism for topological phases. Phys. Rev. B, 71: 045110, 2005. https:/​/​doi.org/​10.1103/​PhysRevB.71.045110.

[127] K. Walker and Z. Wang. (3+1)-TQFTs and topological insulators. Front. Phys., 7: 150–159, 2023. https:/​/​doi.org/​10.1007/​s11467-011-0194-z.

[128] C. W. von Keyserlingk, F. J. Burnell, and S. H. Simon. Three-dimensional topological lattice models with surface anyons. Phys. Rev. B, 87: 045107, 2013. https:/​/​doi.org/​10.1103/​PhysRevB.87.045107.

[129] D. T. Stephen, H. P. Nautrup, J. Bermejo-Vega, J. Eisert, and R. Raussendorf. Subsystem symmetries, quantum cellular automata, and computational phases of quantum matter. Quantum, 3: 142, 2019. https:/​/​doi.org/​10.22331/​q-2019-05-20-142.

[130] L. Fidkowski, J. Haah, and M. B. Hastings. Exactly solvable model for a $4+1\mathrm{D}$ beyond-cohomology symmetry-protected topological phase. Phys. Rev. B, 101: 155124, 2020. https:/​/​doi.org/​10.1103/​PhysRevB.101.155124.

[131] T. Kitagawa, M. S. Rudner, E. Berg, and E. Demler. Exploring topological phases with quantum walks. Phys. Rev. A, 82: 033429, 2010b. https:/​/​doi.org/​10.1103/​PhysRevA.82.033429.

[132] C. Cedzich, T. Geib, F. A. Grünbaum, C. Stahl, L. Velázquez, A. H. Werner, and R. F. Werner. The topological classification of one-dimensional symmetric quantum walks. Annales Henri Poincaré, 19 (2): 325–383, 2018a. https:/​/​doi.org/​10.1007/​s00023-017-0630-x.

[133] C. Cedzich, F. A. Grünbaum, C. Stahl, L. Velázquez, A. H. Werner, and R. F. Werner. Bulk-edge correspondence of one-dimensional quantum walks. Journal of Physics A: Mathematical and Theoretical, 49 (21): 21LT01, 2016. https:/​/​doi.org/​10.1088/​1751-8113/​49/​21/​21LT01.

[134] C. Cedzich, T. Geib, C. Stahl, L. Velázquez, A. H. Werner, and R. F. Werner. Complete homotopy invariants for translation invariant symmetric quantum walks on a chain. Quantum, 2: 95, 2018b. https:/​/​doi.org/​10.22331/​q-2018-09-24-95.

[135] S. E. Venegas-Andraca. Quantum walks: a comprehensive review. Quantum Information Processing, 11 (5): 1015–1106, 2012. https:/​/​doi.org/​10.1007/​s11128-012-0432-5.

[136] A. J. Bracken, D. Ellinas, and I. Smyrnakis. Free-Dirac-particle evolution as a quantum random walk. Phys. Rev. A, 75: 022322, 2007. https:/​/​doi.org/​10.1103/​PhysRevA.75.022322.

[137] G. di Molfetta and F. Debbasch. Discrete-time quantum walks: Continuous limit and symmetries. Journal of Mathematical Physics, 53 (12): 123302, 2012. https:/​/​doi.org/​10.1063/​1.4764876.

[138] P. Kurzyński. Relativistic effects in quantum walks: Klein's paradox and Zitterbewegung. Physics Letters A, 372 (40): 6125 – 6129, 2008. https:/​/​doi.org/​10.1016/​j.physleta.2008.08.017.

[139] T. C. Farrelly and A. J. Short. Discrete spacetime and relativistic quantum particles. Phys. Rev. A, 89: 062109, 2014b. https:/​/​doi.org/​10.1103/​PhysRevA.89.062109.

[140] P. Arrighi, V. Nesme, and M. Forets. The Dirac equation as a quantum walk: higher dimensions, observational convergence. Journal of Physics A: Mathematical and Theoretical, 47 (46): 465302, 2014a. https:/​/​doi.org/​10.1088/​1751-8113/​47/​46/​465302.

[141] G. di Molfetta, M. Brachet, and F. Debbasch. Quantum walks as massless Dirac fermions in curved space-time. Phys. Rev. A, 88: 042301, 2013. https:/​/​doi.org/​10.1103/​PhysRevA.88.042301.

[142] P. Arrighi, S. Facchini, and M. Forets. Quantum walking in curved spacetime. Quantum Information Processing, 15 (8): 3467–3486, 2016. https:/​/​doi.org/​10.1007/​s11128-016-1335-7.

[143] P. Arrighi and S. Facchini. Quantum walking in curved spacetime: $(3+1)$ dimensions, and beyond. arXiv:1609.00305, 2016.

[144] A. Mallick, S. Mandal, A. Karan, and C. M. Chandrashekar. Simulating Dirac Hamiltonian in curved space-time by split-step quantum walk. Journal of Physics Communications, 3: 015012, 2019. https:/​/​doi.org/​10.1088/​2399-6528/​aafe2f.

[145] L. A. Bru, M. Hinarejos, F. Silva, G. J. de Valcárcel, and E. Roldán. Electric quantum walks in two dimensions. Phys. Rev. A, 93: 032333, 2016. https:/​/​doi.org/​10.1103/​PhysRevA.93.032333.

[146] C. Cedzich, T. Geib, A.H. Werner, and R.F. Werner. Quantum walks in external gauge fields. Journal of Mathematical Physics, 60 (1): 012107, 2019. https:/​/​doi.org/​10.1063/​1.5054894.

[147] G. Di Molfetta, M. Brachet, and F. Debbasch. Quantum walks in artificial electric and gravitational fields. Physica A: Statistical Mechanics and its Applications, 397: 157 – 168, 2014. https:/​/​doi.org/​10.1016/​j.physa.2013.11.036.

[148] G. M. D'Ariano, N. Mosco, P. Perinotti, and A. Tosini. Discrete Feynman propagator for the Weyl quantum walk in 2+1 dimensions. Europhysics Letters, 109 (4): 40012, 2015. https:/​/​doi.org/​10.1209/​0295-5075/​109/​40012.

[149] S. Succi and R. Benzi. Lattice Boltzmann equation for quantum mechanics. Physica D: Nonlinear Phenomena, 69 (3): 327 – 332, 1993. https:/​/​doi.org/​10.1016/​0167-2789(93)90096-J.

[150] D. A. Meyer. Quantum lattice gases and their invariants. International Journal of Modern Physics C, 08 (04): 717–735, 1997. https:/​/​doi.org/​10.1142/​S0129183197000618.

[151] B. M. Boghosian and W. Taylor. Simulating quantum mechanics on a quantum computer. Physica D: Nonlinear Phenomena, 120 (1): 30 – 42, 1998. https:/​/​doi.org/​10.1016/​S0167-2789(98)00042-6.

[152] J. Yepez and B. Boghosian. An efficient and accurate quantum lattice-gas model for the many-body Schrödinger wave equation. Computer Physics Communications, 146 (3): 280 – 294, 2002. https:/​/​doi.org/​10.1016/​S0010-4655(02)00419-8.

[153] D. A. Meyer and A. Shakeel. Quantum cellular automata without particles. Phys. Rev. A, 93: 012333, 2016. https:/​/​doi.org/​10.1103/​PhysRevA.93.012333.

[154] P. C. S. Costa, R. Portugal, and F. de Melo. Quantum Walks via Quantum Cellular Automata. Quantum Inf Process, 17: 226, 2018. https:/​/​doi.org/​10.1007/​s11128-018-1983-x.

[155] J. Yepez. Quantum lattice gas algorithmic representation of gauge field theory. Proceedings, Quantum Information Science and Technology II, 9996: 99960N, 2016a. https:/​/​doi.org/​10.1117/​12.2246702.

[156] J. Yepez. Quantum computational representation of gauge field theory. arXiv:1612.09291v3, 2016b.

[157] A. Bisio, G. M. D'Ariano, P. Perinotti, and A. Tosini. Thirring quantum cellular automaton. Phys. Rev. A, 97: 032132, 2018a. https:/​/​doi.org/​10.1103/​PhysRevA.97.032132.

[158] A. Ahlbrecht, A. Alberti, D. Meschede, V. B. Scholz, A. H. Werner, and R. F. Werner. Molecular binding in interacting quantum walks. New Journal of Physics, 14 (7): 073050, 2012. https:/​/​doi.org/​10.1088/​1367-2630/​14/​7/​073050.

[159] A. Bisio, G. M. D’Ariano, N. Mosco, P. Perinotti, and A. Tosini. Solutions of a two-particle interacting quantum walk. Entropy, 20 (6), 2018b. https:/​/​doi.org/​10.3390/​e20060435.

[160] Y. Lahini, M. Verbin, S.D. Huber, Y. Bromberg, R. Pugatch, and Y. Silberberg. Quantum walk of two interacting bosons. Phys. Rev. A, 86: 011603, 2012. https:/​/​doi.org/​10.1103/​PhysRevA.86.011603.

[161] P. L. Krapivsky, J. M. Luck, and K. Mallick. Interacting quantum walkers: two-body bosonic and fermionic bound states. Journal of Physics A: Mathematical and Theoretical, 48 (47): 475301, 2015. https:/​/​doi.org/​10.1088/​1751-8113/​48/​47/​475301.

[162] P. Arrighi, S. Facchini, and M. Forets. Discrete Lorentz covariance for quantum walks and quantum cellular automata. New Journal of Physics, 16 (9): 093007, 2014b. https:/​/​doi.org/​10.1088/​1367-2630/​16/​9/​093007.

[163] A. Bisio, G. Mauro D'Ariano, and P. Perinotti. Special relativity in a discrete quantum universe. Phys. Rev. A, 94: 042120, 2016a. https:/​/​doi.org/​10.1103/​PhysRevA.94.042120.

[164] A. Bibeau-Delisle, A. Bisio, G. M. D'Ariano, P. Perinotti, and A. Tosini. Doubly special relativity from quantum cellular automata. EPL (Europhysics Letters), 109 (5): 50003, 2015. https:/​/​doi.org/​10.1209/​0295-5075/​109/​50003.

[165] M. Creutz. Quarks, Gluons and Lattices. Cambridge Monographs on Mathematical Physics. Cambridge University Press, 1983.

[166] M. McGuigan. Quantum Cellular Automata from Lattice Field Theories. arXiv:quant-ph/​0307176, 2003.

[167] S. P. Jordan, K. S. M. Lee, and J. Preskill. Quantum algorithms for quantum field theories. Science, 336 (6085): 1130–1133, 2012. https:/​/​doi.org/​10.1126/​science.1217069.

[168] S. P. Jordan, K. S. M. Lee, and J. Preskill. Quantum Algorithms for Fermionic Quantum Field Theories. arXiv:1404.7115, 2014.

[169] A. Bisio, G. M. D'Ariano, and A. Tosini. Quantum field as a quantum cellular automaton i: the Dirac free evolution in one dimension. arXiv:1212.2839, 2012. https:/​/​doi.org/​10.1016/​j.aop.2014.12.016.

[170] C. Destri and H. J. de Vega. Light cone lattice approach to fermionic theories in 2-d: the massive Thirring model. Nucl. Phys., B290: 363, 1987. https:/​/​doi.org/​10.1016/​0550-3213(87)90193-3.

[171] G. M. D'Ariano. The quantum field as a quantum computer. Physics Letters A, 376 (5): 697–702, 2012a. https:/​/​doi.org/​10.1016/​j.physleta.2011.12.021.

[172] G. M. D'Ariano. Physics as quantum information processing: Quantum fields as quantum automata. Foundations of Probability and Physics - 6, AIP Conf. Proc., page 1424 371, 2012b. https:/​/​doi.org/​10.1063/​1.3688990.

[173] A. Bisio, G. M. D'Ariano, P. Perinotti, and A. Tosini. Free quantum field theory from quantum cellular automata. Foundations of Physics, 45 (10): 1137–1152, 2015a. https:/​/​doi.org/​10.1007/​s10701-015-9934-1.

[174] A. Bisio, G. M. D'Ariano, P. Perinotti, and A. Tosini. Weyl, Dirac and Maxwell quantum cellular automata. Foundations of Physics, 45 (10): 1203–1221, 2015b. https:/​/​doi.org/​10.1007/​s10701-015-9927-0.

[175] G. M. D'Ariano and P. Perinotti. Quantum cellular automata and free quantum field theory. Frontiers of Physics, 12 (1): 120301, 2016. https:/​/​doi.org/​10.1007/​s11467-016-0616-z.

[176] A. Mallick and C. Chandrashekar. Dirac cellular automaton from split-step quantum walk. Scientific Reports, 6: 25779, 2016. https:/​/​doi.org/​10.1038/​srep25779.

[177] C. Huerta Alderete, S. Singh, N. H. Nguyen, D. Zhu, R. Balu, C. Monroe, C. M. Chandrashekar, and N. M. Linke. Quantum walks and dirac cellular automata on a programmable trapped-ion quantum computer. arXiv:2002.02537, 2020. https:/​/​doi.org/​10.1038/​s41467-020-17519-4.

[178] M. DeMarco and X.-G. Wen. A Novel Non-Perturbative Lattice Regularization of an Anomaly-Free $1 + 1d$ Chiral ${SU}(2)$ Gauge Theory. arXiv:1706.04648, 2017.

[179] P. Arrighi, C. Bény, and T. Farrelly. A quantum cellular automaton for one-dimensional QED. Quantum Inf Process, 19: 88, 2019. https:/​/​doi.org/​10.1007/​s11128-019-2555-4.

[180] A. Bisio, G. M. D’Ariano, and P. Perinotti. Quantum cellular automaton theory of light. Annals of Physics, 368: 177 – 190, 2016b. https:/​/​doi.org/​10.1016/​j.aop.2016.02.009.

[181] L. de Broglie. Une novelle conception de la lumiere. Hermamm & Cie, 181, 1934.

[182] P. Arrighi, R. Fargetton, V. Nesme, and E. Thierry. Applying causality principles to the axiomatization of probabilistic cellular automata. In B. Löwe, D. Normann, I. Soskov, and A. Soskova, editors, Models of Computation in Context, pages 1–10, Berlin, Heidelberg, 2011b. Springer. https:/​/​doi.org/​10.1007/​978-3-642-21875-0_1.

[183] A. W. W. Ludwig. Topological phases: classification of topological insulators and superconductors of non-interacting fermions, and beyond. Physica Scripta, T168: 014001, 2015. https:/​/​doi.org/​10.1088/​0031-8949/​2015/​t168/​014001.

[184] T. J. Osborne. Continuum Limits of Quantum Lattice Systems. arXiv:1901.06124, 2019.

[185] S. Gogioso, M. E. Stasinou, and B. Coecke. Functorial evolution of quantum fields. arXiv:2003.13271, 2020.

[186] B. Simon. The Statistical Mechanics of Lattice Gases, volume 1. Princeton University Press, Princeton, New Jersey, 1993. https:/​/​doi.org/​10.1515/​9781400863433.

[187] R. Haag. Local Quantum Physics: Fields, Particles, Algebras. Springer-Verlag, Berlin, 1992. https:/​/​doi.org/​10.1007/​978-3-642-97306-2.

Cited by

[1] Todd A. Brun and Leonard Mlodinow, "Quantum cellular automata and quantum field theory in two spatial dimensions", Physical Review A 102 6, 062222 (2020).

[2] Paolo Perinotti, "Cellular automata in operational probabilistic theories", arXiv:1911.11216, Quantum 4, 294 (2020).

[3] Edward Gillman, Federico Carollo, and Igor Lesanovsky, "Numerical simulation of quantum nonequilibrium phase transitions without finite-size effects", Physical Review A 103 4, L040201 (2021).

[4] O. Duranthon and Giuseppe Di Molfetta, "Coarse-grained quantum cellular automata", Physical Review A 103 3, 032224 (2021).

[5] P. Arrighi, "An overview of quantum cellular automata", Natural Computing 18 4, 885 (2019).

[6] Zongping Gong, Lorenzo Piroli, and J. Ignacio Cirac, "Topological Lower Bound on Quantum Chaos by Entanglement Growth", arXiv:2012.02772, Physical Review Letters 126 16, 160601 (2021).

[7] Alessio Celi, Benoît Vermersch, Oscar Viyuela, Hannes Pichler, Mikhail D. Lukin, and Peter Zoller, "Emerging Two-Dimensional Gauge Theories in Rydberg Configurable Arrays", Physical Review X 10 2, 021057 (2020).

[8] T. M. Wintermantel, Y. Wang, G. Lochead, S. Shevate, G. K. Brennen, and S. Whitlock, "Unitary and Nonunitary Quantum Cellular Automata with Rydberg Arrays", Physical Review Letters 124 7, 070503 (2020).

[9] Lorenzo Piroli and J. Ignacio Cirac, "Quantum Cellular Automata, Tensor Networks, and Area Laws", Physical Review Letters 125 19, 190402 (2020).

[10] Edward Gillman, Federico Carollo, and Igor Lesanovsky, "Nonequilibrium Phase Transitions in (1 +1 )-Dimensional Quantum Cellular Automata with Controllable Quantum Correlations", Physical Review Letters 125 10, 100403 (2020).

[11] Terry Farrelly and Julien Streich, "Discretizing quantum field theories for quantum simulation", arXiv:2002.02643.

[12] Lorenzo Piroli, Alex Turzillo, Sujeet K. Shukla, and J. Ignacio Cirac, "Fermionic quantum cellular automata and generalized matrix product unitaries", arXiv:2007.11905, Journal of Statistical Mechanics: Theory and Experiment 2021 1, 013107 (2020).

[13] Ruhi Shah and Jonathan Gorard, "Quantum Cellular Automata, Black Hole Thermodynamics, and the Laws of Quantum Complexity", arXiv:1910.00578.

[14] Zoltán Zimborás, Terry Farrelly, Szilárd Farkas, and Lluis Masanes, "Does causal dynamics imply local interactions?", arXiv:2006.10707.

[15] Alessandro Bisio, Nicola Mosco, and Paolo Perinotti, "Scattering and perturbation theory for discrete-time dynamics", arXiv:1912.09768.

[16] Leonard Mlodinow and Todd A. Brun, "Quantum field theory from a quantum cellular automaton in one spatial dimension and a no-go theorem in higher dimensions", Physical Review A 102 4, 042211 (2020).

[17] Tom Farshi, Daniele Toniolo, Carlos E. González-Guillén, Álvaro M. Alhambra, and Lluis Masanes, "Time-periodic dynamics generates pseudo-random unitaries", arXiv:2007.03339.

[18] Henrik Wilming and Albert H. Werner, "Lieb-Robinson bounds imply locality of interactions", arXiv:2006.10062.

[19] Leonard Mlodinow and Todd A. Brun, "Fermionic and bosonic quantum field theories from quantum cellular automata in three spatial dimensions", arXiv:2011.05597.

[20] David Berenstein and Jiayao Zhao, "Exotic equilibration dynamics on a 1-D quantum CNOT gate lattice", arXiv:2102.05745.

[21] Luca Apadula, Alessandro Bisio, Giacomo Mauro D'Ariano, and Paolo Perinotti, "Symmetries of the Dirac quantum walk and emergence of the de Sitter group", Journal of Mathematical Physics 61 8, 082202 (2020).

[22] C. Cedzich, T. Geib, and R. F. Werner, "An algorithm to factorize quantum walks into shift and coin operations", arXiv:2102.12951.

The above citations are from Crossref's cited-by service (last updated successfully 2021-04-21 14:21:34) and SAO/NASA ADS (last updated successfully 2021-04-21 14:21:35). The list may be incomplete as not all publishers provide suitable and complete citation data.