quantum cellular automaton

In the context of models of computation or of physical systems, quantum cellular automaton refers to the merger of elements of both (1) the study of cellular automata in conventional computer science and (2) the study of quantum information processing. In particular, the following are features of models of quantum cellular automata:

• The computation is considered to come about by parallel operation of multiple computing devices, or cells. The cells are usually taken to be identical, finite-dimensional quantum systems (e.g. each cell is a qubit).
• Each cell has a neighborhood of other cells. Altogether these form a network of cells, which is usually taken to be regular (e.g. the cells are arranged as a lattice with or without periodic boundary conditions).
• The evolution of all of the cells has a number of physics-like symmetries. Locality is one: the next state of a cell depends only on its current state and that of its neighbours. Homogeneity is another: the evolution acts the same everywhere, and is independent of time.
• The state space of the cells, and the operations performed on them, should be motivated by principles of quantum mechanics.

Another feature that is often considered important for a model of quantum cellular automata is that it should be universal for quantum computation (i.e. that it can efficiently simulate quantum Turing machines,{{citation

| last = Watrous | first = John | authorlink = John Watrous (computer scientist)

| contribution = On one-dimensional quantum cellular automata

| doi = 10.1109/SFCS.1995.492583

| location = Los Alamitos, CA

| mr = 1619103

| pages = 528–537

| publisher = IEEE Comput. Soc. Press

| title = Proc. 36th Annual Symposium on Foundations of Computer Science (Milwaukee, WI, 1995)

| year = 1995| title-link = Symposium on Foundations of Computer Science | isbn = 0-8186-7183-1 | s2cid = 7441203 }}.C. Pérez-Delgado and D. Cheung, "Local Unitary Quantum Cellular Automata",

Phys. Rev. A 76, 032320, 2007. See also [http://www.arxiv.org/abs/0709.0006 arXiv:0709.0006 (quant-ph)] some arbitrary quantum circuit

D.J. Shepherd, T. Franz, R.F. Werner: Universally programmable Quantum Cellular Automaton. Phys. Rev. Lett. 97, 020502 (2006)

or simply all other quantum cellular automataP. Arrighi, R. Fargetton, Z. Wang, Intrinsically universal one-dimensional quantum cellular automata in two flavours, Fundamenta Informaticae Vol.91, No.2, pp.197-230, (2009). See also [https://arxiv.org/abs/0704.3961 (quant-ph)]P. Arrighi, J. Grattage, A quantum Game of Life, Proceedings of JAC 2010, Turku, December 2010. TUCS Lecture Notes 13, 31-42, (2010). See also [https://arxiv.org/abs/arXiv:1010.3120 (quant-ph)] and [http://www.grattage.co.uk/jon/3DQCA (Companion Website)]).

Models which have been proposed recently impose further conditions, e.g. that quantum cellular automata should be reversible and/or locally unitary, and have an easily determined global transition function from the rule for updating individual cells. Recent results show that these properties can be derived axiomatically, from the symmetries of the global evolution.B. Schumacher and R. Werner, "Reversible quantum cellular automata", [http://www.arxiv.org/abs/quant-ph/0405174 quant-ph/0405174]Pablo Arrighi, Vincent Nesme, Reinhard Werner, One-dimensional quantum cellular automata over finite, unbounded configurations. See also [https://arxiv.org/abs/0711.3517 (quant-ph)]Pablo Arrighi, Vincent Nesme, Reinhard Werner, N-dimensional quantum cellular automata. See also [https://arxiv.org/abs/0711.3975 (quant-ph)]

In 1982, Richard Feynman suggested an initial approach to quantizing a model of cellular automata.R. Feynman, "Simulating physics with computers", Int. J. Theor. Phys. 21, 1982: pp. 467–488. In 1985, David Deutsch presented a formal development of the subject.D. Deutsch, "Quantum theory, the Church-Turing principle and the universal quantum computer" Proceedings of the Royal Society of London A 400 (1985), pp. 97–117. Later, Gerhard Grössing and Anton Zeilinger introduced the term "quantum cellular automata" to refer to a model they defined in 1988,G. Grossing and A. Zeilinger, "Quantum cellular automata", Complex Systems 2 (2), 1988: pp. 197–208 and 611–623. although their model had very little in common with the concepts developed by Deutsch and so has not been developed significantly as a model of computation.

The first formal model of quantum cellular automata to be researched in depth was that introduced by John Watrous. This model was developed further by Wim van Dam,W. van Dam, "Quantum cellular automata", Master Thesis, Computer Science Nijmegen, Summer 1996. as well as Christoph Dürr, Huong LêThanh, and Miklos Santha,C. Dürr and M. Santha, "A decision procedure for unitary linear quantum cellular automata", [http://www.arxiv.org/abs/quant-ph/9604007 quant-ph/9604007 ].C. Dürr, H. LêTanh, M. Santha, "A decision procedure for well-formed linear quantum cellular automata", Rand. Struct. Algorithms 11, 1997: pp. 381–394. See also [http://www.arxiv.org/abs/cs.DS/9906024 cs.DS/9906024]. Jozef Gruska.J. Gruska, "Quantum Computing", McGraw-Hill, Cambridge 1999: Section 4.3. and Pablo Arrighi.Pablo Arrighi, An algebraic study of unitary one dimensional quantum cellular automata, Proceedings of MFCS 2006, LNCS 4162, (2006), pp122-133. See also [https://arxiv.org/abs/quant-ph/0512040 quant-ph/0512040] However it was later realised that this definition was too loose, in the sense that some instances of it allow superluminal signalling. A second wave of models includes those of Susanne Richter and Reinhard Werner,S. Richter and R.F. Werner, "Ergodicity of quantum cellular automata", J. Stat. Phys. 82, 1996: pp. 963–998. See also [http://www.arxiv.org/abs/cond-mat/9504001 cond-mat/9504001] of Benjamin Schumacher and Reinhard Werner, of Carlos Pérez-Delgado and Donny Cheung, and of Pablo Arrighi, Vincent Nesme and Reinhard Werner. These are all closely related, and do not suffer any such locality issue. In the end one can say that they all agree to picture quantum cellular automata as just some large quantum circuit, infinitely repeating across time and space. Recent reviews of the topic are available here.P. Arrighi, An overview of quantum cellular automata, [https://arxiv.org/abs/1904.12956 arXiv:1904.12956]Terry Farrelly, A review of Quantum Cellular Automata [https://arxiv.org/abs/1904.13318 arXiv:1904.13318]

Models of quantum cellular automata have been proposed by David Meyer,D. Meyer, "From quantum cellular automata to quantum lattice gases", Journal of Statistical Physics 85, 1996: pp. 551–574. See also [http://www.arxiv.org/abs/quant-ph/9604003 quant-ph/9604003].D. Meyer, "On the absence of homogeneous scalar unitary cellular automata'", Physics Letters A 223, 1996: pp. 337–340. See also [http://www.arxiv.org/abs/quant-ph/9604011 quant-ph/9604011]. Bruce Boghosian and Washington Taylor,B. Boghosian and W. Taylor, "Quantum lattice-gas model for the many-particle Schrödinger equation in d dimensions", Physical Review E 57, 1998: pp. 54–66. and Peter Love and Bruce BoghosianP. Love and B. Boghosian, "From Dirac to Diffusion: Decoherence in Quantum Lattice Gases", Quantum Information Processing 4, 2005, pp. 335–354. as a means of simulating quantum lattice gases, motivated by the use of "classical" cellular automata to model classical physical phenomena such as gas dispersion.B. Chophard and M. Droz, "Cellular Automata modeling of Physical Systems", Cambridge University Press, 1998. Criteria determining when a quantum cellular automaton (QCA) can be described as quantum lattice gas automaton (QLGA) were given by Asif Shakeel and Peter Love.{{Cite journal|title = When is a quantum cellular automaton (QCA) a quantum lattice gas automaton (QLGA)?|journal = Journal of Mathematical Physics|date = 2013-09-01|issn = 0022-2488|pages = 092203|volume = 54|issue = 9|doi = 10.1063/1.4821640|first1 = Asif|last1 = Shakeel|first2 = Peter J.|last2 = Love|arxiv = 1209.5367 |bibcode = 2013JMP....54i2203S |s2cid = 2351651}}

A proposal for implementing classical cellular automata by systems designed with quantum dots has been proposed under the name "quantum cellular automata" by Doug Tougaw and Craig Lent,P. Tougaw, C. Lent, "Logical devices implemented using quantum cellular automata", J. Appl. Phys. 75, 1994: pp. 1818–1825 as a replacement for classical computation using CMOS technology. In order to better differentiate between this proposal and models of cellular automata which perform quantum computation, many authors working on this subject now refer to this as a quantum dot cellular automaton.

• {{annotated link|Quantum finite automata}}
• {{annotated link|Quantum Hall effect}}

{{reflist}}

{{Quantum mechanics topics}}

{{Richard Feynman|state=collapsed}}

Category:Cellular automata

Category:Quantum information science

Category:Richard Feynman