A Simple n-Dimensional Intrinsically Universal Quantum Cellular Automaton

1. Albert, J., Culik, K.: A simple universal cellular automaton and its one-way and totalistic version. Complex Systems 1, 1–16 (1987)

   MATH  MathSciNet  Google Scholar 

2. Arrighi, P.: Algebraic characterizations of unitary linear quantum cellular automata. In: Královič, R., Urzyczyn, P. (eds.) MFCS 2006. LNCS, vol. 4162, pp. 122–133. Springer, Heidelberg (2006)

   Chapter  Google Scholar 

3. Arrighi, P., Fargetton, R.: Intrinsically universal one-dimensional quantum cellular automata. In: Proceedings of the Development of Computational Models workshop, DCM ’07 (2007)

   Google Scholar 

4. Arrighi, P., Fargetton, R., Wang, Z.: Intrinsically universal one-dimensional quantum cellular automata in two flavours. Fundamenta Informaticae 21, 1001–1035 (2009)

   MathSciNet  Google Scholar 

5. Arrighi, P., Grattage, J.: Intrinsically universal n-dimensional quantum cellular automata. Extended version of this paper. ArXiv preprint: arXiv:0907.3827 (2009)

   Google Scholar 

6. Arrighi, P., Grattage, J.: Partitioned quantum cellular automata are intrinsically universal (2009) (submitted)

   Google Scholar 

7. Arrighi, P., Grattage, J.: Two minimal n-dimensional intrinsically universal quantum cellular automata (2009) (manuscript)

   Google Scholar 

8. Arrighi, P., Nesme, V., Werner, R.: Unitarity plus causality implies localizability. Quantum Information Processing (QIP) 2010, ArXiv preprint: arXiv:0711.3975 (2007)

   Google Scholar 

9. Arrighi, P., Nesme, V., Werner, R.F.: Quantum cellular automata over finite, unbounded configurations. In: Martín-Vide, C., Otto, F., Fernau, H. (eds.) LATA 2008. LNCS, vol. 5196, pp. 64–75. Springer, Heidelberg (2008)

   Chapter  Google Scholar 

10. Banks, E.R.: Universality in cellular automata. In: Proceedings of the 11th Annual Symposium on Switching and Automata Theory (SWAT ’70), Washington, DC, USA, pp. 194–215. IEEE Computer Society, Los Alamitos (1970)

    Chapter  Google Scholar 

11. Brennen, G.K., Williams, J.E.: Entanglement dynamics in one-dimensional quantum cellular automata. Phys. Rev. A 68(4), 042311 (2003)

    Article  MathSciNet  Google Scholar 

12. Dür, W., Vidal, G., Cirac, J.I.: Three qubits can be entangled in two inequivalent ways. Phys. Rev. A 62, 062314 (2000)

    Article  Google Scholar 

13. Durand, B., Roka, Z.: The Game of Life: universality revisited, Research Report 98-01. Technical report, Ecole Normale Suprieure de Lyon (1998)

    Google Scholar 

14. Durand-Lose, J.O.: Reversible cellular automaton able to simulate any other reversible one using partitioning automata. In: Baeza-Yates, R., Poblete, P.V., Goles, E. (eds.) LATIN 1995. LNCS, vol. 911, pp. 230–244. Springer, Heidelberg (1995)

    Google Scholar 

15. Durand-Lose, J.O.: Intrinsic universality of a 1-dimensional reversible cellular automaton. In: Reischuk, R., Morvan, M. (eds.) STACS 1997. LNCS, vol. 1200, p. 439. Springer, Heidelberg (1997)

    Chapter  Google Scholar 

16. Durr, C., Le Thanh, H., Santha, M.: A decision procedure for well-formed linear quantum cellular automata. In: Puech, C., Reischuk, R. (eds.) STACS 1996. LNCS, vol. 1046, pp. 281–292. Springer, Heidelberg (1996)

    Google Scholar 

17. Feynman, R.P.: Quantum mechanical computers. Foundations of Physics (Historical Archive) 16(6), 507–531 (1986)

    Article  MathSciNet  Google Scholar 

18. Lloyd, S.: A theory of quantum gravity based on quantum computation. ArXiv preprint: quant-ph/0501135 (2005)

    Google Scholar 

