Quantum cellular automata are alternative quantum-computing paradigms to quantum Turing machines and quantum circuits. Their working mechanisms are inherently automated, therefore measurement free, and they act in a translation invariant manner on all cells or qudits of a register, generating a global rule that updates cell states locally, i.e., based solely on the states of their neighbors. Although desirable features in many applications, it is generally not clear to which extent these fully automated discrete-time local updates can generate and sustain long-range order in the (noisy) systems they act upon. In particular, whether and how quantum cellular automata can perform quantum error correction remain open questions. We close this conceptual gap by proposing quantum cellular automata with quantum-error-correction capabilities. We design and investigate two (quasi)one dimensional quantum cellular automata based on known classical cellular-automata rules with density-classification capabilities, namely the local majority voting and the two-line voting. We investigate the performances of those quantum cellular automata as quantum-memory components by simulating the number of update steps required for the logical information they act upon to be afflicted by a logical bit flip. The proposed designs pave a way to further explore the potential of new types of quantum cellular automata with built-in quantum-error-correction capabilities.
Quantum cellular automata are alternative quantum-computing paradigms to quantum Turing machines and quantum circuits. Their working mechanisms are inherently automated, therefore measurement free, and they act in a translation invariant manner on all cells or qudits of a register, generating a global rule that updates cell states locally, i.e., based solely on the states of their neighbors. Although desirable features in many applications, it is generally not clear to which extent these fully automated discrete-time local updates can generate and sustain long-range order in the (noisy) systems they act upon. In particular, whether and how quantum cellular automata can perform quantum error correction remain open questions. We close this conceptual gap by proposing quantum cellular automata with quantum-error-correction capabilities. We design and investigate two (quasi)one dimensional quantum cellular automata based on known classical cellular-automata rules with density-classification capabilities, namely the local majority voting and the two-line voting. We investigate the performances of those quantum cellular automata as quantum-memory components by simulating the number of update steps required for the logical information they act upon to be afflicted by a logical bit flip. The proposed designs pave a way to further explore the potential of new types of quantum cellular automata with built-in quantum-error-correction capabilities.
Quantum error correction (QEC) normally requires active maintenance using measurements, classical processing and externally controlled correction schedules. Passive QEC, by contrast, was previously established only in unphysical spatial dimensions. Here, we give an explicit scheme for autonomous quantum error correction and computation in two dimensions, formulated as a dissipative quantum cellular automaton with a fixed, local and translation-invariant update rule. The construction uses hierarchical, self-simulating control elements based on ideas from the seminal classical results of Gács (1986, 1989) together with a measurement-free concatenated quantum code. We prove the existence of a nonzero noise threshold under a local noise model. Below this threshold, logical errors on encoded initial states are suppressed exponentially with increasing system size and the memory lifetime diverges in the thermodynamic limit. As an extension, we outline how this mechanism can also be implemented in continuous time by a time-independent, translation-invariant local Lindbladian. Quantum circuits can moreover be encoded in the automaton's initial state and executed fault-tolerantly with polylogarithmic overhead under the same circuit-independent rule. Our scheme thus realizes a self-correcting quantum computer capable of universal computation.
Quantum cellular automata are alternative quantum-computing paradigms to quantum Turing machines and quantum circuits. Their working mechanisms are inherently automated, therefore measurement free, and they act in a translation invariant manner on all cells/qudits of a register, generating a global rule that updates cell states locally, i.e., based solely on the states of their neighbors. Although desirable features in many applications, it is generally not clear to which extent these fully automated discrete-time local updates can generate and sustain long-range order in the (noisy) systems they act upon. In special, whether and how quantum cellular automata can perform quantum error correction remain open questions. We close this conceptual gap by proposing quantum cellular automata with quantum-error-correction capabilities. We design and investigate two (quasi-)one dimensional quantum cellular automata based on known classical cellular-automata rules with density-classification capabilities, namely the local majority voting and the two-line voting. We investigate the performances of those quantum cellular automata as quantum-memory components by simulating the number of update steps required for the logical information they act upon to be afflicted by a logical bit flip. The proposed designs pave a way to further explore the potential of new types of quantum cellular automata with built-in quantum error correction capabilities.
Quantum cellular automata consist in arrays of identical finite-dimensional quantum systems, evolving in discrete-time steps by iterating a unitary operator G. Moreover the global evolution G is required to be causal (it propagates information at a bounded speed) and translation-invariant (it acts everywhere the same). Quantum cellular automata provide a model/architecture for distributed quantum computation. More generally, they encompass most of discrete-space discrete-time quantum theory. We give an overview of their theory, with particular focus on structure results; computability and universality results; and quantum simulation results.
The density classification (DC) task, a computation which maps global density information to local density, is studied using one-dimensional non-unitary quantum cellular automata (QCAs). Two approaches are considered: one that preserves the number density and one that performs majority voting. For number-preserving DC, two QCAs are introduced that reach the fixed-point solution in a time scaling quadratically with the system size. One of the QCAs is based on a known classical probabilistic cellular automaton which has been studied in the context of DC. The second is a new quantum model that is designed to demonstrate additional quantum features and is restricted to only two-body interactions. Both can be generated by continuous-time Lindblad dynamics. A third QCA is a hybrid rule defined by both discrete-time and continuous-time three-body interactions that is shown to solve the majority voting problem within a time that scales linearly with the system size.
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.
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.