Feynman and Margolus have shown that a closed, locally interacting quantum system is capable of performing deterministic computation. Feynman's system computes in a serial way. Margolus was able to extend Feynman's ideas to get quantum description of a cellular automaton, i.e. a model which calculates in parallel. In this article, a new kind of speed limit for quantum computation is established. An upper bound on the average velocity ("instructions per second ") for both computers is derived. One would expect a cellular automaton to have a computational velocity which scales with the number k of its cells. However, the upper bound on the average velocity is only proportional to p k in this case. This does not reflect the parallelism of the cellular automaton. Whether it is possible to construct a locally interacting quantum computer that really works in parallel remains an open problem. Introduction There is a growing interest in devices computing on a scale where quantum mechanic...
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.