Document Open Access Logo

Universal Gauge-Invariant Cellular Automata

Authors Pablo Arrighi , Marin Costes , Nathanaël Eon

PDF

File

Thumbnail PDF
PDF
LIPIcs.MFCS.2021.9.pdf
  • Filesize: 0.7 MB
  • 14 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Models of computation
Keywords
  • Cellular automata
  • Gauge-invariance
  • Universality

Metrics

Abstract

Gauge symmetries play a fundamental role in Physics, as they provide a mathematical justification for the fundamental forces. Usually, one starts from a non-interactive theory which governs "matter", and features a global symmetry. One then extends the theory so as make the global symmetry into a local one (a.k.a gauge-invariance). We formalise a discrete counterpart of this process, known as gauge extension, within the Computer Science framework of Cellular Automata (CA). We prove that the CA which admit a relative gauge extension are exactly the globally symmetric ones (a.k.a the colour-blind). We prove that any CA admits a non-relative gauge extension. Both constructions yield universal gauge-invariant CA, but the latter allows for a first example where the gauge extension mediates interactions within the initial CA.

Cite As Get BibTex

Pablo Arrighi, Marin Costes, and Nathanaël Eon. Universal Gauge-Invariant Cellular Automata. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.MFCS.2021.9

Author Details

Pablo Arrighi
  • Université Paris-Saclay, CNRS, LMF, 91190 Gif-sur-Yvette, France
  • IXXI, Lyon, France
Marin Costes
  • ENS Paris-Saclay, CNRS, LMF, 91190 Gif-sur-Yvette, France
Nathanaël Eon
  • Aix-Marseille Université, Université de Toulon, CNRS, LIS, Marseille, France

Funding

This publication was made possible through the support of the ID# 61466 grant from the John Templeton Foundation, as part of the “The Quantum Information Structure of Spacetime (QISS)” Project (qiss.fr). The opinions expressed in this publication are those of the author(s) and do not necessarily reflect the views of the John Templeton Foundation.

Acknowledgements

The authors would like to thank Guillaume Theyssier for asking us the question whether any CA admits a gauge extension.

References

  1. Pablo Arrighi, Cédric Bény, and Terry Farrelly. A quantum cellular automaton for one-dimensional qed. Local proceedings of AQIS 2019. Quantum Information Processing, 19:88, 2020. arXiv preprint. URL: http://arxiv.org/abs/1903.07007.
  2. Pablo Arrighi, Giuseppe Di Molfetta, and Nathanaël Eon. A gauge-invariant reversible cellular automaton. In International Workshop on Cellular Automata and Discrete Complex Systems, pages 1-12. Springer, 2018. Google Scholar
  3. Pablo Arrighi, Giuseppe Di Molfetta, and Nathanaël Eon. Non-abelian gauge-invariant cellular automata. In International Conference on Theory and Practice of Natural Computing, pages 211-221. Springer, 2019. Google Scholar
  4. Pablo Arrighi, Giuseppe Di Molfetta, and Nathanaël Eon. Gauge-invariance in cellular automata. arXiv preprint, 2020. URL: http://arxiv.org/abs/2004.03656.
  5. Pablo Arrighi, Nicolas Durbec, and Aurélien Emmanuel. Reversibility vs local creation/destruction. In Proceedings of RC 2019, LLNCS, volume 11497, pages 51-66. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-21500-2_4.
  6. Shailesh Chandrasekharan and U-J Wiese. Quantum link models: A discrete approach to gauge theories. Nuclear Physics B, 492(1-2):455-471, 1997. Google Scholar
  7. Péter Gács. Reliable computation with cellular automata. Journal of Computer and System Sciences, 32(1):15-78, 1986. Google Scholar
  8. Péter Gács. Reliable cellular automata with self-organization. Journal of Statistical Physics, 103(1):45-267, 2001. Google Scholar
  9. IM Georgescu, Sahel Ashhab, and Franco Nori. Quantum simulation. Reviews of Modern Physics, 86(1):153, 2014. Google Scholar
  10. Pierre Guillon, Pierre-Etienne Meunier, and Guillaume Theyssier. Clandestine Simulations in Cellular Automata. 18 pages, 2010. URL: https://hal.archives-ouvertes.fr/hal-00521624.
  11. Masateru Harao and Shoichi Noguchi. Fault tolerant cellular automata. Journal of computer and system sciences, 11(2):171-185, 1975. Google Scholar
  12. W Keith Hastings. Monte carlo sampling methods using markov chains and their applications. Biometrika, 57(1):97-109, 1970. Google Scholar
  13. A Yu Kitaev. Fault-tolerant quantum computation by anyons. Annals of Physics, 303(1):2-30, 2003. Google Scholar
  14. Chetan Nayak, Steven H Simon, Ady Stern, Michael Freedman, and Sankar Das Sarma. Non-abelian anyons and topological quantum computation. Reviews of Modern Physics, 80(3):1083, 2008. Google Scholar
  15. Simone Notarnicola, Mario Collura, and Simone Montangero. Real-time-dynamics quantum simulation of (1+ 1)-dimensional lattice qed with rydberg atoms. Physical Review Research, 2(1):013288, 2020. Google Scholar
  16. Ville Salo and Ilkka Törmä. Color blind cellular automata. In International Workshop on Cellular Automata and Discrete Complex Systems, pages 139-154. Springer, 2013. Google Scholar
  17. Pietro Silvi, Enrique Rico, Tommaso Calarco, and Simone Montangero. Lattice gauge tensor networks. New Journal of Physics, 16(10):103015, October 2014. URL: https://doi.org/10.1088/1367-2630/16/10/103015.
  18. A. Toom. Cellular automata with errors: Problems for students of probability. Topics in Contemporary Probability and Its Applications, pages 117-157, 1995. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact