A method of quantization of classical soliton cellular automata (QSCA) is put forward that provides a description of their time evolution operator by means of quantum circuits that involve quantum gates from which the associated Hamiltonian describing a quantum chain model is constructed. The intrinsic parallelism of QSCA, a phenomenon first known from quantum computers, is also emphasized. Introduction. Soliton cellular automata (SCA), is a class of cellular automata[1] operating on binary sequences with an updating rule function f for each cell, that depends on past and present time cells, the number of which determines the radius r of the automaton[2]. Contrary to usual CA ( that evolve their cells by means of past time cells only), SCA exhibit a variety of evolution patterns[4, 5, 6] that is mainly known to characterize the temporal behavior of
A method of quantization of classical soliton cellular automata (QSCA) is put forward that provides a description of their time evolution operator by means of quantum circuits that involve quantum gates from which the associated Hamiltonian describing a quantum chain model is constructed. The intrinsic parallelism of QSCA, a phenomenon first known from quantum computers, is also emphasized. Introduction. Soliton cellular automata (SCA), is a class of cellular automata[1] operating on binary sequences with an updating rule function f for each cell, that depends on past and present time cells, the number of which determines the radius r of the automaton[2]. Contrary to usual CA ( that evolve their cells by means of past time cells only), SCA exhibit a variety of evolution patterns[4, 5, 6] that is mainly known to characterize the temporal behavior of
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.
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.
This paper proposes a novel approach to quantum algorithm design by leveraging the principles of cellular automata (CA). The core idea is to utilize CA as a hardware abstraction layer for quantum computation, mimicking the evolution rules of qubits. This allows for a parallelized design and optimization of quantum algorithms. Specifically, quantum gates are mapped to CA rules, enabling the simulation of qubit superposition and entanglement through cellular interactions and information transfer. This work explores the theoretical framework and outlines a methodology for designing quantum algorithms using CA, focusing on the potential for enhanced computational efficiency and scalability. The design methodology includes defining the CA grid, encoding quantum states into cellular configurations, translating quantum gates into CA rule updates, and analyzing the resulting algorithm execution. The presented framework offers a fundamentally different perspective on quantum algorithm development, potentially bridging the gap between classical algorithmic design and the unique characteristics of quantum systems. Further research will focus on exploring specific quantum algorithms and evaluating the performance of the CA-based approach.
A quantum cellular automaton (QCA) is a unitary discrete-time evolution of a quantum many-body system, which can be described as a dynamics system , where A is any matrix and is a unitary operator representing the global evolution of QCA. And QCAs are characterized by locality (or causality). Among them, quantum circuits are the special classes of QCAs, which use unitary operators to control and transform the initial quantum state of qubit into a final quantum state, quantum circuits are special and widely studied in quantum information. A group is a set of elements combined with an operation, which satisfies associativity, identity and invertibility. This article shows that group theory provides the right language for studying the relation between QCAs and quantum circuits among them.
We consider discrete and integer-valued cellular automata (CA). A particular class of which comprises "Hamiltonian CA" with equations of motion that bear similarities to Hamilton's equations, while they present discrete updating rules. The dynamics is linear , quite similar to unitary evolution described by the Schrödinger equation. This has been essential in our construction of an invertible map between such CA and continuous quantum mechanical models, which incorporate a fundamental discreteness scale. Based on Shannon's sampling theory, it leads, for example, to a one-to-one relation between quantum mechanical and CA conservation laws. The important issue of linearity of the theory is examined here by incorporating higher-order nonlinearities into the underlying action. These produce inconsistent nonlocal (in time) effects when trying to describe continuously such nonlinear CA. Therefore, in the present framework, only linear CA and local quantum mechanical dynamics are compatible.
Take a cellular automaton, consider that each configuration is a basis vector in some vector space, and linearize the global evolution function. If lucky, the r esult could actually make sense physically, as a valid quantum evolution; but do es it make sense as a quantum cellular automaton? That is the main question we a ddress in this paper. In every model with discrete time and space, two things ar e required in order to qualify as a cellular automaton: invariance by translatio n and locality. We prove that this locality condition is so restrictive in the q uantum case that every quantum cellular automaton constructed in this way - i. e., by linearization of a classical one - must be reversible. We also discuss some subtleties about the extent of nonlocality that can be encountered in the o ne-dimensional case; we show that, even when the quantized version is non local, still, under some conditions, we may be unable to use this nonlocality to trans mit information nonlocally.