Cellular automata in operational probabilistic theories
arXiv:1911.11216 · doi:10.22331/q-2020-07-09-294
Abstract
The theory of cellular automata in operational probabilistic theories is developed. We start introducing the composition of infinitely many elementary systems, and then use this notion to define update rules for such infinite composite systems. The notion of causal influence is introduced, and its relation with the usual property of signalling is discussed. We then introduce homogeneity, namely the property of an update rule to evolve every system in the same way, and prove that systems evolving by a homogeneous rule always correspond to vertices of a Cayley graph. Next, we define the notion of locality for update rules. Cellular automata are then defined as homogeneous and local update rules. Finally, we prove a general version of the wrapping lemma, that connects CA on different Cayley graphs sharing some small-scale structure of neighbourhoods.
arXiv commentUpdated version: the only change consists in the extension of the proof of lemma 2
References in corpus (28)
- Fermionic quantum computation
- In defense of the epistemic view of quantum states: a toy theory
- Informational derivation of Quantum Theory
- Probabilistic theories with purification
- A derivation of quantum theory from physical requirements
- Causal and localizable quantum operations
- Index theory of one dimensional quantum walks and cellular automata
- A review of Quantum Cellular Automata
- Limited Holism and Real-Vector-Space Quantum Theory
- Semicausal operations are semilocalizable
- Derivation of the Dirac Equation from Principles of Information Processing
- Quantum Field as a quantum cellular automaton: the Dirac free evolution in one dimension
- Three routes to the exact asymptotics for the one-dimensional quantum walk
- The Feynman problem and Fermionic entanglement: Fermionic theory versus qubit theory
- Classification of Quantum Cellular Automata
- Fermionic computation is non-local tomographic and violates monogamy of entanglement
- Propagating Quantum Walks: the origin of interference structures
- The Thirring quantum cellular automaton
- Quantum cellular automata and free quantum field theory
- The Dirac Quantum Cellular Automaton in one dimension: Zitterbewegung and scattering from potential
- The Group Structure of Quantum Cellular Automata
- Generalized Partitioned Quantum Cellular Automata and Quantization of Classical CA
- Testing axioms for Quantum Mechanics on Probabilistic toy-theories
- Solutions of a two-particle interacting quantum walk
- Weyl, Dirac and Maxwell Quantum Cellular Automata: analitical solutions and phenomenological predictions of the Quantum Cellular Automata Theory of Free Fields
- Isotropic quantum walks on lattices and the Weyl equation
- Bounds on the Speedup in Quantum signalling
- Scalar fermionic cellular automata on finite Cayley graphs
Cited by in corpus (10)
- General probabilistic theories: An introduction
- Classicality without local discriminability: decoupling entanglement and complementarity
- Incompatibility of observables, channels and instruments in information theories
- Causal and compositional structure of unitary transformations
- Can quantum non-locality be connected to extra-dimensions?
- Shannon theory beyond quantum: information content of a source
- Causal influence in operational probabilistic theories
- Renormalisation of Quantum Cellular Automata
- Minimal operational theories: classical theories with quantum features
- Causal influence versus signalling for interacting quantum channels