Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2510.06947

Unitary Quantum Cellular Automata for Density Classification

Pedro C. S. Costa, Yuval R. Sanders, Balbi, Pedro Paulo, Gavin K. Brennen

Published Oct 8, 2025• 0 citations
arXivHTMLPDF

Abstract

We investigate the density classification task (DCT) -- determining the majority bit in a one-dimensional binary lattice -- within a quantum cellular automaton (CA) framework. While there is no one-dimensional two-state, radius $r \geq 1$, deterministic CA with periodic boundary conditions that solves the DCT perfectly, we explore whether a unitary quantum model can succeed. We employ the Partitioned Unitary Quantum Cellular Automaton (PUQCA), a number-conserving model, and, via evolutionary search, find solutions to the DCT where the success condition is stipulated in terms of measurement probabilities rather than convergence to fixed-point configurations. Finally, we identify a classically simulable regime of the PUQCA in which we find rules that solve the DCT at fixed system sizes and analyze their performance.

DOI
10.48550/arxiv.2510.06947

Related papers

Density Classification with Non-Unitary Quantum Cellular Automata

Elisabeth Wagner, Federico Dell’Anna, Ramil Nigmatullin +1 more

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.

arXiv:2404.05461•Entropy•Dec 31, 2024•2 citations

When is a quantum cellular automaton (QCA) a quantum lattice gas automaton (QLGA)?

Asif Shakeel, Peter J. Love

Quantum cellular automata (QCA) are models of quantum computation of particular interest from the point of view of quantum simulation. Quantum lattice gas automata (QLGA - equivalently partitioned quantum cellular automata) represent an interesting subclass of QCA. QLGA have been more deeply analyzed than QCA, whereas general QCA are likely to capture a wider range of quantum behavior. Discriminating between QLGA and QCA is therefore an important question. In spite of much prior work, classifying which QCA are QLGA has remained an open problem. In the present paper we establish necessary and sufficient conditions for unbounded, finite QCA (finitely many active cells in a quiescent background) to be QLGA. We define a local condition that classifies those QCA that are QLGA, and we show that there are QCA that are not QLGA. We use a number of tools from functional analysis of separable Hilbert spaces and representation theory of associative algebras that enable us to treat QCA on finite but unbounded configurations in full detail.

arXiv:1209.5367•Journal of Mathematical Physics•Sep 1, 2013•24 citations

Quantum Cellular Automata for Quantum Error Correction and Density Classification

Thiago L. M. Guedes, D. Winter, Markus Müller

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.

Physical Review Letters•Oct 7, 2024•9 citations

Quantum cellular automata for quantum error correction and density classification

Thiago L. M. Guedes, Winter, Don, Markus Müller

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.

arXiv:2309.03608•Jan 1, 2023•0 citations

Quantum State Collapse as a Cellular Automaton Algorithm

Jincheng Zhang

Quantum state collapse is a fundamental process in quantum mechanics, representing the irreversible loss of information upon measurement. This paper explores the potential of utilizing a cellular automata (CA) framework to model and simulate this collapse, offering a novel approach to understanding and potentially manipulating quantum evolution. We formalize collapse as a dynamic process governed by specific rules and feedback loops, enabling the simulation of complex quantum patterns. We propose a CA-based model that incorporates the probabilistic nature of quantum mechanics, allowing for a more intuitive and potentially controllable simulation of quantum phenomena. The core mechanism focuses on systematically evolving the system's state space, mirroring the collapse process and highlighting the interplay between initial conditions and emergent behavior. This work provides a foundational step in exploring the application of CA algorithms to complex quantum systems, opening avenues for future research in quantum simulation and understanding.

•Sep 6, 2026•0 citations

Training the classification capability of large-scale quantum cellular automata

Mario Boneberg, Simon Kochsiek, Gabriele Perfetto +1 more

In the vicinity of a phase transition ergodicity can be broken. Here, different initial many-body configurations evolve towards one of several fixed points, which are macroscopically distinguishable through an order parameter. This mechanism enables state classification in quantum cellular automata and feed-forward quantum neural networks. We demonstrate that this capability can be efficiently learned from training data even in extremely high-dimensional state spaces. We illustrate this using a quantum cellular automaton that allows binary classification, which is closely connected to the dynamics of a $\mathbb{Z}_2$-symmetric Ising model with local interactions and dissipation. This approach can be generalized beyond binary classification and offers a natural framework for exploring the link between emergent many-body phenomena and the interpretation of data processing capabilities in the context of quantum machine learning.

arXiv:2509.18262•Physical Review A•Jun 1, 2026•0 citations
We investigate the density classification task (DCT) -- determining the majority bit in a one-dimensional binary lattice -- within a quantum cellular automaton (CA) framework. While there is no one-dimensional two-state, radius r≥1r \geq 1r≥1, deterministic CA with periodic boundary conditions that solves the DCT perfectly, we explore whether a unitary quantum model can succeed. We employ the Partitioned Unitary Quantum Cellular Automaton (PUQCA), a number-conserving model, and, via evolutionary search, find solutions to the DCT where the success condition is stipulated in terms of measurement probabilities rather than convergence to fixed-point configurations. Finally, we identify a classically simulable regime of the PUQCA in which we find rules that solve the DCT at fixed system sizes and analyze their performance.
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.
Quantum cellular automata (QCA) are models of quantum computation of particular interest from the point of view of quantum simulation. Quantum lattice gas automata (QLGA - equivalently partitioned quantum cellular automata) represent an interesting subclass of QCA. QLGA have been more deeply analyzed than QCA, whereas general QCA are likely to capture a wider range of quantum behavior. Discriminating between QLGA and QCA is therefore an important question. In spite of much prior work, classifying which QCA are QLGA has remained an open problem. In the present paper we establish necessary and sufficient conditions for unbounded, finite QCA (finitely many active cells in a quiescent background) to be QLGA. We define a local condition that classifies those QCA that are QLGA, and we show that there are QCA that are not QLGA. We use a number of tools from functional analysis of separable Hilbert spaces and representation theory of associative algebras that enable us to treat QCA on finite but unbounded configurations in full detail.
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/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 state collapse is a fundamental process in quantum mechanics, representing the irreversible loss of information upon measurement. This paper explores the potential of utilizing a cellular automata (CA) framework to model and simulate this collapse, offering a novel approach to understanding and potentially manipulating quantum evolution. We formalize collapse as a dynamic process governed by specific rules and feedback loops, enabling the simulation of complex quantum patterns. We propose a CA-based model that incorporates the probabilistic nature of quantum mechanics, allowing for a more intuitive and potentially controllable simulation of quantum phenomena. The core mechanism focuses on systematically evolving the system's state space, mirroring the collapse process and highlighting the interplay between initial conditions and emergent behavior. This work provides a foundational step in exploring the application of CA algorithms to complex quantum systems, opening avenues for future research in quantum simulation and understanding.
In the vicinity of a phase transition ergodicity can be broken. Here, different initial many-body configurations evolve towards one of several fixed points, which are macroscopically distinguishable through an order parameter. This mechanism enables state classification in quantum cellular automata and feed-forward quantum neural networks. We demonstrate that this capability can be efficiently learned from training data even in extremely high-dimensional state spaces. We illustrate this using a quantum cellular automaton that allows binary classification, which is closely connected to the dynamics of a Z2\mathbb{Z}_2Z2​-symmetric Ising model with local interactions and dissipation. This approach can be generalized beyond binary classification and offers a natural framework for exploring the link between emergent many-body phenomena and the interpretation of data processing capabilities in the context of quantum machine learning.