Intrinsically Universal One-dimensional Quantum Cellular Automata in Two Flavours

• Autorzy: Arrighi P. , Fargetton R. , Wang Z.
• Języki publikacji: EN

Abstrakty

EN

We give a one-dimensional quantum cellular automaton (QCA) capable of simulating all others. By this we mean that the initial configuration and the local transition rule of any onedimensional QCA can be encoded within the initial configuration of the universal QCA. Several steps of the universal QCA will then correspond to one step of the simulated QCA. The simulation preserves the topology in the sense that each cell of the simulated QCA is encoded as a group of adjacent cells in the universal QCA. The encoding is linear and hence does not carry any of the cost of the computation. We do this in two flavours: a weak one which requires an infinite but periodic initial configuration and a strong one which needs only a finite initial configuration.

Słowa kluczowe

EN

quantum cellular automata; intrinsic universality; quantum computation

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 91, nr 2
• Strony: 197--230
• Opis fizyczny: bibliogr. 28 poz., rys., tab., wykr.

Twórcy

autor

Arrighi P.

autor

Fargetton R.

autor

Wang Z.

• University of Grenoble LIG, 46 avenue Felix Viallet, 38000 Grenoble, France,

Bibliografia

• [1] J. Albert, K. Culik, A simple universal cellular automaton and its one-way totalistic version, Complex Systems, 1, 1-16, (1987).
• [2] P. Arrighi, An algebraic study of one-dimensional quantum cellular automata, Proceedings of MFCS 2006, LNCS 4162, 122-133, (2006).
• [3] P. Arrighi, V. Nesme, R. Werner, Quantum cellular automata upon finite, unbounded configurations, LATA'08, Proceedings to be published in LNCS. Pre-print arXiv:0711.3517.
• [4] Pablo Arrighi, Vincent Nesme, Reinhard Werner, N-dimensional quantum cellular automata, Pre-print arXiv:0711.3975.
• [5] R. B. Banks, Universality in cellular automata, Symposium on Switching and Automata Theory, (Santa Monica, California, 1970), IEEE, 194-215, (1970).
• [6] P. Boykin, T. Mor, M. Pulver, V. Roychowdhury, F. Vatan, On universal and fault-tolerant quantum computing, arxiv:quant-ph/9906054
• [7] D. Cheung, C. A. Perez-Delgado, Local Unitary Quantum Cellular Automata, arXiv:/0709.0006.
• [8] M. Delorme, An introduction to cellular automata, in 'Cellular Automata: A Parallel Model', Kluwer, (1999).
• [9] J. Durand-Lose, Reversible Cellular Automaton Able to Simulate Any Other Reversible One Using Partitioning Automata, Proc. of LATIN '95, LNCS 911, 230-244, (1995).
• [10] J. Durand-Lose, Intrinsic universality of a 1-dimensional reversible cellular automaton, STACS 97, LNCS 1200, 439450, (1997).
• [11] J. Durand-Lose, Representing Reversible Cellular Automata with Reversible Block Cellular Automata, DMCCG' 01, Discrete Mathematics and Theoretical Computer Science Proceedings, AA, 145-154, (2001).
• [12] C. Dürr, H. LêThanh, M. Santha, A decision procedure for well formed quantum cellular automata, Random Structures and Algorithms, 11, 381-394, (1997).
• [13] C. Dürr, M. Santha, A decision procedure for unitary quantum linear cellular automata, SIAM J. of Computing, 31(4), 1076-1089, (2002).
• [14] R. P. Feynman, Quantum mechanical computers, Found. Phys. 16, 507-531, (1986).
• [15] D. Meyer, Unitarity in one dimensional nonlinear quantum cellular automata, arXiv:quant-ph/9605023, (1995).
• [16] M.A. Nielsen, I.L. Chuang, Quantum computation and quantum information, Cambridge University Press, 194-195, (2000).
• [17] N. Ollinger, Automates cellulaires: structures., Ph.D. Thesis at ENS-Lyon, (2002).
• [18] N. Ollinger, Universalities in Cellular Automata: A short survey., JAC 2008.
• [19] J. Kari, Representation of Reversible Cellular Automata with Block Permutations, Theory of Computing Systems, 29, 47-61, (1996).
• [20] J. Kari, On the Circuit Depth of Structurally Reversible Cellular Automata, Fundamenta Informaticae, 38(1-2), 93-107, (1999).
• [21] R. Raussendorf, Quantum cellular automaton for universal quantum computation, Phys. Rev. A, 72, 022301, (2005).
• [22] B. Schumacher, R. F. Werner, Reversible quantum cellular automata, arXiv:quant-ph/0405174.
• [23] D. J. Shepherd, T. Franz, R. F. Werner, Universally programmable quantum cellular automata, Phys. Rev. Lett., 97, 020502 (2006).
• [24] T. Toffoli, Computation and construction universality of reversible cellular automata, J. of Computer and System Sciences, 15(2), (1977).
• [25] T. Toffoli, N. Margolus, Cellular Automata Machine - A New Environment for Modelling, MIT Press, Cambridge MA, (1987).
• [26] T. Toffoli, N. Margolus, Invertible Cellular Automata : A Review, Physica D, 45, 229-253, (1990).
• [27] W. Van Dam, Quantum Cellular Automata, Master thesis, Department of Mathematics and Computer Science, University of Nijmegen, The Netherlands, (1996).
• [28] J. Watrous, On one-dimensional quantum cellular automata, Complex Systems 5(1), 19-30, (1991).