19. Margolus, N.: Physics-like models of computation. Physica D: Nonlinear Phenomena 10(1-2) (1984)

    Google Scholar 

20. Margolus, N.: Parallel quantum computation. In: Complexity, Entropy, and the Physics of Information: The Proceedings of the 1988 Workshop on Complexity, Entropy, and the Physics of Information, Santa Fe, New Mexico, Perseus Books, May-June 1989, p. 273 (1990)

    Google Scholar 

21. Mazoyer, J., Rapaport, I.: Inducing an order on cellular automata by a grouping operation. In: Meinel, C., Morvan, M. (eds.) STACS 1998. LNCS, vol. 1373, pp. 116–127. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

22. Morita, K.: Reversible simulation of one-dimensional irreversible cellular automata. Theoretical Computer Science 148(1), 157–163 (1995)

    Article  MATH  MathSciNet  Google Scholar 

23. Morita, K., Harao, M.: Computation universality of one-dimensional reversible (injective) cellular automata. IEICE Trans. Inf. & Syst., E 72, 758–762 (1989)

    Google Scholar 

24. Morita, K., Ueno, S.: Computation-universal models of two-dimensional 16-state reversible cellular automata. IEICE Trans. Inf. & Syst., E 75, 141–147 (1992)

    Google Scholar 

25. Nagaj, D., Wocjan, P.: Hamiltonian Quantum Cellular Automata in 1D. ArXiv preprint: arXiv:0802.0886 (2008)

    Google Scholar 

26. Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (October 2000)

    MATH  Google Scholar 

27. Ollinger, N.: Universalities in cellular automata a (short) survey. In: Durand, B. (ed.) Proceedings of First Symposium on Cellular Automata Journées Automates Cellulaires (JAC 2008), Uzès, France, April 21-25, pp. 102–118. MCCME Publishing House, Moscow (2008)

    Google Scholar 

28. Ollinger, N., Richard, G.: A Particular Universal Cellular Automaton. In: Neary, T., Woods, D., Seda, A.K., Murphy, N. (eds.) CSP, pp. 267–278. Cork University Press (2008)

    Google Scholar 

29. Paz, J.P., Zurek, W.H.: Environment-induced decoherence and the transition from quantum to classical. Lecture Notes in Physics, pp. 77–140 (2002)

    Google Scholar 

30. Pérez-Delgado, C., Cheung, D.: Local unitary quantum cellular automata. Physical Review A 76(3), 32320 (2007)

    Article  Google Scholar 

31. Raussendorf, R.: Quantum cellular automaton for universal quantum computation. Phys. Rev. A 72(022301) (2005)

    Google Scholar 

32. Schumacher, B., Werner, R.: Reversible quantum cellular automata. ArXiv pre-print quant-ph/0405174 (2004)

    Google Scholar 

33. Shepherd, D.J., Franz, T., Werner, R.F.: A universally programmable quantum cellular automata. Phys. Rev. Lett. 97(020502) (2006)

    Google Scholar 

34. Theyssier, G.: Captive cellular automata. In: Fiala, J., Koubek, V., Kratochvíl, J. (eds.) MFCS 2004. LNCS, vol. 3153, pp. 427–438. Springer, Heidelberg (2004)

    Google Scholar 

35. Toffoli, T.: Computation and construction universality of reversible cellular automata. J. of Computer and System Sciences 15(2) (1977)

    Google Scholar 

36. Van Dam, W.: Quantum cellular automata. Masters thesis, University of Nijmegen, The Netherlands (1996)

    Google Scholar 

37. Vollbrecht, K.G.H., Cirac, J.I.: Reversible universal quantum computation within translation-invariant systems. New J. Phys. Rev. A 73, 012324 (2004)

    Article  Google Scholar 

38. von Neumann, J.: Theory of Self-Reproducing Automata. University of Illinois Press, Champaign (1966)

    Google Scholar 

39. Watrous, J.: On one-dimensional quantum cellular automata. Complex Systems 5(1), 19–30 (1991)

    MathSciNet  Google Scholar 

40. Watrous, J.: On one-dimensional quantum cellular automata. In: Proceedings of the 36th IEEE Symposium on Foundations of Computer Science, Washington, DC, USA, pp. 528–537. IEEE Computer Society, Los Alamitos (1995)

    Google Scholar 

Download references