QUIT Group, Dipartimento di Fisica, Università degli studi di Pavia, and INFN sezione di Pavia, via Bassi 6, 27100 Pavia, Italy
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
The theory of cellular automata in operational probabilistic theories is developed. We start introducing the composition of infinitely many elementary systems, and then use this notion to define update rules for such infinite composite systems. The notion of causal influence is introduced, and its relation with the usual property of signalling is discussed. We then introduce homogeneity, namely the property of an update rule to evolve every system in the same way, and prove that systems evolving by a homogeneous rule always correspond to vertices of a Cayley graph. Next, we define the notion of locality for update rules. Cellular automata are then defined as homogeneous and local update rules. Finally, we prove a general version of the wrapping lemma, that connects CA on different Cayley graphs sharing some small-scale structure of neighbourhoods.
► BibTeX data
► References
[1] Lucien Hardy. Disentangling nonlocality and teleportation, 1999. arXiv:quant-ph/9906123.
arXiv:quant-ph/9906123
[2] Lucien Hardy. Quantum theory from five reasonable axioms, 2001. arXiv:quant-ph/0101012.
arXiv:quant-ph/0101012
[3] Christopher A. Fuchs. Quantum mechanics as quantum information (and only a little more), 2002. arXiv:quant-ph/0205039.
arXiv:quant-ph/0205039
[4] Gilles Brassard. Is information the key? Nature Physics, 1(1):2–4, 2005. URL: https://doi.org/10.1038/nphys134.
https://doi.org/10.1038/nphys134
[5] Jonathan Barrett. Information processing in generalized probabilistic theories. Phys. Rev. A, 75:032304, Mar 2007. URL: https://doi.org/10.1103/PhysRevA.75.032304.
https://doi.org/10.1103/PhysRevA.75.032304
[6] Giacomo M. D’Ariano. Probabilistic theories: What is special about quantum mechanics? In Alisa Bokulich and Gregg Jaeger, editors, Philosophy of Quantum Information and Entanglement, chapter 5, pages 85–126. Cambridge University Press., 2010. URL: https://doi.org/10.1017/CBO9780511676550.007.
https://doi.org/10.1017/CBO9780511676550.007
[7] Giacomo Mauro D’Ariano and Alessandro Tosini. Testing axioms for quantum theory on probabilistic toy-theories. Quantum Information Processing, 9(2):95–141, 2010. URL: https://doi.org/10.1007/s11128-010-0172-3.
https://doi.org/10.1007/s11128-010-0172-3
[8] Giulio Chiribella, Giacomo Mauro D’Ariano, and Paolo Perinotti. Probabilistic theories with purification. Phys. Rev. A, 81:062348, Jun 2010. URL: https://doi.org/10.1103/PhysRevA.81.062348.
https://doi.org/10.1103/PhysRevA.81.062348
[9] Giulio Chiribella, Giacomo Mauro D’Ariano, and Paolo Perinotti. Informational derivation of quantum theory. Phys. Rev. A, 84:012311, Jul 2011. URL: https://doi.org/10.1103/PhysRevA.84.012311.
https://doi.org/10.1103/PhysRevA.84.012311
[10] Lluís Masanes and Markus P Müller. A derivation of quantum theory from physical requirements. New Journal of Physics, 13(6):063001, jun 2011. URL: https://doi.org/10.1088/1367-2630/13/6/063001.
https://doi.org/10.1088/1367-2630/13/6/063001
[11] Borivoje Dakić and Časlav Brukner. Quantum theory and beyond: is entanglement special? In H. Halvorson, editor, Deep Beauty: Understanding the Quantum World through Mathematical Innovation, pages 365–392. Cambridge University Press, 2011. URL: https://doi.org/10.1017/CBO9780511976971.011.
https://doi.org/10.1017/CBO9780511976971.011
[12] Peter Rastall. Locality, Bell’s theorem, and quantum mechanics. Foundations of Physics, 15(9):963–972, Sep 1985. URL: https://doi.org/10.1007/BF00739036.
https://doi.org/10.1007/BF00739036
[13] Sandu Popescu and Daniel Rohrlich. Quantum nonlocality as an axiom. Foundations of Physics, 24(3):379–385, Mar 1994. URL: https://doi.org/10.1007/BF02058098.
https://doi.org/10.1007/BF02058098
[14] Robert W. Spekkens. Evidence for the epistemic view of quantum states: A toy theory. Phys. Rev. A, 75:032110, Mar 2007. URL: https://doi.org/10.1103/PhysRevA.75.032110.
https://doi.org/10.1103/PhysRevA.75.032110
[15] Giacomo Mauro D’Ariano, Giulio Chiribella, and Paolo Perinotti. Quantum theory from first principles: an informational approach. Cambridge University Press, 2017. URL: https://doi.org/10.1017/9781107338340.
https://doi.org/10.1017/9781107338340
[16] Howard Barnum, Jonathan Barrett, Matthew Leifer, and Alexander Wilce. Teleportation in general probabilistic theories, 2008. arXiv:0805.3553.
arXiv:0805.3553
[17] Howard Barnum and Alexander Wilce. Information processing in convex operational theories. Electronic Notes in Theoretical Computer Science, 270(1):3 – 15, 2011. Proceedings of the Joint 5th International Workshop on Quantum Physics and Logic and 4th Workshop on Developments in Computational Models (QPL/DCM 2008). URL: https://doi.org/10.1016/j.entcs.2011.01.002.
https://doi.org/10.1016/j.entcs.2011.01.002
[18] Bob Coecke. Kindergarten quantum mechanics: Lecture notes. AIP Conference Proceedings, 810(1):81–98, 2006. URL: https://doi.org/10.1063/1.2158713.
https://doi.org/10.1063/1.2158713
[19] Bob Coecke and Aleks Kissinger. Picturing Quantum Processes: A First Course in Quantum Theory and Diagrammatic Reasoning. Cambridge University Press, 2017. URL: https://doi.org/10.1017/9781316219317.
https://doi.org/10.1017/9781316219317
[20] Günther Ludwig. Foundations of quantum mechanics II. New York, NY (United States); Springer-Verlag, 1985. URL: https://doi.org/10.1007/978-3-662-28726-2.
https://doi.org/10.1007/978-3-662-28726-2
[21] Alexander Wilce. Test spaces and orthoalgebras. In Bob Coecke, David Moore, and Alexander Wilce, editors, Current Research in Operational Quantum Logic: Algebras, Categories, Languages, pages 81–114. Springer Netherlands, Dordrecht, 2000. URL: https://doi.org/10.1007/978-94-017-1201-9_4.
https://doi.org/10.1007/978-94-017-1201-9_4
[22] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, 2010. URL: https://doi.org/10.1017/CBO9780511976667.
https://doi.org/10.1017/CBO9780511976667
[23] Alessandro Bisio, Giacomo Mauro D’Ariano, and Alessandro Tosini. Dirac quantum cellular automaton in one dimension: Zitterbewegung and scattering from potential. Phys. Rev. A, 88:032301, Sep 2013. URL: https://doi.org/10.1103/PhysRevA.88.032301.
https://doi.org/10.1103/PhysRevA.88.032301
[24] Alessandro Bisio, Giacomo Mauro D’Ariano, and Alessandro Tosini. Quantum field as a quantum cellular automaton: The dirac free evolution in one dimension. Annals of Physics, 354:244 – 264, 2015. URL: https://doi.org/10.1016/j.aop.2014.12.016.
https://doi.org/10.1016/j.aop.2014.12.016
[25] Giacomo Mauro D’Ariano and Paolo Perinotti. Derivation of the dirac equation from principles of information processing. Phys. Rev. A, 90:062106, Dec 2014. URL: https://doi.org/10.1103/PhysRevA.90.062106.
https://doi.org/10.1103/PhysRevA.90.062106
[26] Alessandro Bisio, Giacomo Mauro D’Ariano, Paolo Perinotti, and Alessandro Tosini. Weyl, Dirac and Maxwell quantum cellular automata. Foundations of Physics, 45(10):1203–1221, Oct 2015. URL: https://doi.org/10.1007/s10701-015-9927-0.
https://doi.org/10.1007/s10701-015-9927-0
[27] Richard P. Feynman. Simulating physics with computers. International Journal of Theoretical Physics, 21(6):467–488, 1982. URL: https://doi.org/10.1007/BF02650179.
https://doi.org/10.1007/BF02650179
[28] Wim van Dam. Quantum Cellular Automata. PhD thesis, University of Nijmegen, 1996. URL: https://sites.cs.ucsb.edu/ vandam/qca.pdf.
https://sites.cs.ucsb.edu/~vandam/qca.pdf
[29] J. Watrous. On one-dimensional quantum cellular automata. In Proceedings of IEEE 36th Annual Foundations of Computer Science, pages 528–537, Oct 1995. URL: https://doi.org/10.1109/SFCS.1995.492583.
https://doi.org/10.1109/SFCS.1995.492583
[30] J Gruska. Quantum Computing. McGraw-Hill, 1999.
[31] B. Schumacher and R. F. Werner. Reversible quantum cellular automata, 2004. arXiv:quant-ph/0405174.
arXiv:quant-ph/0405174
[32] Pablo Arrighi, Vincent Nesme, and Reinhard Werner. Unitarity plus causality implies localizability. Journal of Computer and System Sciences, 77(2):372 – 378, 2011. Adaptivity in Heterogeneous Environments. URL: https://doi.org/10.1016/j.jcss.2010.05.004.
https://doi.org/10.1016/j.jcss.2010.05.004
[33] 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(2):419–454, Mar 2012. URL: https://doi.org/10.1007/s00220-012-1423-1.
https://doi.org/10.1007/s00220-012-1423-1
[34] Pablo Arrighi, Renan Fargetton, Vincent Nesme, and Eric Thierry. Applying causality principles to the axiomatization of probabilistic cellular automata. In Benedikt Löwe, Dag Normann, Ivan Soskov, and Alexandra Soskova, editors, Models of Computation in Context, pages 1–10, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/978-3-642-21875-0_1.
https://doi.org/10.1007/978-3-642-21875-0_1
[35] Sergey B. Bravyi and Alexei Yu. Kitaev. Fermionic quantum computation. Annals of Physics, 298(1):210 – 226, 2002. URL: https://doi.org/10.1006/aphy.2002.6254.
https://doi.org/10.1006/aphy.2002.6254
[36] G. M. D’Ariano, F. Manessi, P. Perinotti, and A. Tosini. Fermionic computation is non-local tomographic and violates monogamy of entanglement. EPL (Europhysics Letters), 107(2):20009, jul 2014. URL: https://doi.org/10.1209/0295-5075/107/20009.
https://doi.org/10.1209/0295-5075/107/20009
[37] Giacomo Mauro D’Ariano, Franco Manessi, Paolo Perinotti, and Alessandro Tosini. The feynman problem and fermionic entanglement: Fermionic theory versus qubit theory. International Journal of Modern Physics A, 29(17):1430025, 2014. URL: https://doi.org/10.1142/S0217751X14300257.
https://doi.org/10.1142/S0217751X14300257
[38] Y. Aharonov, L. Davidovich, and N. Zagury. Quantum random walks. Phys. Rev. A, 48:1687–1690, Aug 1993. URL: https://doi.org/10.1103/PhysRevA.48.1687.
https://doi.org/10.1103/PhysRevA.48.1687
[39] Dorit Aharonov, Andris Ambainis, Julia Kempe, and Umesh Vazirani. Quantum walks on graphs. In Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, STOC ’01, pages 50–59, New York, NY, USA, 2001. Association for Computing Machinery. URL: https://doi.org/10.1145/380752.380758.
https://doi.org/10.1145/380752.380758
[40] Peter L. Knight, Eugenio Roldán, and J. E. Sipe. Propagating quantum walks: The origin of interference structures. Journal of Modern Optics, 51(12):1761–1777, 2004. URL: https://doi.org/10.1080/09500340408232489.
https://doi.org/10.1080/09500340408232489
[41] Norio Konno. A new type of limit theorems for the one-dimensional quantum random walk. J. Math. Soc. Japan, 57(4):1179–1195, 10 2005. URL: https://doi.org/10.2969/jmsj/1150287309.
https://doi.org/10.2969/jmsj/1150287309
[42] Hilary A Carteret, Mourad E H Ismail, and Bruce Richmond. Three routes to the exact asymptotics for the one-dimensional quantum walk. Journal of Physics A: Mathematical and General, 36(33):8775–8795, aug 2003. URL: https://doi.org/10.1088/0305-4470/36/33/305.
https://doi.org/10.1088/0305-4470/36/33/305
[43] Andris Ambainis, Eric Bach, Ashwin Nayak, Ashvin Vishwanath, and John Watrous. One-dimensional quantum walks. In Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, STOC ’01, pages 37–49, New York, NY, USA, 2001. Association for Computing Machinery. URL: https://doi.org/10.1145/380752.380757.
https://doi.org/10.1145/380752.380757
[44] Alessandro Bisio, Giacomo Mauro D’Ariano, Paolo Perinotti, and Alessandro Tosini. Thirring quantum cellular automaton. Phys. Rev. A, 97:032132, Mar 2018. URL: https://doi.org/10.1103/PhysRevA.97.032132.
https://doi.org/10.1103/PhysRevA.97.032132
[45] Paolo Perinotti and Leopoldo Poggiali. Scalar fermionic cellular automata on finite cayley graphs. Phys. Rev. A, 98:052337, Nov 2018. URL: https://doi.org/10.1103/PhysRevA.98.052337.
https://doi.org/10.1103/PhysRevA.98.052337
[46] Giacomo Mauro D’Ariano and Paolo Perinotti. Quantum cellular automata and free quantum field theory. Frontiers of Physics, 12(1):120301, Sep 2016. URL: https://doi.org/10.1007/s11467-016-0616-z.
https://doi.org/10.1007/s11467-016-0616-z
[47] P. de la Harpe. Topics in Geometric Group Theory. Chicago Lectures in Mathematics. University of Chicago Press, 2000. URL: https://press.uchicago.edu/ucp/books/book/chicago/T/bo3641370.html.
https://press.uchicago.edu/ucp/books/book/chicago/T/bo3641370.html
[48] Shuichi Inokuchi and Yoshihiro Mizoguchi. Generalized partitioned quantum cellular automata and quantization of classical ca. Int. Journ. of Unconventional Computing, 1:149–160, 2005. arXiv:quant-ph/0312102.
arXiv:quant-ph/0312102
[49] J. von Neumann. On infinite direct products. Compositio Mathematica, 6:1–77, 1939. URL: http://www.numdam.org/item/CM_1939__6__1_0.
http://www.numdam.org/item/CM_1939__6__1_0
[50] F. J. Murray and J. v. Neumann. On rings of operators. Annals of Mathematics, 37(1):116–229, 1936. URL: https://doi.org/10.2307/1968693.
https://doi.org/10.2307/1968693
[51] Rainer J. Nagel. Order unit and base norm spaces. In A. Hartkämper and H. Neumann, editors, Foundations of Quantum Mechanics and Ordered Linear Spaces: Advanced Study Institute Marburg 1973, pages 23–29. Springer Berlin Heidelberg, Berlin, Heidelberg, 1974. URL: https://doi.org/10.1007/3-540-06725-6_4.
https://doi.org/10.1007/3-540-06725-6_4
[52] David Beckman, Daniel Gottesman, M. A. Nielsen, and John Preskill. Causal and localizable quantum operations. Phys. Rev. A, 64:052309, Oct 2001. URL: https://doi.org/10.1103/PhysRevA.64.052309.
https://doi.org/10.1103/PhysRevA.64.052309
[53] T Eggeling, D Schlingemann, and R. F Werner. Semicausal operations are semilocalizable. Europhysics Letters (EPL), 57(6):782–788, mar 2002. URL: https://doi.org/10.1209/epl/i2002-00579-4.
https://doi.org/10.1209/epl/i2002-00579-4
[54] Benjamin Schumacher and Michael D. Westmoreland. Locality and information transfer in quantum operations. Quantum Information Processing, 4(1):13–34, February 2005. URL: https://doi.org/10.1007/s11128-004-3193-y.
https://doi.org/10.1007/s11128-004-3193-y
[55] Jonathan Barrett, Robin Lorenz, and Ognyan Oreshkov. Quantum causal models. 2019. arXiv:1906.10726.
arXiv:1906.10726
[56] Pablo Arrighi, Nicolas Schabanel, and Guillaume Theyssier. Stochastic cellular automata: Correlations, decidability and simulations. Fundamenta Informaticae, 126:121–156, 2013. URL: https://doi.org/10.3233/FI-2013-875.
https://doi.org/10.3233/FI-2013-875
[57] Giacomo Mauro D’Ariano, Marco Erba, and Paolo Perinotti. Isotropic quantum walks on lattices and the weyl equation. Phys. Rev. A, 96:062101, Dec 2017. URL: https://doi.org/10.1103/PhysRevA.96.062101.
https://doi.org/10.1103/PhysRevA.96.062101
[58] Lucien Hardy and William K. Wootters. Limited holism and real-vector-space quantum theory. Foundations of Physics, 42(3):454–473, 2012. URL: https://doi.org/10.1007/s10701-011-9616-6.
https://doi.org/10.1007/s10701-011-9616-6
[59] Karl-Peter Hadeler and Johannes Müller. Introduction. In Cellular Automata: Analysis and Applications, pages 1–17. Springer International Publishing, Cham, 2017. URL: https://doi.org/10.1007/978-3-319-53043-7_1.
https://doi.org/10.1007/978-3-319-53043-7_1
[60] Pablo Arrighi and Vincent Nesme. The block neighborhood. In Jarkko Kari, editor, Second Symposium on Cellular Automata “Journeés Automates Cellulaires”, JAC 2010, Turku, Finland, December 15-17, 2010. Proceedings, pages 43–53. Turku Center for Computer Science, 2010. URL: https://hal.archives-ouvertes.fr/hal-00542488.
https://hal.archives-ouvertes.fr/hal-00542488
[61] Pablo Arrighi, Vincent Nesme, and Reinhard F. Werner. Bounds on the speedup in quantum signaling. Phys. Rev. A, 95:012331, Jan 2017. URL: https://doi.org/10.1103/PhysRevA.95.012331.
https://doi.org/10.1103/PhysRevA.95.012331
[62] Michael Freedman and Matthew B. Hastings. Classification of quantum cellular automata. Communications in Mathematical Physics, 376(2):1171–1222, 2020. URL: https://doi.org/10.1007/s00220-020-03735-y.
https://doi.org/10.1007/s00220-020-03735-y
[63] Michael Freedman, Jeongwan Haah, and Matthew B Hastings. The group structure of quantum cellular automata. 2019. arXiv:1910.07998.
arXiv:1910.07998
[64] Terry Farrelly. A review of quantum cellular automata, 2019. arXiv:1904.13318.
arXiv:1904.13318
[65] P. Arrighi. An overview of quantum cellular automata. Natural Computing, 18(4):885–899, 2019. URL: https://doi.org/10.1007/s11047-019-09762-6.
https://doi.org/10.1007/s11047-019-09762-6
[66] Alessandro Bisio, Giacomo D’Ariano, Nicola Mosco, Paolo Perinotti, and Alessandro Tosini. Solutions of a two-particle interacting quantum walk. Entropy, 20(6):435, Jun 2018. URL: https://doi.org/10.3390/e20060435.
https://doi.org/10.3390/e20060435
Cited by
[1] Robin Lorenz and Jonathan Barrett, “Causal and compositional structure of unitary transformations”, arXiv:2001.07774.
The above citations are from SAO/NASA ADS (last updated successfully 2020-07-09 12:48:12). The list may be incomplete as not all publishers provide suitable and complete citation data.
Could not fetch Crossref cited-by data during last attempt 2020-07-09 12:48:10: Could not fetch cited-by data for 10.22331/q-2020-07-09-294 from Crossref. This is normal if the DOI was registered recently.
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.
Source: https://quantum-journal.org/papers/q-2020-07-09-294/
