Density Classification with Non-Unitary Quantum Cellular Automata

Abstract

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.

31 pages, 10 figures. (Update: Removed definitions from previous section I and minor corrections.)

References in corpus (9)

• Measurement-free fault-tolerant quantum error correction in near-term devices
• On fault-tolerance with noisy and slow measurements
• Non-equilibrium phase transitions in $(1+1)$-dimensional quantum cellular automata with controllable quantum correlations
• Directed percolation in non-unitary quantum cellular automata
• Quantum and classical temporal correlations in $(1+1)D$ Quantum Cellular Automata
• A two-party quantum parliament
• Numerical Simulation of Critical Quantum Dynamics without Finite Size Effects
• Quantum cellular automata for quantum error correction and density classification
• Explorations of ternary cellular automata and ternary density classification problems