2025/10/08 by Pedro C. S. Costa, Yuval R. Sanders, Costa, Pedro C. S. +4
Computer Science · #Cellular Automata and Applications #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #Quantum-Dot Cellular Automata
paper · pdf · doi:10.48550/arxiv.2510.06947
openalex publication_date 2025/10/08 · openalex created_date 2025/10/18 · openalex updated_date 2026/07/28
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 ≥ 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.