NONLOCAL COMPUTATION IN QUANTUM CELLULAR-AUTOMATA

Quantum cellular automata (QCA) have been introduced [G. Grossing 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.