Quantum cellular automata
Encyclopedia
Quantum Cellular Automata (QCA) refers to models of quantum computation, which have been devised in analogy to conventional models of cellular automata introduced by von Neumann. It may also refer to quantum dot cellular automata, which is a proposed physical implementation of "classical" cellular automata by exploiting quantum mechanical phenomena.
and (2) the study of quantum information processing. In particular, the following are features of models of quantum cellular automata:
One 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 local 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.
suggested an initial approach to quantizing a model of cellular automata Gerhard Grössing and Anton Zeilinger
introduced the term "quantum cellular automata" to refer to a model they defined in 1988: however, their model has very little in common with the concepts developed in quantum computation after David Deutsch's formal development of that subject from 1985, and so has not been developed significantly as a model of computation.
. This model was developed further by Wim van Dam, 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. A second wave of models includes those of Susanne Richter and Reinhard Werner, 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.
and Craig Lent, 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
.
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 scienceComputer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
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 qubitQubitIn quantum computing, a qubit or quantum bit is a unit of quantum information—the quantum analogue of the classical bit—with additional dimensions associated to the quantum properties of a physical atom....
); - 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.
One 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
Quantum circuit
In quantum information theory, a quantum circuit is a model for quantum computation in which a computation is a sequence of quantum gates, which are reversible transformations on a quantum mechanical analog of an n-bit register...
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 local 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.
Early proposals
Richard FeynmanRichard Feynman
Richard Phillips Feynman was an American physicist known for his work in the path integral formulation of quantum mechanics, the theory of quantum electrodynamics and the physics of the superfluidity of supercooled liquid helium, as well as in particle physics...
suggested an initial approach to quantizing a model of cellular automata Gerhard Grössing and Anton Zeilinger
Anton Zeilinger
Anton Zeilinger is an Austrian quantum physicist. He is currently professor of physics at the University of Vienna, previously University of Innsbruck. He is also the director of the Vienna branch of the Institute for Quantum Optics and Quantum Information IQOQI at the Austrian Academy of Sciences...
introduced the term "quantum cellular automata" to refer to a model they defined in 1988: however, their model has very little in common with the concepts developed in quantum computation after David Deutsch's formal development of that subject from 1985, 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 WatrousJohn Watrous (computer scientist)
John Harrison Watrous is an associate professor of computer science at the David R. Cheriton School of Computer Science at the University of Waterloo, a member of the Institute for Quantum Computing, an affiliate member of the Perimeter Institute for Theoretical Physics and a Fellow of the Canadian...
. This model was developed further by Wim van Dam, 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. A second wave of models includes those of Susanne Richter and Reinhard Werner, 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.
Models of physical systems
Models of quantum cellular automata have been proposed by David Meyer, by Bruce Bogosian and Washington Taylor, and by Peter Love and Bruce Bogosian 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.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 TougawPaul Douglas Tougaw
Paul Douglas Tougaw, born July 3, 1969, is the chair of and a professor in the Department of Electrical and Computer Engineering at Valparaiso University. He received his B.S. in Electrical Engineering from the Rose-Hulmann Institute of Technology and his M.S. and Ph.D. in Electrical Engineering...
and Craig Lent, 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
Quantum dot cellular automaton
Quantum Dot Cellular Automata are proposed models of quantum computation, which have been devised in analogy to conventional models of cellular automata introduced by von Neumann.-Background:...
.