Density Classification with Non-Unitary Quantum Cellular Automata

Area of Science:

• Quantum Information Science
• Computational Physics
• Complex Systems

Background:

• Density Classification (DC) is a fundamental computation mapping global density to local density.
• Cellular automata (CA) are widely used models for studying complex systems.
• Quantum Cellular Automata (QCAs) offer a quantum mechanical framework for computation.

Purpose of the Study:

• To investigate the application of one-dimensional non-unitary quantum cellular automata (QCAs) to the density classification task.
• To develop and analyze QCAs that preserve number density and perform majority voting.
• To explore quantum features and interaction types within QCA models for DC.

Main Methods:

• Development of two number-preserving QCAs, one based on a classical probabilistic automaton and a novel quantum model.
• Analysis of QCA dynamics, including continuous-time Lindblad dynamics.
• Introduction of a hybrid QCA rule combining discrete-time and continuous-time three-body interactions.

Main Results:

• Number-preserving QCAs achieve fixed-point solutions with time complexity scaling quadratically with system size.
• A novel two-body interaction QCA demonstrates additional quantum features.
• A hybrid three-body interaction QCA solves the majority voting problem with linear time complexity.

Conclusions:

• Non-unitary QCAs provide effective models for solving the density classification task.
• Quantum approaches offer advantages in computational efficiency compared to classical counterparts.
• The study highlights the potential of QCAs for exploring quantum computation and complex system dynamics.