Quantum cellular automaton

Usage of the term

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, some arbitrary quantum circuit or simply all other quantum cellular automata).

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.

Models

Early proposals

In 1982, Richard Feynman suggested an initial approach to quantizing a model of cellular automata. In 1985, David Deutsch presented a formal development of the subject. Later, Gerhard Grössing and Anton Zeilinger introduced the term "quantum cellular automata" to refer to a model they defined in 1988, 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.

Models of universal quantum computation

The first formal model of quantum cellular automata to be researched in depth was that introduced by John Watrous. as well as Christoph Dürr, Huong LêThanh, and Miklos Santha, Jozef Gruska. and Pablo Arrighi. However it was later realised that this definition was too loose, in the sense that some instances of it allow superluminal signalling. of Benjamin Schumacher and Reinhard Werner,

Models of physical systems

Models of quantum cellular automata have been proposed by David Meyer, Bruce Boghosian and Washington Taylor, and Peter Love and Bruce Boghosian 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. 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.

Quantum dot cellular automata

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,{{cite journal | last1=Tougaw | first1=P. Douglas | last2=Lent | first2=Craig S. | title=Logical devices implemented using quantum cellular automata | journal=Journal of Applied Physics | date=1994 | volume=75 | issue=3 | pages=1818–1825 | doi=10.1063/1.356375

Models of Particle Physics

Many QCAs that simulate Quantum Field Theories in the continuum limit have been devised. The simplest one is the Dirac QCA that, for low-momentum and low mass regime, behaves like a Dirac particle. Some other QCAs that simulate Quantum Electrodynamics have also been constructed. However, there remain some problems with these modes. For instance, it is not clear how to define a free Dirac vacuum in such models that is stable.

References

References

1. Watrous, John. (1995). "Proceedings of IEEE 36th Annual Foundations of Computer Science".
2. (2007). "Local unitary quantum cellular automata". Physical Review A.
3. (2006). "Universally Programmable Quantum Cellular Automaton". Physical Review Letters.
4. (2007). "Intrinsically universal one-dimensional quantum cellular automata in two flavours".
5. (2010). "A Quantum Game of Life".
6. (2004). "Reversible quantum cellular automata".
7. (2007). "One-dimensional quantum cellular automata over finite, unbounded configurations".
8. (2007). "Unitarity plus causality implies localizability".
9. (1982). "Simulating physics with computers". International Journal of Theoretical Physics.
10. (1985). "Quantum theory, the Church–Turing principle and the universal quantum computer". Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences.
11. (1988). "Quantum cellular automata". Complex Systems.
12. This model was developed further by Wim van Dam,W. van Dam, "Quantum cellular automata", Master Thesis, Computer Science Nijmegen, Summer 1996.
13. (1996). "A decision procedure for unitary linear quantum cellular automata".
14. http://www.arxiv.org/abs/cs.DS/9906024
15. J. Gruska, "Quantum Computing", McGraw-Hill, Cambridge 1999: Section 4.3.
16. (2005). "An algebraic study of unitary one dimensional quantum cellular automata".
17. (1996). "Ergodicity of quantum cellular automata". Journal of Statistical Physics.
18. (2020). "A review of Quantum Cellular Automata". Quantum.
19. (1996). "From quantum cellular automata to quantum lattice gases". Journal of Statistical Physics.
20. (1996). "On the absence of homogeneous scalar unitary cellular automata". Physics Letters A.
21. (1998). "Quantum lattice-gas model for the many-particle Schrödinger equation in d dimensions". Physical Review E.
22. (2005). "From Dirac to Diffusion: Decoherence in Quantum Lattice Gases". Quantum Information Processing.
23. B. Chophard and M. Droz, "Cellular Automata modeling of Physical Systems", Cambridge University Press, 1998.
24. (2013-09-01). "When is a quantum cellular automaton (QCA) a quantum lattice gas automaton (QLGA)?". Journal of Mathematical Physics.
25. (2014-06-16). "Discrete spacetime and relativistic quantum particles". Physical Review A.
26. (2020). "A quantum cellular automaton for one-dimensional QED". Quantum Information Processing.
27. (2024). "The Dirac Vacuum in Discrete Spacetime".