Quantum cellular automata (QCA) have been introduced [G. Gr\"ossing and A. Zeilinger, Complex Syst. 2, 197 (1988); 2, 611 (1988)] as n-dimensional arrays of discrete sites characterized by a complex number whose absolute square lies between 0 and 1 such that each site represents a quantum-mechanical probability amplitude. The evolutions of one-dimensional QCA with a local (i.e., nearest-neighbor) interaction and with periodic boundary conditions have been studied in some detail. In this paper we present a thorough mathematical analysis of one-dimensional QCA, and we particularly emphasize the effects of what we term nonlocal computation: because of the conservation of the total probability for each time step, information of the global array spread out over generally nonlocal distances must be conveyed for each time step to each local site via the normalization procedure. With the aid of a mathematical description of QCA evolution the following, previously observed phenomena can be explained: (i) the asymptotic appearance of plane-wave patterns after a characteristic transient phase, (ii) the dependence of the period of the patterns on the input parameters for both small and large values of the couplings between the sites, and (iii) the role of the initial values of the cells. Finally, the effects of nonlocal computation are made visible with the simulation of a ``double-slit-like'' experiment on a QCA grid.
Quantum cellular automata (QCA) have been introduced [G. Gr"ossing and A. Zeilinger, Complex Syst. 2, 197 (1988); 2, 611 (1988)] as n-dimensional arrays of discrete sites characterized by a complex number whose absolute square lies between 0 and 1 such that each site represents a quantum-mechanical probability amplitude. The evolutions of one-dimensional QCA with a local (i.e., nearest-neighbor) interaction and with periodic boundary conditions have been studied in some detail. In this paper we present a thorough mathematical analysis of one-dimensional QCA, and we particularly emphasize the effects of what we term nonlocal computation: because of the conservation of the total probability for each time step, information of the global array spread out over generally nonlocal distances must be conveyed for each time step to each local site via the normalization procedure. With the aid of a mathematical description of QCA evolution the following, previously observed phenomena can be explained: (i) the asymptotic appearance of plane-wave patterns after a characteristic transient phase, (ii) the dependence of the period of the patterns on the input parameters for both small and large values of the couplings between the sites, and (iii) the role of the initial values of the cells. Finally, the effects of nonlocal computation are made visible with the simulation of a ``double-slit-like'' experiment on a QCA grid.
This thesis presents a model of Quantum Cellular Automata (QCA). The presented formalism is a natural quantization of the classical Cellular Automata (CA). It is based on a lattice of qudits, and an update rule consisting of local unitary operators that commute with their own lattice translations. One purpose of this model is to act as a theoretical model of quantum computation, similar to the quantum circuit model. The main advantage that QCA have over quantum circuits is that QCA make considerably fewer demands on the underlying hardware. In particular, as opposed to direct implementations of quantum circuits, the global evolution of the lattice in the QCA model does not assume independent control over individual \emph{qudits}. Rather, all qudits are to be addressed collectively in parallel. The QCA model is also shown to be an appropriate abstraction for space-homogeneous quantum phenomena, such as quantum lattice gases, spin chains and others. Some results that show the benefits of basing the model on local unitary operators are shown: computational universality, strong connections to the circuit model, simple implementation on quantum hardware, and a series of applications. A detailed discussion will be given on one particular application of QCA that lies outside either computation or simulation: single-spin measurement. This algorithm uses the techniques developed in this thesis to achieve a result normally considered hard in physics. It serves well as an example of why QCA are interesting in their own right.
The quantum walk is a subset of classical random walks.Considerable research has lately been conducted on quantum walks in relation to quantum computing.The walk may be thought of as a type of quantum cellular automata.In a broader sense, there is a one-to-one link between them.Furthermore, we look at another type of quantum cellular automata that may be thought of as a quantum version of stochastic cellular automata.The quantum walk formalism is a widely used and quite practical paradigm for modelling quantum systems such as Dirac equation simulations, discrete dynamics in both the low and high energy regimes, and the development of a multitude of quantum algorithms.The walker in a QW moves in a quantum superposition of pathways, and the ensuing interference serves as the foundation for a broad range of quantum algorithms, including quantum search, graph isomorphism issues, and rating nodes in a network.To generate a block representation of n-dimensional quantum cellular automata, we apply the following general result to them.As a result, we have demonstrated that their generic, axiomatic formulation nevertheless produces a unifying, operational representation of them.Some non-trivial ramifications are investigated, such as the fact that bijective non-reversible CA are not physical as closed systems, or that quantum information can move faster than classical informationwithin some specified dynamics.Finally, we present n-dimensional quantum cellular automata that can simulate anything else.This means that the initial configuration and local transition rule of any one-dimensional QCA may be stored within the universal QCA's initial configuration.The simulated QCA will then correspond to many phases of the universal QCA.In the sense that each cell in the simulated QCA is represented as a group of nearby cells in the universal QCA, the simulation preserves the topology.Because the encoding is linear, it bears no cost of the calculation.
Discretizing spacetime is often a natural step towards modelling physical systems. For quantum systems, if we also demand a strict bound on the speed of information propagation, we get quantum cellular automata (QCAs). These originally arose as an alternative paradigm for quantum computation, though more recently they have found application in understanding topological phases of matter and have} been proposed as models of periodically driven (Floquet) quantum systems, where QCA methods were used to classify their phases. QCAs have also been used as a natural discretization of quantum field theory, and some interesting examples of QCAs have been introduced that become interacting quantum field theories in the continuum limit. This review discusses all of these applications, as well as some other interesting results on the structure of quantum cellular automata, including the tensor-network unitary approach, the index theory and higher dimensional classifications of QCAs.
Several proposed schemes for the physical realization of a quantum computer consist of qubits arranged in a cellular array. In the quantum circuit model of quantum computation, an often complex series of two-qubit gate operations is required between arbitrarily distant pairs of lattice qubits. An alternative model of quantum computation based on quantum cellular automata (QCA) requires only homogeneous local interactions that can be implemented in parallel. This would be a huge simplification in an actual experiment. We find some minimal physical requirements for the construction of unitary QCA in a one-dimensional Ising spin chain and demonstrate optimal pulse sequences for information transport and entanglement distribution. We also introduce the theory of nonunitary QCA and show by example that nonunitary rules can generate environment assisted entanglement.
We define quantum cellular automata as infinite quantum lattice systems with discrete time dynamics, such that the time step commutes with lattice translations and has strictly finite propagation speed. In contrast to earlier definitions this allows us to give an explicit characterization of all local rules generating such automata. The same local rules also generate the global time step for automata with periodic boundary conditions. Our main structure theorem asserts that any quantum cellular automaton is structurally reversible, i.e., that it can be obtained by applying two blockwise unitary operations in a generalized Margolus partitioning scheme. This implies that, in contrast to the classical case, the inverse of a nearest neighbor quantum cellular automaton is again a nearest neighbor automaton. We present several construction methods for quantum cellular automata, based on unitaries commuting with their translates, on the quantization of (arbitrary) reversible classical cellular automata, on quantum circuits, and on Clifford transformations with respect to a description of the single cells by finite Weyl systems. Moreover, we indicate how quantum random walks can be considered as special cases of cellular automata, namely by restricting a quantum lattice gas automaton with local particle number conservation to the single particle sector.