From quantum cellular automata to quantum lattice gases

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 Schroedinger equation. This has been essential in our construction of an invertible map between such CA and continuous quantum mechanical models, which incorporate a fu...

Quantum cellular automata are important tools in understanding quantum dynamics, thanks to their simple and effective list of rules. Here we investigate explicitly how coherence is built and lost in the evolution of one-dimensional automata subject to noise. Our analysis illustrates the interplay between unitary and noisy dynamics, and draws considerations on their behaviour in the pseudo-frequency domain.

This study presents a novel quantum algorithm for 1D and 2D lattice gas automata simulation, demonstrating logarithmic complexity in terms of $CX$ gates. The algorithm is composed by three main steps: collision, mapping and propagation. A computational complexity analysis and a comparison using different error rates and number of shots are provided. Despite the impact of noise, our findings indicate that accurate simulations could be achieved already on current noisy devices....

We review the class of cellular automata known as lattice gases, and their applications to problems in physics and materials science. The presentation is self-contained, and assumes very little prior knowledge of the subject. Hydrodynamic lattice gases are emphasized, and non-lattice-gas cellular automata -- even those with physical applications -- are not treated at all. We begin with a review of lattice gases as the term is understood in equilibrium statistical physics. We ...

In this paper we introduce a new quantum computation model, the linear quantum cellular automaton. Well-formedness is an essential property for any quantum computing device since it enables us to define the probability of a configuration in an observation as the squared magnitude of its amplitude. We give an efficient algorithm which decides if a linear quantum cellular automaton is well-formed. The complexity of the algorithm is $O(n^2)$ in the algebraic model of computation...

We present a new cellular data processing scheme, a hybrid of existing cellular automata (CA) and gate array architectures, which is optimized for realization at the quantum scale. For conventional computing, the CA-like external clocking avoids the time-scale problems associated with ground-state relaxation schemes. For quantum computing, the architecture constitutes a novel paradigm whereby the algorithm is embedded in spatial, as opposed to temporal, structure. The archite...

One can think of some physical evolutions as being the emergent-effective result of a microscopic discrete model. Inspired by classical coarse-graining procedures, we provide a simple procedure to coarse-grain color-blind quantum cellular automata that follow Goldilocks rules. The procedure consists in (i) space-time grouping the quantum cellular automaton (QCA) in cells of size $N$; (ii) projecting the states of a cell onto its borders, connecting them with the fine dynamics...

A synopsis is offered of the properties of discrete and integer-valued, hence "natural", cellular automata (CA). A particular class comprises the "Hamiltonian CA" with discrete updating rules that resemble Hamilton's equations. The resulting dynamics is linear like the unitary evolution described by the Schr\"odinger equation. Employing Shannon's Sampling Theorem, we construct an invertible map between such CA and continuous quantum mechanical models which incorporate a funda...

It has been shown that certain quantum walks give rise to relativistic wave equations, such as the Dirac and Weyl equations, in their long-wavelength limits. This intriguing result raises the question of whether something similar can happen in the multi-particle case. We construct a one-dimensional quantum cellular automaton (QCA) model which matches the quantum walk in the single particle case, and which approaches the quantum field theory of free fermions in the long-wavele...

Central to the field of quantum machine learning is the design of quantum perceptrons and neural network architectures. A key question in this regard is the impact of quantum effects on the way in which such models process information. Here, we approach this question by establishing a connection between $(1+1)D$ quantum cellular automata, which implement a discrete nonequilibrium quantum many-body dynamics through the successive application of local quantum gates, and recurre...