methods [5, 6, 7] that lead to a wealth of remark-
able results [8, 9, 10, 11]. In particular, quan-
tum theory can be now understood as a theory
of information processing, that is selected among
a universe of alternate theories [12, 13, 1, 14] by
operational principles about the possibility or im-
possibility to perform specific information pro-
cessing tasks [9, 15].
The scenario of alternate theories among which
the principles select quantum theory is called the
framework of Operational Probabilistic Theories
(OPTs) [8, 15], and has connections with the less
structured concept of Generalized Probabilistic
Theory (GPT) [5, 16, 17], as well as the dia-
grammatic category theoretical approach often
referred to as quantum picturialism [18, 19]. In-
spiration for the framework came also from quan-
tum logic [20, 21].
Quantum theory, namely the theory of Hilbert
spaces, density matrices, completely positive
maps and POVMs (in particular we refer to the
elegant exposition of Ref. [22]), can thus be re-
formulated as a special theory of information pro-
cessing. Besides the many advantages of this re-
sult, one has to face a main issue: the theory
as such is devoid of its physical content. El-
ementary systems are thought of as elementary
information carriers—brutally speaking, memory
cells—rather than elementary particles or fields in
space-time. While this framework is satisfactory
for an effective, empirical description of physical
experiments, when it comes to provide a theo-
retical foundation for the physics of elementary
systems, the informational approach at this stage
calls for a way to re-embrace mechanical notions
such as mass, energy, position, space-time, and
complete the picture encompassing the dynamics
of quantum systems.
A recent proposal for this endeavour is based
on the idea that physical laws have to be ulti-
mately understood as algorithms, that make sys-
tems evolve, changing their state, exactly as the
memory cells of a computer are updated by the
run of an algorithm [23, 24, 25]. Such a program
already achieved successful results in the recon-
struction of Weyl’s, Dirac’s and Maxwell’s equa-
tions (for a comprehensive review see Ref. [26]).
The most natural candidate algorithm for de-
scribing a physical law in this context is a cellular
automaton. The theory of cellular automata is
a wide and established branch of computer sci-
ence. The notion of a cellular automaton for
quantum systems was first devised as the quan-
tum version of its classical counterpart, e.g. in
Refs. [27, 28, 29, 30], but turned out to give rise to
a rather independent theory, developed starting
from Ref. [31]: the theory of Quantum Cellular
Automata (QCAs). The latter counts presently
various important results—see e.g. Refs. [32, 33],
just to mention a few. We stress that, most
commonly, QCAs are defined to be reversible al-
gorithms, and most results in the literature are
proved with this hypothesis. It is known, how-
ever, that many desirable preoperties fail to hold
in the irreversible case (see e.g. Ref. [34]). In the
present work we will not consider irreversible cel-
lular automata, and leave this subject for further
studies.
In order to use cellular automata as candi-
date physical laws in the foundational perspec-
tive based on OPTs, one has two choices at
hand. The first one is to start treating automata
within a definite theory, and this is the approach
adopted so far, in particular within Fermionic
theory [35, 36, 37]. In the linear case, Fermionic
cellular automata reduce to Quantum Walks, and
this brings in the picture all the tools from such
widely studied topic [38, 39, 40, 41, 42, 43]. The
non-linear case is far less studied [44, 45], and
does not offer as many results for the analy-
sis. Needless to say, this approach faces difficul-
ties that are specific of the theory at hand, and
prevents a comparison of different theories on a
ground that is genuinely physical.
The second approach is initiated in the present
paper, and consists in defining cellular automata
in the general context of OPTs. This perspective
offers the possibility of extracting the essential
features of the theory of quantum or Fermionic
cellular automata, those that are not specific of
the theory but are well suited in any theory of
information processing. As a consequence, one
can generalise some results, and figure out why
and how others fail to extend to the broader sce-
nario. Moving a much less structured mathemat-
ical context, this approach can use only few tools,
but provides results that have the widest appli-
cability range.
Accepted in Quantum 2020-07-03, click title to verify. Published under CC-BY 4.0. 2