# Temporal correlations in the simplest measurement sequences

Lucas B. Vieira<EMAIL_ADDRESS>Institute for Quantum Optics and
Quantum Information (IQOQI), Austrian Academy of Sciences,
Boltzmanngasse 3, 1090 Vienna, Austria  Costantino Budroni
<EMAIL_ADDRESS>Faculty of Physics, University of Vienna,
Boltzmanngasse 5, 1090 Vienna, Austria  Institute for Quantum Optics and
Quantum Information (IQOQI), Austrian Academy of Sciences,
Boltzmanngasse 3, 1090 Vienna, Austria

###### Abstract

We investigate temporal correlations in the simplest measurement scenario,
i.e., that of a physical system on which the same measurement is performed at
different times, producing a sequence of dichotomic outcomes. The resource for
generating such sequences is the internal dimension, or _memory_ , of the
system. We characterize the minimum memory requirements for sequences to be
obtained deterministically, and numerically investigate the probabilistic
behavior below this memory threshold, in both classical and quantum scenarios.
In the classical case, a particular class of sequences is found to offer an
upper-bound for all other sequences, which suggests a nontrivial universal
upper-bound of $1/e$ for the probability of realization of any sequence below
this memory threshold. We further present evidence that no such nontrivial
bound exists in the quantum case.

##  1 Introduction

Temporal correlations arise in any information processing task that consists
of sequential operations, possibly involving inputs, producing an output at
each time step. From a quantum mechanical perspective, these operations can be
interpreted as measurements of some observables of a physical system. Models
of quantum computation involve this notion [Markiewicz  _et
al._(2014)Markiewicz, Przysieżna, Brierley, and Paterek, Zurel  _et
al._(2020)Zurel, Okay, and Raussendorf], but a variety of different approaches
are present in the literature: from random access codes (RACs) [Wiesner(1983),
Ambainis  _et al._(1999)Ambainis, Nayak, Ta-Shma, and Vazirani, Ambainis  _et
al._(2002)Ambainis, Nayak, Ta-Shma, and Vazirani, Bowles  _et
al._(2015)Bowles, Brunner, and Pawłowski, Aguilar  _et al._(2018)Aguilar,
Farkas, Martínez, Alvarado, Cariñe, Xavier, Barra, Cañas, Pawłowski, and Lima,
Miklin  _et al._(2020)Miklin, Borkała, and Pawłowski], to classical
simulations of quantum contextuality [Kleinmann  _et al._(2011)Kleinmann,
Gühne, Portillo, Åke Larsson, and Cabello, Fagundes and Kleinmann(2017)],
quantum simulation of stochastic processes [Garner  _et al._(2017)Garner, Liu,
Thompson, Vedral, and Gu, Elliott and Gu(2018), Elliott  _et
al._(2020)Elliott, Yang, Binder, Garner, Thompson, and Gu], purity
certification [Spee(2020)], and time-keeping devices [Erker  _et
al._(2017)Erker, Mitchison, Silva, Woods, Brunner, and Huber, Woods  _et
al._(2018)Woods, Silva, Pütz, Stupar, and Renner, Woods(2021), Schwarzhans
_et al._(2021)Schwarzhans, Lock, Erker, Friis, and Huber].

In parallel to quantum information applications, an analysis of nonclassical
properties of temporal correlations was proposed by Leggett and Garg (LG)
[Leggett and Garg(1985), Emary  _et al._(2014)Emary, Lambert, and Nori], who
investigated the limitation of temporal correlations in a classical theory
they called _macroscopic realism_. Similarly to the case of Bell nonlocality
[Bell(1964), Brunner  _et al._(2014)Brunner, Cavalcanti, Pironio, Scarani, and
Wehner], an experimental violation of LG inequalities disproves that the
observed correlations come from a macrorealist theory. In addition to the
standard assumption of _realism_ , i.e., that physical variables have a
definite value at any instant of time, macrorealist theories assume that such
values can be measured in a _non-invasive_ way. The latter is a strong
condition that makes LG experiments challenging due to the _clumsiness
loophole_ [Wilde and Mizel(2012)]: A clumsy measurement alone may be
responsible for the violation of the LG inequality, and considerable effort is
needed to close it [Budroni  _et al._(2015)Budroni, Vitagliano, Colangelo,
Sewell, Gühne, Tóth, and Mitchell, Halliwell(2016), Knee  _et al._(2016)Knee,
Kakuyanagi, Yeh, Matsuzaki, Toida, Yamaguchi, Saito, Leggett, and Munro,
Emary(2017), Uola  _et al._(2019)Uola, Vitagliano, and Budroni]. It is clear,
then, that any information processing task where the information carrier is
modified by sequential operations cannot be discussed in terms of LG
inequalities. A recently introduced framework [Budroni  _et al._(2019)Budroni,
Fagundes, and Kleinmann] for temporal correlations, admitting invasive
measurements, overcomes this problem: any operation on the physical system
under consideration modifies (or store information in) it, but up to a limit,
given by its _internal memory_. The case of a noninvasive measurement is
recovered for zero bits of internal memory. Of course, the amount of
invasiveness must be limited, otherwise classical theory is able to generate
the same correlations as quantum theory [Fritz(2010), Hoffmann  _et
al._(2018)Hoffmann, Spee, Gühne, and Budroni]. This framework has been
explored from several perspectives: quantum dimension witnesses [Hoffmann  _et
al._(2018)Hoffmann, Spee, Gühne, and Budroni, Spee  _et al._(2020a)Spee,
Siebeneich, Gloger, Kaufmann, Johanning, Kleinmann, Wunderlich, and Gühne],
differences between classical, quantum, and general probability theories
[Budroni  _et al._(2019)Budroni, Fagundes, and Kleinmann], minimal dimensional
realizations of extreme correlations [Spee  _et al._(2020b)Spee, Budroni, and
Gühne] and their convex mixtures [Mao  _et al._(2020)Mao, Spee, Xu, and Gühne]
(albeit with different assumptions on the time evolution and convexity
properties), and time-keeping devices [Budroni  _et al._(2021)Budroni,
Vitagliano, and Woods].

In this paper, we consider the simplest form of temporal correlations: A
single finite-dimensional system subjected to the same dichotomous measurement
at different times. Such a system can be modeled as a probabilistic _finite-
state automaton_ [Rabin(1963), Paz(1971)] (FA, defined in section 2). First,
we investigate the minimal dimension necessary to generate a sequence, which
we call its _deterministic complexity_ ($\operatorname{DC}$), and provide an
efficient algorithm to compute it. Below this dimension, i.e., for
$d<\operatorname{DC}$, any realization must be probabilistic and only here
difference between classical and quantum correlations may arise [Spee  _et
al._(2020b)Spee, Budroni, and Gühne]. Then, we investigate numerically all
classical sequences up to $L=10$, and all $d<\operatorname{DC}$. Our results
suggest that the probability of each sequence, for any $d<\operatorname{DC}$,
can be upper bounded by the probability of a special sequence, called _one-
tick sequence_ , of length $\operatorname{DC}$ and realized in the same
dimension. If proven, this conjecture would imply an universal bound of $1/e$
for the probability of realization of any sequence in $d<\operatorname{DC}$.
Finally, we show how quantum models can outperform classical ones and provide
an explicit model approaching the bound of probability $1$ in the limit of
long sequences and high dimension.

The paper is organized as follows. In Sec. 2, we introduce the formalism and
basic concepts related to finite-state automata. In Sec. 3, we investigate the
minimal dimension necessary to deterministically generate a sequence of
outputs. In Sec. 4, we investigate minimal classical probabilistic
realizations. In Sec. 5, we investigate quantum realizations. Finally, in Sec.
6, we present the conclusion and outlook of our work.

##  2 Preliminary notions

A finite-state automaton (FA) is a machine that generates an output, belonging
to some alphabet $\mathcal{A}$, and performs a state transition both according
to a time-independent probabilistic rule. We assume the machine has $d$
internal states (classical or quantum) and produces a sequence of outcomes
$\vec{a}=(a_{1},a_{2},\dots,a_{L})$, $a_{i}\in\mathcal{A}$, for a sequence of
measurements of length $L$. It may be helpful sometimes to denote the sequence
of outcomes as $\vec{a}^{L}$ to indicate that it has length $L$.

Our model may be thought of as a box with $d$ internal states, a display, a
“measure” button, and a “reset” button (Figure 1). Upon pressing “measure”,
the box performs a time-invariant, and possibly invasive, dichotomous
measurement, and displays the outcome ($0$ or $1$). We perform the measurement
as many times as we wish, e.g., $L=4$ times, obtaining a _sequence_ of
outcomes, e.g., $\vec{a}=(0,0,1,0)$, after which we reset the box to its
initial state and repeat the experiment. Over many trials we estimate a
probability distribution over all possible outcomes the box can realize using
its $d$ internal states as a resource.

Figure 1: A pictorial representation of our physical model, as a box with a
“measure” button (red, on top), a “reset” button (blue, in front), and a
display for the outcomes of measurements performed by the box. The “measure”
button is pressed $L$ times to generate a sequence of length $L$, then the
“reset” button brings the machine to its initial state, and the measurement
sequence can be repeated to collect statistics.

The classical model (see [Paz(1971)] for a textbook introduction, and [Shallit
and Wang(2001)]) is described by a pair of matrices $T=(T_{0},T_{1})$, where
$T_{0},T_{1}$ are sub-stochastic transition matrices such that $T_{0}+T_{1}$
is row-stochastic, i.e., with nonnegative entries, $[T_{a}]_{ij}\geq 0$ for
$a=0,1$, and $\sum_{j}[T_{0}]_{ij}+[T_{1}]_{ij}=1$ for all $i$. Given a
$d$-dimensional classical model $T$, a sequence $\vec{a}$, an initial state
$\pi$, its probability can be computed as

$p(\vec{a}|T,d)=\pi T_{a_{1}}T_{a_{2}}\dots T_{a_{L}}\eta,$ (1)

where $\pi$ is a distribution over all possible $d$ states, i.e., $\pi_{i}\geq
0$ and $\sum_{i}\pi_{i}=1$, and $\eta:=(1,1,\ldots,1)^{\mathsf{T}}$ provides
the sum over all possible final states. From this definition, it is clear that
switching all $0\leftrightarrow 1$ gives the same probability, as the model is
symmetric under relabeling. Thus, without loss of generality, we can assume
$a_{1}=0$.

In the quantum case, the output generation is simply interpreted as sequential
quantum measurements. The output probability and state transition are
described by the instruments $\mathcal{I}=(\mathcal{I}_{0},\mathcal{I}_{1})$,
in the Heisenberg picture, i.e., $\mathcal{I}_{a}$ is completely positive (CP)
for $a=0,1$ and $\mathcal{I}_{0}+\mathcal{I}_{1}$ is a unital map. For an
initial state $\rho$ on a $d$-dimensional Hilbert space, the probability for a
sequence $\vec{a}$ is then

$p(\vec{a}|\mathcal{I},d)=\operatorname{tr}[\rho\
\mathcal{I}_{a_{1}}\circ\mathcal{I}_{a_{2}}\circ\ldots\mathcal{I}_{a_{L}}(\mathbbm{1})].$
(2)

The classical case is recovered by requiring the initial state and
transformation to be diagonal in the same basis. The time evolution is not
explicitly considered here. However, a unitary time evolution, and even some
forms of Markovian ones, can be absorbed into the definition of the
instruments with a proper choice of measurement times, and deviations from
this ideal situation can be taken into account [Spee  _et al._(2020b)Spee,
Budroni, and Gühne].

We call the pair $T=(T_{0},T_{1})$ or the pair
$\mathcal{I}=(\mathcal{I}_{0},\mathcal{I}_{1})$, a FA, or simply a _model_ ,
when its classical or quantum nature is clear from the context or irrelevant.

A sequence of particular interest, as we shall see, is the sequence
$\vec{a}^{L}=(0,0,\ldots,0,1)$. It appeared in the investigation of classical
and quantum clocks [Budroni  _et al._(2021)Budroni, Vitagliano, and Woods], as
the sequence corresponding to one tick of the clock. We, thus, call it the
_one-tick sequence_ and denote it as ${\vec{a}_{\rm ot}}^{L}$.

##  3 Lossless compression of a model

Figure 2: The general structure of minimal DFAs corresponding to minimal
patterns. The initial state is denoted by a thick incoming arrow, nodes of the
graph represent the internal states, arrows state transitions and symbols
$a_{i}$ the output associated with them. For a pattern the minimal model
consists of a tail, with $l_{1}\geq 0$ states, which leads to a cycle, with
$l_{2}>0$ states.

The internal memory of the system, either classical or quantum, is the
resource needed to reproduce a given sequence $\vec{a}$. Not all models,
however, use this memory efficiently. In many cases, the number of internal
states of a model can be reduced, still obtaining the chosen sequence with
probability $1$. In this section, we investigate precisely the minimal amount
of resources needed to reproduce a sequence deterministically, by providing an
explicit algorithm to compute it. We first outline our working definition.

######  Definition.

(Lossless compression of a model). If the number of internal states of a model
can be reduced, and the model is still able to generate the same sequence with
probability $1$, we speak of a _lossless compression_ of the model, where we
use the term “compression” strictly in the sense of number of states in a
model.

This information is central to the characterization of the difference between
classical and quantum correlations in time, as quantum deterministic models
require no coherence, hence, they can be simulated by classical models of the
same dimension. In fact, as shown in [Spee  _et al._(2020b)Spee, Budroni, and
Gühne], states that produce a different sequence of outcomes with probability
one are orthogonal, hence, a minimal representation can be realized with pure
states and deterministic transitions among them. This quantum model, then,
requires no coherence and can be simulated classically. For this reason, in
the following we simply discuss classical models in the investigation of the
minimal dimension necessary for a deterministic realization of a sequence.

We remark that this is in stark contrast with other models of temporal
correlations, such as the original Leggett-Garg formulation [Leggett and
Garg(1985), Emary  _et al._(2014)Emary, Lambert, and Nori], which assumes
noninvasive measurability, quantum contextuality for sequential measurements
[Kirchmair  _et al._(2009)Kirchmair, Zähringer, Gerritsma, Kleinmann, Gühne,
Cabello, Blatt, and Roos, Gühne  _et al._(2010)Gühne, Kleinmann, Cabello,
Larsson, Kirchmair, Zähringer, Gerritsma, and Roos, Budroni  _et
al._(2021)Budroni, Cabello, Gühne, Kleinmann, and Larsson], which assumes some
form of compatible measurements, or other forms of temporal quantum
correlations assuming projective measurements [Budroni  _et al._(2013)Budroni,
Moroder, Kleinmann, and Gühne, Budroni and Emary(2014), Schild and
Emary(2015), Ringbauer and Chaves(2017), Sohbi  _et al._(2021)Sohbi, Markham,
Kim, and Quintino] or a combination of spatial and temporal correlations
[Gallego  _et al._(2014)Gallego, Würflinger, Chaves, Acín, and Navascués,
Spee(2020), Bowles  _et al._(2020)Bowles, Baccari, and Salavrakos].

Given these considerations, we introduce the following notion.

######  Definition.

(Deterministic Complexity). Given a sequence $\vec{a}$, we define its
_deterministic complexity_ , denoted by $\operatorname{DC}(\vec{a})$ or simply
DC, as the minimal $d$ such that there exists a model $T$ giving
$p(\vec{a}|T,d)=1$.

A trivial upper bound for $\operatorname{DC}$ is given by the sequence length,
i.e., $\operatorname{DC}(\vec{a}^{L})\leq L$. The bound is generally not
tight: it is saturated only in the case of the one-tick sequence, i.e.,
$\operatorname{DC}({\vec{a}_{\rm ot}}^{L})=L$ (see Appendix A) and the
equivalent one obtained by the substitution $0\leftrightarrow 1$. A general
criterion for counting the minimal number of states necessary to realize a
given sequence deterministically has been formulated in Ref. [Spee  _et
al._(2020b)Spee, Budroni, and Gühne]. In simple terms, one may say that two
different steps of a sequence are associated with the same internal state if
“they have the same future”, namely, if they are followed by the same sequence
of outcomes. The minimal number of internal states is the number of different,
or inequivalent, futures. This also give us the intuition as to why the one-
tick sequence is the one with the highest deterministic complexity: each step
$k<L$ is associated with the different future “emit $1$ in $L-k$ steps” (see
also Appendix A). In the following, we present an efficient algorithm to
compute such a minimal number of states for a FA.

We have seen that each deterministic sequence can be realized by transitions
among orthogonal states and that, for a minimal realization, rank-1 states are
sufficient (see Ref. [Spee  _et al._(2020b)Spee, Budroni, and Gühne]). A
simple argument shows that all minimal models are of this form, namely, that
the evolution is always between rank-1 states and never creates a mixed state.
Since, we are discussing transitions among orthogonal blocks, it is sufficient
to consider the classical model.

######  Observation 1.

A deterministic probability for a sequence $\vec{a}$ implies deterministic
state transitions for its minimal (classical) model $T$, with
$d=\operatorname{DC}(\vec{a})$, i.e.,

$p(\vec{a}|T,\operatorname{DC}(\vec{a}))=1\implies[T_{a}]_{ij}\in\\{0,1\\},\;\forall\,i,j,a.$
(3)

###### Proof.

By contradiction, suppose that at the $n$-th transition, $n<L$, instead of
moving deterministically, the automaton transitions to the state $s$ with
probability $q$ or to the state $s^{\prime}$ with probability $(1-q)$. The
total probability, then, can be written as $1=p=qp_{1}+(1-q)p_{2}$, where
$p_{1}$ and $p_{2}$ are the probabilities for the two paths, conditioned on
that probabilistic transition at the $n$-th step. Since $0\leq q\leq 1$ and
$p_{i}\leq 1$, $p=1$ implies $p_{1}=p_{2}=1$. Hence, it is sufficient to
follow the path going through, e.g., $s$ to generate the sequence with
probability $1$. One may, then, simply remove the state $s^{\prime}$ and put
$q=1$, in contradiction with the assumption that the dimension was minimal.
The argument can be applied iteratively, if more than one probabilistic
transition appears. The only remaining case is that of a transition happening
in the last step, i.e., $n=L$, in which case the transition is irrelevant for
the model. In the terminology above, $1=p=p_{1}(q+1-q)$.

Notice that the previous argument uses only the probability over paths in the
state space, thus, it is valid also for the case of machines accepting inputs
as in, e.g., Refs. [Hoffmann  _et al._(2018)Hoffmann, Spee, Gühne, and
Budroni, Budroni  _et al._(2019)Budroni, Fagundes, and Kleinmann, Spee  _et
al._(2020b)Spee, Budroni, and Gühne].

Such deterministic models are referred to as deterministic finite-state
automata (DFA). These DFAs have a special form that allows for an easier
characterization. In such cases, the automata are able to generate with
probability one not only the finite sequences considered, i.e.,
$p(\vec{a}|T,\operatorname{DC}(\vec{a}))=1$, but an infinite family of
sequences. For instance, the sequence $\vec{a}=(0,0,0,1,1,0,1,1,0)$ can be
seen as a truncation of the infinite sequence $\mathtt{00(011)}$, where
$\mathtt{(011)}$ denotes that the subsequence $\mathtt{011}$ is repeated
indefinitely. We call such a description of infinite sequences a _pattern_ ,
and to each pattern corresponds a deterministic model. In this simple example,
the pattern consists of an initial sequence which occurs once, the _tail_
$\mathtt{00}$, and the _cycle_ $\mathtt{(011)}$, which occurs at least once,
while further repetitions may be truncated. Since the state transitions are
deterministic, it is clear that to each output is associated the current state
of the machine and the transition to the subsequent one. This structure is
general: Since the number of states $d$ is finite for $L\geq d$, the system
must at some point transition back to a previously used state and repeat the
sequence thereafter, as in Figure 2. This can be summarized in the following

######  Observation 2.

Every minimal deterministic model is characterized by a tail and a cycle,
which completely describe the structure of the state transitions and generate
a pattern. The minimal number of states needed to generate a pattern is
precisely the length of the pattern.

Note that, due to truncations of the cyclic part, more than one minimal
pattern may describe a given sequence, but all such patterns share the same
length. Clearly, a DFA generating a minimal pattern of length $\ell$ is
minimal if it uses exactly $\ell$ states.

This suggests an algorithm to compute $\operatorname{DC}$ for an arbitrary
sequence $\vec{a}^{L}$: it is enough to compute the length of a minimal
pattern that generates it. Intuitively, for a sequence $\vec{a}^{L}$ its
minimal patterns are characterized by two numbers $l_{1}$ and $l_{2}$,
respectively, the length of the tail and the length of the cycle, such that
$\operatorname{DC}(\vec{a})=l_{1}+l_{2}$. An explicit algorithm to compute
minimal patterns is presented in Appendix A. Here, we present a brief outline.

Algorithm (outline). To find the minimal patterns and the deterministic
complexity of a given sequence $\vec{a}$ of length $L$:

  1. 1.

Assume a pattern length $\ell=1,\dots,L$. To ensure minimality of the pattern,
we test each $\ell$ in increasing order.

  2. 2.

For each $\ell$, assume a tail length $l_{1}=0,\dots,\ell-1$, giving a cycle
length $l_{2}=\ell-l_{1}$.

  3. 3.

If all outcomes $a_{i}$ for $i=\ell+1,\dots,L$ can be interpreted as
repetitions of the cycle subsequence, $(a_{l_{1}+1},\dots,a_{\ell})$, then
$(l_{1},l_{2})$ describes a valid pattern for $\vec{a}$ of length $\ell$, and
thus, $\operatorname{DC}(\vec{a})=\ell$.

  4. 4.

If we also wish to find all patterns compatible with $\vec{a}$, we may
continue checking the remaining $l_{1}$ for the same $\ell$.

In this way, we need to generate and compare at most $L^{2}$ patterns with the
original sequence, corresponding to $O(L^{3})$ operations.

Interestingly, the tail and cycle structure also allows us to compute the
exact number of minimal patterns that can be generated with exactly $\ell$
states, adapting an argument by Nicaud [Nicaud(1999)] for unary automata,
based on two simple conditions: $(i)$ the tail is minimal, and $(ii)$ the
cycle is minimal. The only nontrivial counting corresponds to that of minimal
cycles, which can be mapped to a known combinatoric problem of _primitive
words_ , i.e., strings of symbols $w$ that cannot be written as $w=x^{k}$ for
some $k\geq 2$ [Allouche and Shallit(2003)]. An explicit expression for the
number of minimal patterns length $\ell$ over a $k$-symbol alphabet is given
by

$N_{k}(\ell)=\psi_{k}(\ell)+\sum_{i=1}^{\ell-1}(k-1)k^{i-1}\psi_{k}(\ell-i),$
(4)

where $\psi_{k}(n)=\sum_{d|n}\mu(d)k^{n/d}$ is the number of primitive words
of length $n$ in a $k$-symbol alphabet and $\mu(d)$ is the Möbius function.
The details of the derivation are presented in Appendix A.

In summary, the deterministic complexity of a sequence represents the optimal
“lossless compression” of its finite-state automaton. It provides the
threshold after which quantum systems provide an advantage: namely for “lossy
compression” of a sequence $\vec{a}$, corresponding to
$d<\operatorname{DC}(\vec{a})$. It is also connected to what appears to be a
classical upper bound for this probability, which depends only the pair
$(d,\operatorname{DC}(\vec{a}))$ and can be computed in terms of the one-tick
sequence ${\vec{a}_{\rm ot}}^{\operatorname{DC}(\vec{a})}$. This potential
upper bound is discussed in the next section.

Finally, it is worth commenting on the terminology used. The number of
internal states of an automaton is commonly used as a measure of complexity,
such as _state complexity_ for a regular language [Holzer and Kutrib(2009),
Nicaud(1999)], the _statistical complexity_ associated with an
$\varepsilon$-machine [Shalizi and Crutchfield(2001)], or _automatic
complexity_ [Shallit and Wang(2001)]. By _compression_ of a model, we simply
mean the reduction of its number of internal states. Of course, this
“compression” cannot be interpreted as a compression of the bit-string of
outputs itself, as the description of the model may simply be more expensive,
in terms of memory, than the original sequence. Since the stopping condition
(i.e. the length $L$ of the sequence) is specified _a priori_ , and not
embedded in the automaton, the deterministic complexity as defined herein
possesses different properties with respect to the other notions in the
literature.

##  4 Lossy compression of a classical model

Figure 3: The optimal model found for the sequence $\vec{a}=(0,0,1,0,1,1)$
($\operatorname{DC}(\vec{a})=5$) and $d=4$, which results in
$p=8/27=0.\overline{296}$. Arrow colors were used to help distinguish the $0$
(blue) and $1$ (red) transitions, and labels correspond to their respective
outputs and transition probabilities, e.g., “$1|p=2/3$” denotes an output of 1
with probability $2/3$. The model contains a nontrivial combination of
probabilistic and deterministic transitions. Different sequences can lead to
vastly different models, and the structure of such behaviors are still under
study.

In this section, we investigate the optimal probability with which a sequence
$\vec{a}$ can be generated when $d<\operatorname{DC}(\vec{a})$. In line with
the previous discussion, this procedure can be interpreted as a further
compression of the model, beyond the threshold $d=\operatorname{DC}(\vec{a})$.
By definition, we necessarily have $p<1$ in this case, and therefore we refer
to this as a _lossy compression_ of a model.

###  4.1 Survey of general sequences

The optimal models obtained under such constraints must make nontrivial use of
the memory resources available, which gives rise to complex behaviors and
transitions that are specific for each sequence, as shown in Figure 3 and
Figure 10.

In studying these behaviors, we looked at all $2046$ sequences $\vec{a}^{L}$,
for $L=2,3,\ldots,10$, and all possible realizations in dimensions $d$ such
that $d<\operatorname{DC}(\vec{a}^{L})$. To do so, we analyzed the nonconvex
constrained problem

$\begin{split}\max_{\\{T\\}}\ &p(\vec{a}|T,d)=\pi_{0}T_{a_{1}}T_{a_{2}}\dots
T_{a_{L}}\eta,\\\ \text{subjected to:
}&\sum_{j}\left([T_{0}]_{ij}+[T_{1}]_{ij}\right)=1,\forall\,i,\\\
&[T_{a}]_{ij}\geq 0,\ \forall i,j,\end{split}$ (5)

via gradient-descent methods, in particular, the algorithm Adam [Kingma and
Ba(2014)]. This is possible by transforming the problem into an unconstrained
one, see Appendix C for details.

The results of this general survey highlighted a special property of the one-
tick sequences, which required further investigation. This is described next.

###  4.2 Survey of one-tick sequences

In addition to this extensive search, the one-tick sequences in particular
were also surveyed based on an improvement of the optimal classical models
extensively investigated in Ref. [Budroni  _et al._(2021)Budroni, Vitagliano,
and Woods], both with analytical and numerical methods. There, a specific
model referred to as the _multicyclic model_ was shown to be optimal in some
cases and thought to be optimal in general. Here, we show that this model can
be improved with a slight modification, and in several cases such models
increase the probabilities previously obtained. We term these _enhanced
multicyclic models_ (EMCMs), in analogy to the multicyclic model in Ref.
[Budroni  _et al._(2021)Budroni, Vitagliano, and Woods]. However, the
optimality of these models is still conjectured.

Figure 4: The structure of enhanced multicyclic models, consisting of $n$
identical probabilistic cycle blocks of size $k\in\mathbb{N}$, followed by
$t\geq 0$ deterministic transitions such that $d=nk+t$. The transitions within
each cycle are deterministic. The initial state (not shown) can be any of the
first $k$ states in the first block.

A schematic representation of EMCMs is presented in Figure 4. The model
consists of $n$ blocks of size $k$, each forming its own cycle, followed by
$t\geq 0$ deterministic transitions, such that $d=nk+t$. The transitions
within each cycle block are deterministic. In the last state of each cycle,
the machine can either cycle through the block with probability $q$, or
transition to the next one with probability $1-q$. All these transition are
associated with the output $0$, and once the last state of the last cycle is
reached, if $t>0$, the machine can either cycle again with probability $q$, or
step into the final block with deterministic transitions. At the end of the
final $t$ deterministic transitions, the machine emits the outcome $1$ with
probability $1$, after which the subsequent state transition is irrelevant. In
the special case where $t=0$, and there are no deterministic transitions at
the end, the output $1$ is associated to the forward transition of the last
cycle.

As an example, an EMCM with $k=2,n=2,t=1$ is as following:

$T_{0}=\left[\begin{array}[]{cc|cc|c}0&1&0&0&0\\\ q&0&1-q&0&0\\\ \hline\cr
0&0&0&1&0\\\ 0&0&q&0&1-q\\\ \hline\cr 0&0&0&0&0\\\ \end{array}\right]\ ,\
T_{1}\eta=\left[\begin{array}[]{c}0\\\ 0\\\ 0\\\ 0\\\ 1\end{array}\right]\ .$
(6)

As initial state, one can choose any state within the first block, otherwise
the states of previous blocks are never used, in contradiction with the
assumption of a minimal model. The optimal probability $q$ depends on the
structure of the model and the length of the sequence.

The special case $n=d,k=1,t=0$ corresponds to the one-way model $T_{\rm ow}$
described in [Budroni  _et al._(2021)Budroni, Vitagliano, and Woods], for
which the optimal probability $p({\vec{a}_{\rm ot}}^{L}|T_{\rm ow},d)$, for
$d<L$, is given by the negative binomial distribution:

$F_{\rm
ow}(L,d)=\binom{L-1}{d-1}\left(1-\frac{d}{L}\right)^{L-d}\left(\frac{d}{L}\right)^{d},$
(7)

where the optimal cycle probability is $q=1-d/L$. An EMCM can be described by
just five parameters

$\displaystyle L$ $\displaystyle\text{the sequence length for the model},$ (8)
$\displaystyle n$ $\displaystyle\text{the number of cycle blocks},$
$\displaystyle k$ $\displaystyle\text{size of the cycle blocks},$
$\displaystyle t$ $\displaystyle\text{size of the deterministic block},$
$\displaystyle z$ initial state shift

with $L,n,k,t,z\in\mathbb{N}$, $k>0$, $n=(d-t)/k$, and $z\leq k-1$, where
$z=0$ means we start from the initial state, $z=1$ from the second, and so on.
Note that only $k$ and $z$ are independent parameters of the model, whereas
$n$ and $t$ depend jointly on the model and the sequence. We take Eq. (8) as a
definition of the EMCM.

Denoting the corresponding model as $T^{(L,n,k,t,z)}$, we can compute the
probability for the ${\vec{a}_{\rm ot}}$ sequence as

$\displaystyle p({\vec{a}_{\rm ot}}^{L}|T^{(L,n,k,t,z)},d)=F_{\rm
ow}\left(L^{\prime},d^{\prime}\right)$ (9) $\displaystyle\text{with}\quad
L^{\prime}=\frac{L-t+z}{k},\quad d^{\prime}=\frac{d-t}{k}$

where, in addition to previous constraints, $z$ satisfies
$(L-t+z)/k\in\mathbb{N}$. Given Eq. (9), we may thus optimize directly the
parameters $k$ and $z$ and obtain $(L,n,k,t,z)$ for any $(L,d)$. More details
and intuitions for these results, in particular the meaning of
$(L^{\prime},d^{\prime})$, can be found in Appendix B. We will refer to
optimal EMCMs, for a given context, simply by $E$.

Figure 5: Probabilities of optimal classical models (black dots) for all
$L=10$ sequences and all $d<\operatorname{DC}(\vec{a})$. The red line is the
EMCM upper-bound as described by Conj. 1. For clarity, the points have been
sorted by increasing conjectured bound, then by increasing probability. At the
top, the universal classical bound $1/e$ is shown.

###  4.3 One-tick sequence probability as an upper-bound

An example of the numerical results of both surveys, for the case of $L=10$,
is presented in Figure 5. For general sequences and optimal EMCMs for one-tick
sequences, the results have revealed a striking property of the one-tick
sequences: The optimal probability for the one-tick sequence of length
$\operatorname{DC}(\vec{a})$ at dimension $d$ seems to act as an upper-bound
for all sequences with the same $\operatorname{DC}$ and $d$. While a proof of
this result is yet to be found, our current results led us to formulate the
following conjecture:

######  Conjecture 1.

The optimal probability of any sequence $\vec{a}$, in any classical
$d<\operatorname{DC}(\vec{a})$ scenario, is upper-bounded by the probability
of the one-tick sequence ${\vec{a}_{\rm ot}}^{L}$ with length
$L=\operatorname{DC}(\vec{a})$, using the EMCM on $d$ states, i.e.:

$p(\vec{a}^{L}|T,d)\leq p({\vec{a}_{\rm
ot}}^{\operatorname{DC}(\vec{a}^{L})}|E,d),\quad\forall\,d<\operatorname{DC}(\vec{a}^{L})$
(10)

where $E$ is the optimal EMCM model with $d$ states.

In light of this, and in analogy with $\operatorname{DC}$, we may also define
the $q$-_probabilistic complexity_ of a sequence $\vec{a}$ for $q\in[0,1]$,
denoted as $\operatorname{PC}_{q}(\vec{a})$, as the minimal $d$ such that
there exists a model $T$ giving $p(\vec{a}|T,d)\geq q$. By definition,
$\operatorname{PC}_{1}=\operatorname{DC}$. The previous conjecture, then,
would imply a stronger relation which is presented in the following.

######  Observation 3.

Provided Conj. (1) holds, then it follows that:

  * •

$\operatorname{PC}_{q}(\vec{a}^{L})=\operatorname{DC}(\vec{a}^{L}),\forall\
L,\vec{a}^{L},$ if $q\geq 1/e$,

  * or equivalently,

  * •

$p(\vec{a}^{L}|T,d)<1/e,\forall\ L,\vec{a}^{L},T,$ if
$d<\operatorname{DC}(\vec{a}^{L})$.

###### Proof.

To show that it is sufficient to notice that

$\begin{split}p({\vec{a}_{\rm
ot}}^{L}|E,d)\leq\sup_{L^{\prime},d^{\prime}<L^{\prime}}F_{\rm
ow}(L^{\prime},d^{\prime})=\sup_{L^{\prime}}F_{\rm
ow}(L^{\prime},L^{\prime}-1)\\\
=\lim_{L^{\prime}\rightarrow\infty}\left(1-\frac{1}{L^{\prime}}\right)^{L^{\prime}}=\frac{1}{e}\
,\end{split}$ (11)

where we used Eq. (9) as a value for the EMCM, the fact that $F_{\rm ow}(L,d)$
is monotonically increasing in $d$ and the convergence of
$\left(1-1/L\right)^{L}$ is monotone, i.e., $1/e$ is the upper bound for all
$L$.

In other words, any probabilistic realization with probability $q\geq 1/e$
requires at least the same dimension as a deterministic realization, or
equivalently, there is a universal upper bound probability for the classical
realization of any sequence.

These ideas are concisely shown in Figure 5 and Figure 11. Interestingly, for
many different sequences and different optimal models the same few values
appears as bounds, which are identical to those associated with the one-tick
sequence. This is a hint of a rich structure that needs to be explored with
more refined mathematical tools. For more details see Appendix C.

The code used for the optimizations presented here and the data obtained as a
result are publicly available at the online repository [git()].

##  5 Quantum violations

For the quantum models, one may describe the instruments
$(\mathcal{I}_{0},\mathcal{I}_{1})$ by Kraus operators $K_{a}^{i}$ satisfying
$\sum_{a,i}(K_{a}^{i})^{\dagger}(K_{a}^{i})=\mathbbm{1}$. While the greater
number of degrees of freedom and the non-linear constraints make a general
optimization more difficult to perform and interpret, it is still instructive
to investigate.

###  5.1 Survey of general sequences

For simplicity, we fix the dimension $d$ and the same number $N_{K}$ of Kraus
operators for each instrument $\mathcal{I}_{a}$, such that

$\mathcal{I}_{a}(\cdot)=\sum_{i=1}^{N_{K}}\left(K_{a}^{i}\right)^{\dagger}\cdot\left(K_{a}^{i}\right).$
(12)

For the numerical survey’s quantum models, we looked at all $252$ sequences
$\vec{a}^{L}$, for $L=2,\ldots,7$, and all possible realizations in dimensions
$d$ such that $d<\operatorname{DC}(\vec{a}^{L})$, and for $N_{K}=1,2,3$. The
constrained problem is then given by

$\begin{split}\max_{\mathcal{I}}\
&p(\vec{a}|\mathcal{I},d)=\operatorname{tr}[\rho\
\mathcal{I}_{a_{1}}\circ\mathcal{I}_{a_{2}}\circ\ldots\mathcal{I}_{a_{L}}(\mathbbm{1})].\\\
\text{subjected
to:}&\sum_{a,i}(K_{a}^{i})^{\dagger}(K_{a}^{i})=\mathbbm{1},\end{split}$ (13)

with $\rho=|0\rangle\langle 0|$, which we optimized via the Adam algorithm
through an unconstrained form of the problem. See Appendix E for details.
Quantum advantages over the classical models were observed for all sequences,
and the conjectured universal upper-bound of $1/e$ is violated by many
sequences, but not all of them.

A sample of our results is shown in Figure 6. These results indicate that the
one-tick sequence also outperforms all other sequences in the quantum case,
while also providing the greatest advantage over its classical counterpart.
Surprisingly, the results also display no benefit in using more than a single
Kraus operator, as clearly seen in Figure 6 by the close coincidence of the
results for each $N_{K}$. The optimization algorithm eventually converges with
the various Kraus operators, for each instrument, being merely scalar
multiples of one another.

Naturally, classical models can be simulated by quantum ones, but classical
probabilistic models always transform a pure state into a mixed state, what
requires the use of multiple Kraus operators. With this in mind, a possible
interpretation of this result is the observation that any quantum advantage
would arise from the use of coherences between memory states, and these
coherences are reduced as the state becomes mixed. Thus, these additional
Kraus operators can only lower the performance of the model, by bringing their
behavior closer towards the classical probabilistic behavior.

Figure 6: Probabilities found for $L=6$, $d=\operatorname{DC}(\vec{a})-1$
using the quantum models described, sorted by increasing quantum advantage
over the best classical model found. Note the coincidence of the values
obtained for $N_{K}=1,2,3$, up to numerical error, indicating no advantage in
utilizing more than one Kraus operator. See Appendix E for the full results.

###  5.2 No nontrivial universal quantum bound

A natural question arises of whether a universal bound also appears in the
quantum case, as in the classical scenario. To obtain some intuition on this
problem, we analyzed the ${\vec{a}_{\rm ot}}^{L}$ sequence for the special
case $L=d+1$, i.e., ${d=\operatorname{DC}({\vec{a}_{\rm ot}}^{L})-1}$. Despite
the complexity of the problem, especially in high dimensions, this analysis is
still feasible.

For simplicity, we opt for using a single Kraus operator representation for
each instrument, each with one degree of freedom according to the following
parameterization. To automatically satisfy the constraints, the Kraus
operators are written as the polar decomposition $K_{a}=U_{a}\sqrt{E_{a}}$,
with $E_{a}\geq 0$ and $E_{0}+E_{1}=\mathbbm{1}$. We can choose the operators
$E_{a}$ to be diagonal and tailored for the target sequence (in our case,
${\vec{a}_{\rm ot}}$), based on the optimal classical model found, i.e.,
$E_{a}=\operatorname{diag}(\eta_{a})$, where $\eta_{a}=T_{a}\eta$ for the
optimal $T_{a}$ of the classical model. As in [Budroni  _et al._(2021)Budroni,
Vitagliano, and Woods], the one-parameter unitaries are defined in terms of a
Fourier transform of the computational basis, namely,

$U_{a}=e^{-\mathrm{i}H\theta_{a}},\qquad
H=F\left(\sum_{i=0}^{d-1}k|k\rangle\langle k|\right)F^{\dagger}.$ (14)

The only parameter of the model is then the angle $\theta_{0}$ appearing in
Eq. (14), since $E_{0}$ is fixed to be the diagonal matrix ${\rm
diag}(1,1,\ldots,1,q)$, with $q$ taken as in the optimal classical model
previously described, i.e., $q=1-d/(d+1)$.

Let us formulate the problem in this simplified form. Fixing the dimension by
the condition $d=L-1$ and an initial state $\rho=|0\rangle\langle 0|$, without
loss of generality, the probability can be written as

$\displaystyle p({\vec{a}_{\rm ot}}^{L})$
$\displaystyle=\operatorname{tr}\left[K_{0}^{d}|0\rangle\langle
0|(K_{0}^{\dagger})^{d}E_{1}\right]=\operatorname{tr}\left[|0\rangle\langle
0|(K_{0}^{\dagger})^{d}E_{1}K_{0}^{d}\right]$
$\displaystyle=(1-q)\operatorname{tr}\left[|0\rangle\langle
0|(K_{0}^{\dagger})^{d}|d-1\rangle\langle d-1|K_{0}^{d}\right]$
$\displaystyle=(1-q)\left|\langle d-1|K_{0}^{d}|0\rangle\right|^{2},$ (15)

where we used the cyclicity of the trace, and the definition of $E_{1}$ as
$\mathbbm{1}-E_{0}=(1-q)|d-1\rangle\langle d-1|$. Using the optimal
$E_{0},E_{1}$, corresponding to $q=1-d/L=1-d/(d+1)$, we are left with only one
parameter $\theta_{0}$ to optimize.

For large $d$, the optimal probability is highly sensitive on the value of
$\theta_{0}$, see Appendix E. A good performance, however, is given by the
angle $\theta_{0}=(2\pi/d)(1-1/d)$, suggesting that it is asymptotically
optimal, even if for small $d$ some deviation from the true optimum can be
found. To guess this particular value, we analyzed the action of the unitary
$U_{0}$. We recall that applying $d$ times the unitary $U_{0}$ gives

$\begin{split}U_{0}^{d}=e^{-\mathrm{i}\theta_{0}dH}=e^{-\mathrm{i}\theta_{0}dF\left(\sum_{k=0}^{d-1}k|k\rangle\langle
k|\right)F^{\dagger}}\\\
=F\left(\sum_{k=0}^{d-1}e^{-\mathrm{i}\theta_{0}dk}|k\rangle\langle
k|\right)F^{\dagger},\text{ with }[\,F\,]_{jk}=\frac{1}{\sqrt{d}}e^{\frac{2\pi
i}{d}jk}.\end{split}$ (16)

This gives a transition probability between the last and the first state

$\begin{split}=\left|\langle
d-1|U_{0}^{d}|0\rangle\right|^{2}=\left|\sum_{k=0}^{d-1}[F]_{d-1,k}\,e^{-ikd\theta_{0}}\,[F^{\dagger}]_{k,0}\right|^{2}\\\
=\frac{1}{d^{2}}\left|\sum_{k=0}^{d-1}\exp\left[\frac{2\pi
i}{d}(d-1)k-ikd\theta_{0}\right]\right|^{2}.\end{split}$ (17)

The maximum occurs when all the amplitudes are in phase, which implies the
slowest rotating amplitude ($k=1$) has to reach zero phase, i.e., when
$\frac{2\pi}{d}(d-1)-d\theta_{0}=0$. This gives $\theta_{0}=(2\pi/d)(1-1/d)$,
as desired. The POVM $E_{0}$ has been ignored here, which is at the origin of
the deviation for small $d$. However, from the result of numerical
calculation, see Fig. 7, it seems that our approximation is good enough. See
Appendix E for details.

This behavior is in close parallel with the optimal probability of
transitioning forward in the classical case, $d/(d+1)$, which can be
interpreted as the automaton transitioning $d$ states in $d+1$ steps. In the
quantum case, the angle corresponds to a phase which synchronizes the
amplitudes of all states when transitioning to the last state after $d$ steps.
More details and intuitions on the quantum case are presented in Appendix E.

Figure 7:  Results of the numerical optimization for the the probability of
the ${\vec{a}_{\rm ot}}^{L}$ sequence for the case $L=d+1$ or
${d=\operatorname{DC}({\vec{a}_{\rm ot}}^{L})-1}$, for $d=2,\ldots,500$. The
quantum value seems to converge to the trivial probability bound of $1$, and
these models easily outperform the $1/e$ bound suggested by the classical
scenario. See Appendix E for the full result.

The results of this numerical optimization, shown in Fig. 7, suggest that in
the quantum case probability $1$ can be asymptotically reached. Of course,
this fact cannot be proven rigorously by these numerical optimization methods,
as any concrete computation, in a given dimension, results in a probability
value strictly smaller than $1$. To approach such questions a more
sophisticated construction of quantum models is warranted and shall be the
topic of future research.

##  6 Conclusions and outlook

We explored optimal deterministic and probabilistic realization of a binary
sequence with classical and quantum resources in the framework of finite-state
automata. For deterministic realizations, where the difference between
classical and quantum systems play no role, we introduced the notion of
deterministic complexity quantifying the minimal dimension required, and
provided an algorithm to efficiently compute it, as well as characterized some
of its properties as a complexity measure. In the probabilistic case, i.e.,
$d<\operatorname{DC}$, we explore optimal realizations of sequences up to
length $10$ via the Adam algorithm. This investigation improved a previously
known model for the one-tick sequence probability with the discovery of the
enhanced multicyclic models. Moreover, our results suggest that for any given
sequence $\vec{a}$ and any dimension $d<\operatorname{DC}(\vec{a})$ the
optimal EMCM for the sequence ${\vec{a}_{\rm
ot}}^{\operatorname{DC}(\vec{a})}$ provides an upper bound for the probability
of the original sequence. In particular, by studying the optimal probability
for all EMCMs, one can derive a universal upper bound of $1/e$ for all
classical probabilistic realization ($d<\operatorname{DC}$) of a given
sequence.

In the quantum case, we show how even simple models, with a small amount of
memory resources, are already able to violate such universal classical bound,
and consequently to outperform any classical scenario in which the realization
of a sequence must necessarily be probabilistic. Moreover, the analysis of the
performance of such quantum models for the one-tick sequences in high
dimension, i.e., up to $d=500$, suggests that no analogous of such a
nontrivial universal bound exists in the quantum case.

Notwithstanding two fundamental limitations of our approach, namely, the
analysis of only a finite set of sequences and the use of gradient descent
methods, which for nonconcave problems guarantee only local maxima, we believe
our findings provide a strong support for our conjectures. In fact, the number
of sequences analyzed, counting also their realizations in different
dimensions, was of the order of tens of thousands, all showing a similar
structure of the optimal solution. It seems unlikely that any additional
properties of sequences and models would emerge, which could invalidate these
bounds. At the same time, an indication of the good performance of the
gradient descent methods (in particular, Adam algorithm [Kingma and Ba(2014)])
is that it was able to find very sparse solutions, containing mostly $0$s and
$1$s. For the quantum bound, similarly to the classical case, it would be very
surprising if the limit of the one-tick sequence for $L=d+1$ and
$d\rightarrow\infty$ would converge to some value strictly smaller than one.

Our results stimulate future research in several directions. First, it would
be interesting to understand whether the general upper bound based on the EMCM
fails for longer sequences or if it is valid in general. This will also have
consequence for the universal upper bound for lossy compression of a model.

Without proof of its optimality, it may be possible that for certain longer
sequences a nontrivial model may outperform its respective EMCM. The
optimality of EMCMs themselves for one-tick sequences is also only conjectured
at this time, but search for more general models have shown no evidence that
EMCMs can be outperformed by uneven cycle lengths or independent
probabilities, as described in Appendix B

Moving away from the one-tick sequence, the optimal models for general
sequences have proven to be exceptionally complex, showing a rich nontrivial
behavior (e.g. Figure 3 and Figure 10). Despite this, nearly all optimal
models found by our numerical search seem to fall into a small number of
equivalence classes with same probability, despite the sequences having
various lengths and dimensions, as shown in Figure 5 and Figure 11. The origin
of these results is as of yet unknown, but suggest that tighter bounds on the
conjecture may be established by exploiting additional structures of the
sequences beyond their deterministic complexity.

Our results for the quantum case also indicate that we may restrict our
attention to instruments defined by single Kraus operators, significantly
reducing the search space in an optimization. The question remains open of
whether there are sequences and non-trivial dimensions for which classical and
quantum lossy compression are equally efficient, i.e., if there exist Leggett-
Garg-type temporal inequalities that are not violated by quantum systems, in
analogy to the _Guess-Your-Neighbor’s-Input_ non-local game [Almeida  _et
al._(2010)Almeida, Bancal, Brunner, Acín, Gisin, and Pironio]. Our results
seem to suggest such scenarios are possible (e.g., see Figure 13), but this
requires further investigation.

It is important to remark that the study of temporal correlations in the
framework of finite-state automata is relatively recent, and few techniques
have been so far developed to attack this problem. The numerical results and
conjectures proposed in the present paper indicate new open problems and
research directions that could stimulate the development on new intuitions and
methods to investigate classical and quantum temporal correlations.

Finally, the results and techniques utilized here could be generalized to
arbitrary output alphabets, as well as the inclusion of inputs, which may
reveal new information processing applications for finite automata models. All
of these questions will be the subject of future research.

## Acknowledgements

We thank Ämin Baumeler, Cornelia Spee, and Giuseppe Vitagliano for useful
discussions and comments on the manuscript. This work is supported by the
Austrian Science Fund (FWF) through projects ZK 3 (Zukunftskolleg) and F7113
(BeyondC).

##  Appendix A Deterministic complexity and generating patterns

We start by proving that ${\vec{a}_{\rm ot}}^{L}$ has $\operatorname{DC}=L$.
The proof is based on a general criterion presented in [Spee  _et
al._(2020b)Spee, Budroni, and Gühne]. In simple terms, we may restate it here
by saying that two steps of a sequence, generated by a minimal DFA, are
associated with the same internal state if they “have the same future”, i.e.,
if they generate the same sequence. For the ${\vec{a}_{\rm ot}}^{L}$, the
first state has the future “emit a $1$ exactly after $L$ steps”, the second
state “emit $1$ exactly after $L-1$ steps”, and so on. Since there are no
repetitions, it follows that each step of the sequence must be associated with
a distinct state, giving $\operatorname{DC}=L$.

As we have seen, the DC of a sequence $\vec{a}$ is computed by finding the
minimal DFA which encodes its symbols utilizing a “tail” sequence leading to a
“cycle”. Such a construction can be succinctly specified with a _pattern_ ,
such as $\mathtt{00(101)}$, where the subsequence inside parentheses
corresponds to a subsequence that must occur at least once in full, but may
also repeat with possible truncations. The length of such patterns (in terms
of $0$s and $1$s) corresponds to the desired DC. Thus, it suffices to find the
minimum such patterns for a given sequence. However, patterns may not be
unique, e.g. $\vec{a}=(0,0,1,0,1,0,1,1,0,1)$ can be written as
$\mathtt{00(10101)}$ or $\mathtt{0010(101)}$, but all compatible and minimal
patterns are of the same length.

As pointed out, the “tail” part may have zero length if the entire sequence is
a (possibly truncated) repeating pattern, as in
$\vec{a}=(0,1,0,0,1,0,0,1,0,0,1)$ giving us the pattern $\mathtt{(010)}$,
where the truncation may be observed in the last $0$ of the $4^{\text{th}}$
cycle. Under such analysis, one-tick sequences (and their $0\leftrightarrow 1$
symmetric counterparts) are identified as the unique sequences saturating
$\operatorname{DC}({\vec{a}_{\rm ot}}^{L})=L$ for all sequences of length $L$.
These sequences also have the maximum number ($L$) of potential patterns, as
for example: ${\vec{a}_{\rm ot}}^{5}=(0,0,0,0,1)$ gives
$\mathtt{(00001)}\cong\mathtt{0(0001)}\cong\mathtt{00(001)}\cong\mathtt{000(01)}\cong\mathtt{0000(1)}$.
Algorithm 1, which runs at $O(L^{3})$, can be used to efficiently compute a
sequence’s deterministic complexity, as well as finding all of its minimal
patterns. Notice that the algorithm is not restricted to a binary alphabet,
and works the same way for an arbitrary one.

Algorithm 1 Deterministic Complexity and patterns (DCPatterns). The idea is to
assume the sequences have the form (tail)+(cycle), with respective lengths
$l_{1}$ and $l_{2}$, such that $\operatorname{DC}(\vec{a})=l_{1}+l_{2}$. We
thus test all such patterns counting up from DC, which ensures we find the
minimal-state representation as early as possible.

1:procedure DCPatterns($\vec{a}$)

2: $L\leftarrow\text{Length}(\vec{a})$

3: $patterns\leftarrow\\{\\}$$\triangleright$ We start with an empty list of
patterns.

4: $dc\leftarrow 0$ $\triangleright$ We count from the bottom up in DC,
stopping as early as possible.

5: $found\leftarrow\mathrm{False}$ $\triangleright$ When we find any patterns,
we can stop.

6: while not $found$ do

7: $dc\leftarrow dc+1$

8: for $l_{1}$ in $0,\dots,dc$ do $\triangleright$ For each possible tail
length

9: $l_{2}\leftarrow dc-l_{1}$ $\triangleright$ … assume the rest is a cycle.

10: $match\leftarrow\mathrm{True}$ $\triangleright$ Assume this is a valid
pattern.

11: for $i$ in $0,\dots,(L-dc)$ do $\triangleright$ For every other symbol
beyond DC

12: if $\vec{a}[dc+i]\neq\vec{a}[l_{1}+(i\;\mathrm{mod}\;l_{2})]$ then
$\triangleright$ we test whether it can be extrapolated.

13: $match\leftarrow\mathrm{False}$ $\triangleright$ If it can’t, this pattern
fails and we stop here.

14: break

15: end if

16: end for

17: if $match$ then $\triangleright$ If the pattern matches the entire
sequence…

18: $patterns\leftarrow patterns+\\{(l_{1},l_{2})\\}$$\triangleright$ … we add
the tuple $(l_{1},l_{2})$ to the list of patterns.

19: $found\leftarrow\mathrm{True}$ $\triangleright$ We stop at this $dc$, but
continue searching for patterns.

20: end if

21: end for

22: end while

23: return $dc,patterns$$\triangleright$ Return the optimum $dc$ and the list
of patterns

24:end procedure

###  A.1 The structure of patterns

Arbitrary patterns are not necessarily unique or minimal in the number of
states. As a concrete example, the patterns $\mathtt{00(00)}$ and
$\mathtt{01(0101)}$, of lengths 4 and 6 respectively, are equivalent to the
minimal patterns $\mathtt{(0)}$ and $\mathtt{(01)}$, of lengths 1 and 2.

Interestingly, the space of unique minimal (binary) patterns using exactly $d$
states can be directly related to the unique minimal unary deterministic
finite automata (uDFAs) with exactly $d$ states. An analysis and enumeration
of these uDFAs has been presented by Nicaud [Nicaud(1999)] and Domaratzki _et
al._ [Domaratzki  _et al._(2002)Domaratzki, Kisman, and Shallit]. For
$d=1,2,\dots$ there are $N_{\text{uDFA}}(d)=2,\ 4,\ 12,\ 30,\ 78,\ 180,\
432,\dots$ such uDFAs, and thus unique minimal patterns with exactly $d$
states.

The argument for uDFAs can be easily adapted to our case and can be understood
as follows. For a pattern of length $\ell$ to be minimal, it must satisfy two
obvious conditions: $(i)$ the tail is minimal, and $(ii)$ the cycle is
minimal.

Suppose the “tail” and “cycle” parts of the pattern are given by the strings
(or _words_) $t$ and $c$, respectively, and let $tc$ be their concatenation.
For condition $(i)$ to be valid, the last symbol of $c$ must be different from
the last symbol of $t$, otherwise, one could include the last transition of
the tail into the cycle while removing the last transition of the cycle,
obtaining a pattern of length $\ell-1$ generating the same infinite sequence.
For instance, the pattern $\mathtt{01(001)}$ is not minimal because it could
be reduced to $\mathtt{0(100)}$.

Condition $(ii)$ implies $c$ is a so-called _primitive word_ [Allouche and
Shallit(2003)], i.e., it must be non-empty and not be expressible as $c=w^{m}$
for $w$ a smaller word and $m\in\mathbb{N}$. As a concrete example,
$\mathtt{0101}$ is not a primitive word of length $4$, as it is a repetition
of a shorter word $\mathtt{01}$ of length $2$. Clearly, the number of
primitive words of length $n$ relates to the divisors $d$ of $n$. For a given
alphabet of $k$ symbols, the number of primitive words $\psi_{k}(n)$ of length
$n$ may be computed [Nicaud(1999), Domaratzki  _et al._(2002)Domaratzki,
Kisman, and Shallit, Allouche and Shallit(2003)] in terms of the Möbius
function $\mu(d)$:

$\mu(d)=\begin{cases}0,&\text{if}\ d\ \text{is divisible by some}\ x^{2}>1,\
\text{with}\ x\in\mathbb{N};\\\ (-1)^{s},&\text{if}\ d=p_{1}p_{2}\dots p_{s},\
\text{where}\ p_{i}\ \text{are distinct primes}.\end{cases}$ (18)

The number of primitive words is then given by

$\psi_{k}(n)=\sum_{d|n}\mu(d)k^{n/d}.$ (19)

The expression for the number of minimal patterns of length $\ell$ over a
$k$-symbol alphabet is, thus,

$N_{k}(\ell)=\psi_{k}(\ell)+\sum_{i=1}^{\ell-1}(k-1)k^{i-1}\psi_{k}(\ell-i),$
(20)

where the term $\psi_{k}(\ell)$ counts the number of length-$\ell$ cycles
(i.e., case of no tail), whereas $(k-1)k^{i-1}\psi_{k}(\ell-i)$ counts the
number of length-$(\ell-i)$ cycles together with length-$i$ tails, where one
element of the tail is constrained by condition $(i)$ above, giving the
$(k-1)k^{i-1}$ factor.

##  Appendix B Optimal classical models for one-tick sequences

Given their special role in the problem at hand, the optimal values for one-
tick sequences deserve a more detailed analysis. In Ref. [Budroni  _et
al._(2021)Budroni, Vitagliano, and Woods], a class of models was proposed for
the optimal bounds for the one-tick sequence. We have since found a further
generalization which gives higher values in certain scenarios. Due to their
sparse structure, these models are unusually difficult to obtain through
typical unconstrained numerical optimizations. Given their significantly
higher performance we conjecture these models to be optimal.

###  B.1 One-way, cyclic and multicyclic models

The model presented in Ref. [Budroni  _et al._(2021)Budroni, Vitagliano, and
Woods] was called the multicyclic model which included as special cases the
one-way model and the cyclic model.

The one-way model was found to be generally best for
$d=\operatorname{DC}({\vec{a}_{\rm ot}}^{L})-1=L-1$, whereas the (multi)cyclic
models were found to outperform it for certain
$d<\operatorname{DC}({\vec{a}_{\rm ot}}^{L})-1$. The multicyclic model divides
the states into equal sub-cycles, within each cycle transitions occur
deterministically, except in the last state of each sub-cycle, where the
cycling back or the transitioning to the next cycle (or even the emission of
output $1$ for the last sub-cycle) is probabilistic. These restrictions imply
that the total number of cycles $n$ and the size of the cycles $k$ must obey
$d=nk$.

(a)

(b)

(c)

Figure 8: Different models for the one-tick sequences in $d=4$: (a) one-way
model, (b) cyclic model, (c) multicyclic models. In the one-tick sequence, the
state after the final transition on outcome 1 is irrelevant.

###  B.2 Generalized & enhanced multicyclic models

Figure 9: The structure of generalized multicyclic models, which consist of
splitting the $d$ states into $n$ blocks of various sizes $k_{i}$, each block
corresponding to an internally-deterministic cycle with independent
probability $q_{i}$ of cycling, and $1-q_{i}$ of moving to the next cycle.
Only the last state of the last block has a probability $1-q_{n}$ of
outputting $1$. All optimal models for the one-tick sequence investigated are
of this form.

In this section, we explain the origins of the _enhanced multicyclic model_
(EMCM) as a generalization of the models introduced in Ref. [Budroni  _et
al._(2021)Budroni, Vitagliano, and Woods].

The multicyclic model assumed $d=nk$, but if $d$ and $k$ are coprime, then
either $k=1$ or $k=d$, and we obtain the one-way or cyclic models,
respectively, which can be sub-optimal. To fully generalize such models we
must allow any possible decomposition of the $d$ states into blocks, whose
cycle probabilities may be optimized independently.

In such a _generalized multicyclic model_ (GMCM), the $T_{0}$ transition
matrix consists of $n$ cycles with internal deterministic transitions, and a
probabilistic transition to the initial state of the cycle, with probability
$q_{i}$, or to the first state in the next cycle, with probability $1-q_{i}$,
for the $i$-th cycle. Once the last state is reached, we have a nonzero
probability, i.e., $1-q_{n}$, for the output $1$. An explicit example of
$T_{0}$ is shown in Eq. (21) for a $d=9$ model, and a general structure in
shown in Figure 9. The $T_{1}$ matrix is $T_{1}={\rm
diag}(0,\ldots,0,1-q_{n})$. Notice that since the last transition is
irrelevant, in $T_{1}$ we could have chosen any other position in the last row
for the non-zero entry $1-q_{n}$.

$T_{0}=\left[\begin{array}[]{cccc|ccc|cc}0&1&0&0&0&0&0&0&0\\\
0&0&1&0&0&0&0&0&0\\\ 0&0&0&1&0&0&0&0&0\\\ q_{1}&0&0&0&1-q_{1}&0&0&0&0\\\
\hline\cr 0&0&0&0&0&1&0&0&0\\\ 0&0&0&0&0&0&1&0&0\\\
0&0&0&0&q_{2}&0&0&1-q_{2}&0\\\ \hline\cr 0&0&0&0&0&0&0&0&1\\\
0&0&0&0&0&0&0&q_{3}&0\\\ \end{array}\right]$ (21)

Such a GMCM is defined by several parameters: a _signature_
$\vec{k}=(k_{1},\ldots,k_{n})$ denoting the size of each of the $n$ cycles,
with $k_{i}\in\mathbb{N}^{+}$ and $\sum_{i}k_{i}=d$, and
$\vec{q}=(q_{1},\ldots,q_{n})$ denoting the probability of each cycling
transition to occur, with $0\leq q_{i}<1$ (the strict inequality is important
as having one of the $q_{i}=1$ would give probability zero for the one-tick
sequence).

Note that there are in total $2^{d-1}$ potential signatures for a given $d$,
corresponding to the number of integer compositions111Also known as ordered
partitions. For example, $d=4$ has 8 compositions: $(1,1,1,1)$, $(1,1,2)$,
$(1,2,1)$, $(2,1,1)$, $(2,2)$, $(1,3)$, $(3,1)$, and $(4)$. These compositions
can be easily enumerated. of the number $d$. A priori, none of these could
have been ruled out, so an exhaustive numerical survey of these models was
performed for $L=3,\dots,10$ and $d=1,\dots,L-1$. The optimal models found are
shown in Table 1, where a few structures became apparent: due to optimal
models having the same probabilities for the same block sizes, signatures
largely obey permutation symmetry, but favoring bigger blocks at the
beginning.

$L=3$
---
$d$ | $p({\vec{a}_{\rm ot}}^{L}|G,d)$ | $\vec{k}$
$1$ | $0.148148$ | $(1)_{0}$
$2$ | $0.296296$ | $(1,1)_{0}$

$L=4$
---
$d$ | $p({\vec{a}_{\rm ot}}^{L}|G,d)$ | $\vec{k}$
$1$ | $0.105469$ | $(1)_{0}$
$2$ | $0.250000$ | $(2)_{0}$
$3$ | $0.316406$ | $(1,1,1)_{0}$

$L=5$
---
$d$ | $p({\vec{a}_{\rm ot}}^{L}|G,d)$ | $\vec{k}$
$1$ | $0.081920$ | $(1)_{0}$
$2$ | $0.148148$ | $(2)_{1}$
$3$ | $0.250000$ | $(1,2)^{*}_{0},(3)_{1}$
$4$ | $0.327680$ | $(1,1,1,1)_{0}$

$L=6$
---
$d$ | $p({\vec{a}_{\rm ot}}^{L}|G,d)$ | $\vec{k}$
$1$ | $0.066980$ | $(1)_{0}$
$2$ | $0.148148$ | $(2)_{0}$
$3$ | $0.250000$ | $(3)_{0}$
$4$ | $0.296296$ | $(2,2)_{0}$
$5$ | $0.334898$ | $(1,1,1,1,1)_{0}$

L=7
---
$d$ | $p({\vec{a}_{\rm ot}}^{L}|G,d)$ | $\vec{k}$
$1$ | $0.056653$ | $(1)_{0}$
$2$ | $0.105469$ | $(2)_{1}$
$3$ | $0.148148$ | $(1,2)^{*}_{0},\;(3)_{2}$
$4$ | $0.250000$ | $(1,3)^{*}_{0},\;(4)_{1}$
$5$ | $0.296296$ | $(1,2,2)^{*}_{0}$
$6$ | $0.339917$ | $(1,1,1,1,1,1)_{0}$

L=8
---
$d$ | $p({\vec{a}_{\rm ot}}^{L}|G,d)$ | $\vec{k}$
$1$ | $0.049087$ | $(1)_{0}$
$2$ | $0.105469$ | $(2)_{0}$
$3$ | $0.148148$ | $(3)_{1}$
$4$ | $0.250000$ | $(4)_{0}$
$5$ | $0.250000$ | $(1,1,3)^{*}_{0},\;(2,3)^{*}_{0},\;(4,1)_{1},\;(5)_{2}$
$6$ | $0.316406$ | $(2,2,2)_{0}$
$7$ | $0.343609$ | $(1,1,1,1,1,1,1)_{0}$

L=9
---
$d$ | $p({\vec{a}_{\rm ot}}^{L}|G,d)$ | $\vec{k}$
$1$ | $0.043305$ | $(1)_{0}$
$2$ | $0.081920$ | $(2)_{1}$
$3$ | $0.148148$ | $(3)_{0}$
$4$ | $0.148148$ | $(3,1)_{1},\;(4)_{3}$
$5$ | $0.250000$ | $(1,4)^{*}_{0},\;(5)_{1}$
$6$ | $0.296296$ | $(3,3)_{0}$
$7$ | $0.316406$ | $(1,2,2,2)^{*}_{0}$
$8$ | $0.346439$ | $(1,1,1,1,1,1,1,1)_{0}$

L=10
---
$d$ | $p({\vec{a}_{\rm ot}}^{L}|G,d)$ | $\vec{k}$
$1$ | $0.038742$ | $(1)_{0}$
$2$ | $0.081920$ | $(2)_{0}$
$3$ | $0.105469$ | $(3)_{2}$
$4$ | $0.148148$ | $(4)_{2},\;(1,3)^{*}_{0}$
$5$ | $0.250000$ | $(5)_{0}$
$6$ | $0.250000$ | $(1,1,4)^{*}_{0},\;(2,4)^{*}_{0},\;(5,1)_{1},\;(6)_{2}$
$7$ | $0.296296$ | $(1,3,3)^{*}_{0}$
$8$ | $0.327680$ | $(2,2,2,2)_{0}$
$9$ | $0.348678$ | $(1,1,1,1,1,1,1,1,1)_{0}$

Table 1: All optimal generalized multicyclic models ($G$) for $3\leq L\leq
10$, with their probabilities and signatures $\vec{k}$. Subscripts on
signatures indicate the optimal initial state $z$ (starting from $0$), and an
asterisk indicates that all permutations of the signature were found to be
equivalent. Several non-uniform optimal models appear, improving upon results
in Ref. [Budroni  _et al._(2021)Budroni, Vitagliano, and Woods].

Despite the fact that many signatures of the optimal models found specify non-
uniform cycle lengths (e.g. $(1,2,2)$), in all such cases the smallest cycles
found had $q_{i}=0$, that is, they do not behave like cycles at all, but
instead acting as a series of deterministic transitions. This renders the
models given by $(1,1,4)$ and $(2,4)$ for $L=10$ identical, for instance.
Furthermore, only the largest cycles required $q_{i}>0$, and in all cases the
optimal models display $q_{i}=q_{j}$ if $k_{i}=k_{j}$. Finally, in all cases
where a signature did not satisfy permutation symmetry, the optimal model
contained the deterministic transitions at the end.

This suggests that we can always permute the model so that all deterministic
transitions occur at the end, as a single deterministic block, while all
identical probabilistic cycles occur at the beginning, thus unifying all such
optimal models within the same structure.

This inspires us to the following simplified model: we only need to consider
models of the form $\vec{k}=(k,\dots,k,t)$, where $d=nk+t$, with a number $n$
of $k$-sized blocks, i.e., the vast majority of signatures can be dismissed.
In such models, we always have $n=\left\lfloor d/k\right\rfloor$, and
$t=d-nk$, and an initial state $z=0,\dots,k-1$.

These are the enhanced multicyclic models (EMCMs), as discussed in the main
text, which we conjecture are optimal. They can be fully specified by the
$5$-tuple of parameters $(L,n,k,t,z)$. Table 2 details the parameters
describing various optimal models.

In addition to the comprehensive low-dimension survey of GMCMs which led us to
the EMCMs, we have also investigated some higher-dimensional cases up to
$d=20$, and $20<L\leq 50$ using both GMCMs and the general unrestricted
models, as discussed in Appendix C. In all cases, the best model found was
always in the form of an EMCM, which further supports our claim that EMCMs are
optimal.

L d | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$
---|---|---|---|---|---|---|---|---|---
$2$ | $(1,1,0,0)$ |  |  |  |  |  |  |  |
$3$ | $(1,1,0,0)$ | $(2,1,0,0)$ |  |  |  |  |  |  |
$4$ | $(1,1,0,0)$ | $(1,2,0,0)$ | $(3,1,0,0)$ |  |  |  |  |  |
$5$ | $(1,1,0,0)$ | $(1,2,0,1)$ | $(1,3,0,1)$ | $(4,1,0,0)$ |  |  |  |  |
$6$ | $(1,1,0,0)$ | $(1,2,0,0)$ | $(1,3,0,0)$ | $(2,2,0,0)$ | $(5,1,0,0)$ |  |  |  |
$7$ | $(1,1,0,0)$ | $(1,2,0,1)$ | $(1,3,0,2)$ | $(1,4,0,1)$ | $(2,2,1,0)$ | $(6,1,0,0)$ |  |  |
$8$ | $(1,1,0,0)$ | $(1,2,0,0)$ | $(1,3,0,1)$ | $(1,4,0,0)$ | $(1,5,0,2)$ | $(3,2,0,0)$ | $(7,1,0,0)$ |  |
$9$ | $(1,1,0,0)$ | $(1,2,0,1)$ | $(1,3,0,0)$ | $(1,4,0,3)$ | $(1,5,0,1)$ | $(2,3,0,0)$ | $(3,2,1,0)$ | $(8,1,0,0)$ |
$10$ | $(1,1,0,0)$ | $(1,2,0,0)$ | $(1,3,0,2)$ | $(1,4,0,2)$ | $(1,5,0,0)$ | $(1,6,0,2)$ | $(2,3,1,0)$ | $(4,2,0,0)$ | $(9,1,0,0)$
Table 2: Optimal $(n,k,t,z)$ parameters for enhanced multicyclic models for
various $L$ and $d$. In the case multiple sets of parameters resulted in the
same probability, the set with the smallest $t$ was chosen to highlight the
cases in which the EMCM structure is strictly required. Including $L$, the
five parameters fully specify the probability for a given $(L,d)$.

###  B.3 Reducible sequences and models

Enhanced multicyclic models can be intuitively understood as follows. The
initial shift $z$, can be interpreted as “increasing” the sequence length
(without affecting $d$): since the transitions within each cycle block are
deterministic, starting from the state $z+1$ is equivalent to lengthening the
sequence by $z$ steps and starting on the first state. Similarly, the final
sequence of $t$ deterministic transitions do not alter the probability,
defined by the cycle blocks. Thus, one may “trim” these deterministic
transitions by removing $t$ steps in the sequence together with $t$ states.
The result of both transformations is a multicyclic model starting at the
first state, with the same probability as before.

Finally, each block of size $k$ is equivalent to a single state of the one-way
model of reduced dimension, effectively a time-scaling by a factor of $1/k$.
In other words, the initial state $z$ and the final deterministic block $t$
both work together to perfectly synchronize the cycles with the number of
transitions.

In summary, the optimal probability for an EMCM with $d$ states and one-tick
sequence of length $L$ can then easily be computed by performing the following
transformations, which leave the probability unchanged:

  1. 1.

For a given $L,d$, pick $k,z\in\mathbb{N}$ obeying $1\leq k\leq d$ and $0\leq
z\leq k-1$. Compute $n=\left\lfloor d/k\right\rfloor$ and $t=d-nk$.

  2. 2.

If $t>0$, we may discard the entire final deterministic block, effectively
reducing the dimension, if we also shorten the one-tick sequence by the same
amount $t$ (removing $t$ $0$s). In the process, we incorporate the
deterministic output $1$ into the final probabilistic transition forwards in
the last state of the last cycle. In the above table, this corresponds to
moving diagonally towards the top-left corner by $t$ cells.

  3. 3.

If the initial state is not the first state, i.e. $z>0$, we may increase the
sequence length by adding $z$ $0$s, as the transitions within cycle blocks are
deterministic. This effectively shifts the initial state to the first state of
the first block. This corresponds to moving down the table by $z$ cells.

  4. 4.

Once these transformations have been performed, we have transformed the
problem into the $L\mapsto L-t+z$, $d\mapsto d-t$ scenario with a simple
multicyclic model.

  5. 5.

Finally, since all blocks have the same length $k$ with $k-1$ deterministic
transitions, we may divide both the new $L$ and $d$ by $k$, obtaining a one-
way model for $L\mapsto L^{\prime}=\frac{L-t+z}{k}$ and $d\mapsto
d^{\prime}=\frac{d-t}{k}$.

We then have the model and sequence in an irreducible canonical form with an
alternative $(L^{\prime},d^{\prime})$ of equal probability, and may directly
apply the optimal probability for the one-way model, given by the negative
binomial distribution

$F_{\rm
ow}(L,d)=\binom{L-1}{d-1}\left(1-\frac{d}{L}\right)^{L-d}\left(\frac{d}{L}\right)^{d},$
(22)

where $q=1-d/L$ is the probability of self-transitions and $1-q=d/L$ the
probability of forward transitions.

The only free parameters in such an approach are finding the optimal $k$ and
$z$, which require a straightforward numerical optimization on the order of
$O(d^{2})$.

This optimality of enhanced multicyclic cycles for one-tick sequences, due to
their reducibility, leads to an alternative physical interpretation of these
models. The resulting uniform multicyclic models with cycle lengths $k$
represent a “ _time-scaling symmetry_ ”. Since every $k-1$ transitions occur
deterministically they may be considered as mere _delays_ which introduce no
relevant dynamics to the behavior of the model. The result of this reduction
is a “time scaling” by a factor of $1/k$, which produces an irreducible
version of the model that captures all of its dynamics in the smallest number
of transitions and states.

##  Appendix C Numerical survey of optimal classical models

For arbitrary sequences $\vec{a}$ optimal models are far from obvious, and
must be optimized numerically. In practice we tackle problem in Eq. (5)
numerically, which can only provide us with a lower estimate
$\Omega^{\text{est.}}(\vec{a},d)$ for the true classical upper-bound of a
sequence, $\Omega^{\star}(\vec{a},d)$.

Instead of approaching this constrained problem as is, we convert it into the
equivalent unconstrained problem by defining the real-valued $d\times$d
matrices $B_{0}$ and $B_{1}$. We can convert these into $T_{0}$ and $T_{1}$ in
the constrained problem via the normalization procedure

$[T_{a}]_{ij}=\frac{[B_{a}]_{ij}^{2}}{\sum_{\ell}\left([B_{0}]_{i\ell}^{2}+[B_{1}]_{i\ell}^{2}\right)},\quad\text{for}\,a=0,1.$
(23)

We performed the optimization using the Adam algorithm [Kingma and Ba(2014)]
as implemented in the PyTorch package [Paszke  _et al._(2019)Paszke, Gross,
Massa, Lerer, Bradbury, Chanan, Killeen, Lin, Gimelshein, Antiga, Desmaison,
Kopf, Yang, DeVito, Raison, Tejani, Chilamkurthy, Steiner, Fang, Bai, and
Chintala]. For each sequence $\vec{a}$, 25 initial $B_{a}$ were chosen at
random with entries drawn from the uniform distribution on the symmetric unit
interval $[-1,1]$. We aimed for an accuracy of $10^{-8}$, which seemed
reasonable given the typical numerical fluctuations observed, and an initial
learning rate of $0.005$. The best probability from all samples obtained was
taken as the optimum estimate for the bound for each sequence, and the optimal
model $T$ found was stored for later analysis.

We estimated the optimal models and probabilities
$\Omega^{\text{est.}}(\vec{a},d)$ for all sequences of length $L=3,\dots,10$
and $d=1,2,\dots,\operatorname{DC}(\vec{a})-1$. Since the models are invariant
under exchange in output symbols ($0\leftrightarrow 1$), we may focus on only
half of the sequences by fixing $a_{1}=0$.

The results of our optimizations are shown, in aggregate, in Figure 11, where
we compare the probabilities found for all sequences with the optimal EMCM
probabilities. The models obtained in our numerical survey show a rich and
complex structure, with many nontrivial mixtures of deterministic and
probabilistic transitions (e.g. Figure 3). Figure 10 displays the behavior of
various $d=\operatorname{DC}(\vec{a})-1$ models.

While a deeper understanding of such structures is subject of ongoing
research, the fact all sequences perform worse than the one-tick sequence may
be interpreted as follows: these results show that there is a nontrivial trade
off occurring when models attempt to reach a higher probability with less
resources. The way other sequences switch between $0$ and $1$ multiple times
forces the memory resources to be spread over multiple incompatible
transitions, leading to a worse performance overall.

Figure 10: Optimal models found for $L=3,4,5,6$ sequences, grouped by
decreasing DC, and sorted by decreasing probability. Only
$d=\operatorname{DC}(\vec{a})-1$ cases are shown. The pictorial representation
of the model matrices $(T_{0},T_{1})$ has $0$ entries as white, and $1$ as
black, with intermediate values in gray. Despite the large variety in
structure and sparsity of the models, nearly all sequences fall into similar
equivalence classes with the same probabilities. The one-tick sequence
(possibly truncated to DC) always outperformed the other sequences, acting as
an upper-bound for any $(L,d)$ combination.

##  Appendix D Conjectured upper bounds

All the available data so far seems to confirm the conjecture that one-tick
sequences may be used as upper estimates for optimal use of the $d$ states
available. A graphical representation of our conjecture is shown in Figure 11,
where it is clear that tighter estimates for the bound may still be available,
by identifying additional structures in the sequences and the origin of the
probability equivalence classes, which appear as “plateaus”.

If the conjecture holds and the EMCMs are indeed optimal, this would imply the
existence of a universal maximum probability for any classical model with
$d<\operatorname{DC}(\vec{a})$, given by $1/e$ (blue line at the top of the
plots). This is the limiting probability of the $d=L-1$ one-way model for
$L\to\infty$, given by $p=\lim_{L\to\infty}\left(1-\frac{1}{L}\right)^{L}$.

Given the promising results shown, it remains to be proven that the one-tick
sequence gives the optimal usage of the $d$ states. This is the focus of
ongoing research.

Figure 11: Collected probabilities (black dots) for all sequences $\vec{a}$
for models of all dimensions $d<\operatorname{DC}(\vec{a})$ for various
lengths $L$. Red line is the upper estimate for different $d$ given by
$p({\vec{a}_{\rm ot}}^{\operatorname{DC}(\vec{a})}|E,d)$, based on the
enhanced multicyclic models. For readability the data is sorted by increasing
probability on the EMCM bound, then by the probability obtained numerically.
Blue line is the conjectured $1/e$ bound. The appearance of “plateaus” suggest
the existence of additional structures within sequences, giving rise to a few
equivalence classes.

##  Appendix E Quantum models

The construction of explicit quantum models is a more difficult task. Recall
that in the quantum case transitions are described by the instruments
$\mathcal{I}=(\mathcal{I}_{0},\mathcal{I}_{1})$ in the Heisenberg picture,
i.e., $\mathcal{I}_{a}$ is completely positive (CP) for $a=0,1$ and
$\mathcal{I}_{0}+\mathcal{I}_{1}$ is a unital map. For an initial state $\rho$
on a $d$-dimensional Hilbert space, the probability for a sequence $\vec{a}$
is then $p(\vec{a}|\mathcal{I},d)=\operatorname{tr}[\rho\
\mathcal{I}_{a_{1}}\circ\mathcal{I}_{a_{2}}\circ\ldots\mathcal{I}_{a_{L}}(\mathbbm{1})]$.

We may model this problem numerically by defining the instruments
$\mathcal{I}_{a}$ in terms of their Kraus representation,

$\mathcal{I}_{a}(\cdot)=\sum_{i=1}^{N_{K}}\left(K_{a}^{i}\right)^{\dagger}\cdot\left(K_{a}^{i}\right),$
(24)

with $N_{K}$ the number of Kraus operator for the instrument. For simplicity,
we assume the same number of operators for both instruments. These Kraus
operators must satisfy the Kraus condition

$\sum_{a}\sum_{i=1}^{N_{K}}(K_{a}^{i})(K_{a}^{i})^{\dagger}=\mathbbm{1}.$ (25)

This gives us the following constrained optimization problem:

$\begin{split}\max_{\mathcal{I}}\
&p(\vec{a}|\mathcal{I},d)=\operatorname{tr}[\rho\
\mathcal{I}_{a_{1}}\circ\mathcal{I}_{a_{2}}\circ\ldots\mathcal{I}_{a_{L}}(\mathbbm{1})].\\\
\text{subjected
to:}&\sum_{a,i}(K_{a}^{i})^{\dagger}(K_{a}^{i})=\mathbbm{1}.\end{split}$ (26)

To simplify the optimization, we turn this into an unconstrained problem as
follows. We first define arbitrary $d\times d$ complex matrices $B_{a}^{i}$ as
our optimization parameters, then compute the matrix

$E=\sum_{a,i}(B_{a}^{i})^{\dagger}(B_{a}^{i}),$ (27)

which by construction is positive semidefinite. Let $\lambda_{\text{max}}$ be
the maximum eigenvalue of this matrix. We can now define the (approximate)
Kraus operators by the normalization
$K_{a}^{i}={B_{a}^{i}}/{\sqrt{\lambda_{\text{max}}}}$. This ensures
$E/\lambda_{\text{max}}\leq\mathbbm{1}$.

There is no guarantee that these Kraus operators will satisfy the condition in
Equation 25 exactly, but this is not relevant for our optimization purposes,
as the optimization procedure will always naturally favor
$E/\lambda_{\text{max}}\approx\mathbbm{1}$. This can be interpreted as if our
experiment contained a third potential output, $\perp$, whose instrument
$\mathcal{I}_{\perp}$ corresponds to the missing Kraus operators required to
complete the Kraus condition. Since the output $\perp$ does not occur in the
sequences we are considering, the contribution of $\mathcal{I}_{\perp}$ will
vanish in the optimization of probability for the sequences not containing
$\perp$.

The objective function in the problem now requires computation of the maximal
eigenvalue of $E$ at every evaluation, which is a non-trivial mathematical
operation. This required abandoning PyTorch for a custom implementation of the
Adam algorithm. We fixed a gradient step size of $10^{-6}$, and for the Adam
algorithm, the parameters $\beta_{1}=0.9$, $\beta_{2}=0.999$,
$\epsilon=10^{-8}$, and a learning rate of $0.003$. We performed a numerical
survey for all sequences of length $L=3,\dots,7$, with
$d=1,\dots,\operatorname{DC}(\vec{a})-1$ and $N_{K}=1,2,3$. For every
scenario, we computed $30$ random trials for a fixed $5000$ iterations, and
saved the best models and probabilities found in each set of trials. Some
results are shown in Figure 12, where we omit sequences with trivial models
($d=1$).

Figure 12: Performance of quantum models for sequences (up to the
$0\leftrightarrow 1$ symmetry) of lengths $L=4,\dots,7$, with
$d=\operatorname{DC}(\vec{a})-1\geq 2$. Sequences were sorted by their quantum
performance, and sequences with $\operatorname{DC}(\vec{a})<3$ were omitted.
Figure 13: As above, but for $L=7$ and $d=\operatorname{DC}(\vec{a})-2\geq 2$,
and sequences with $\operatorname{DC}(\vec{a})<4$ omitted. Despite the limited
number of states, the quantum models still outperform their classical
counterparts for most sequences.

As seen in Figure 13, even with two states missing from a sequence’s
Deterministic Complexity, many sequences still manage to exceed the classical
$1/e$ bound. Additionally, despite the inherent differences in behavior from
quantum and classical models, many sequences are shown to have similar
performances in both cases, perhaps indicating scenarios in which quantum
advantages do not exist. Further investigation is required to understand this
behavior.

###  E.1 No nontrivial universal quantum bound

In the following, we discuss the optimization of the probability for the
${\vec{a}_{\rm ot}}^{L}$ sequence for the special case $L=d+1$, i.e.,
${d=\operatorname{DC}({\vec{a}_{\rm ot}}^{L})-1}$ and the model described
above. This optimization was performed in search for an analogous universal
quantum bound as suggested in the classical case.

To make the discussion self-contained, let us recall some equations from the
main text. For $d=L-1$ and an initial state $\rho=|0\rangle\langle 0|$, the
probability can be written as

$\displaystyle p({\vec{a}_{\rm ot}}^{L})$
$\displaystyle=\operatorname{tr}\left[K_{0}^{d}|0\rangle\langle
0|(K_{0}^{\dagger})^{d}E_{1}\right]=\operatorname{tr}\left[|0\rangle\langle
0|(K_{0}^{\dagger})^{d}E_{1}K_{0}^{d}\right]$
$\displaystyle=(1-q)\operatorname{tr}\left[|0\rangle\langle
0|(K_{0}^{\dagger})^{d}|d-1\rangle\langle
d-1|K_{0}^{d}\right]=(1-q)\left|\langle d-1|K_{0}^{d}|0\rangle\right|^{2}.$
(28)

For a fixed $d$, the probability as a function of $\theta_{0}$ is
characterized by a series of $d$ equally-spaced peaks, which become sharper
with increasing $d$ (Figure 14), indicating that the optimal value requires
fine-tuning.

Figure 14: The probability $p(\theta_{0}|d)$ of the quantum one-way model for
increasing $d$. The various peaks become increasingly sharp for higher
dimensions. The value $\theta_{0}=(2\pi/d)(1-1/d)$ is shown, which appears to
be asymptotically optimal.

The location of the first peak, which is always optimal, can be estimated by
ignoring the effect $E_{0}$, i.e., $E_{0}=\mathbbm{1}$ and simply using
$K_{0}=U_{0}$. In this case, we obtain

$U_{0}^{d}=e^{-\mathrm{i}Hd\theta_{0}}=Fe^{-\mathrm{i}Dd\theta_{0}}F^{\dagger},\quad\text{with}\;D=\operatorname{diag}(0,1,\dots,d-1).$
(29)

The action of the unitary $U_{0}^{d}$ can, then, be computed as

$\left|\langle
d-1|U_{0}^{d}|0\rangle\right|^{2}=\left|\sum_{k=0}^{d-1}[F]_{d-1,k}\,e^{-ikd\theta_{0}}\,[F^{\dagger}]_{k,0}\right|^{2}=\frac{1}{d^{2}}\left|\sum_{k=0}^{d-1}\exp\left[\frac{2\pi
i}{d}(d-1)k-ikd\theta_{0}\right]\right|^{2}.$ (30)

As stated in the main text, the maximum occurs when all the amplitudes are in
phase, which implies the slowest rotating amplitude ($k=1$) has to reach zero
phase, i.e., when $\frac{2\pi}{d}(d-1)-d\theta_{0}=0$, giving
$\theta_{0}=(2\pi/d)(1-1/d)$, as desired.

This simplification made the problem tractable, namely, we were able to
compute the probability for high dimension, without the need of an
optimization over the parameters $\theta_{0}$ and $q$. This result, however,
slightly deviates from the true optimal $\theta_{0}$ for small $d$. For large
$d$, it is asymptotically close to the true optimal. The optimal probability
tends towards $1$ as the dimension (and the length of the sequence) increases
(Figure 7), suggesting that there is no nontrivial quantum upper bound,
strictly smaller than $1$, in the quantum case.

###  E.2 Comparison between classical and quantum one-way models

Figure 15: The overall behavior of classical and quantum one-way models,
showing the evolution of the probability distributions over the $d$ states. In
this diagram, each column represents the states at a given time step in the
sequence, starting from the left with $a_{1}=0$ and ending at the right with
$a_{L}=1$. The first state is at the top. In the quantum case, the
distribution corresponds to the diagonal entries in its density matrix. White
corresponds to zero probability, black to $1$.

The above results suggest an interesting comparison and intuition between the
classical and quantum behaviors in these one-way models.

In the classical case, each transition produces a statistical mixture of
states, in such a way that the average behavior is the machine transitioning
forward $d$ states after $d+1$ transitions, introducing a delay of one state
at the end of the sequence. These transitions always result in a spreading of
the probability over many states. In the quantum case, the dynamics is
governed by the unitary, which produces a coherent superposition of states.
The machine is still transitioning forward $d$ states after $d+1$ transitions,
but the coherence allows the probability to concentrate at the final state
after an initial spread.

The two behaviors are shown in Figure 15, where the “concentration” of
probability can be observed in the quantum case.

## References

  * [Markiewicz  _et al._(2014)Markiewicz, Przysieżna, Brierley, and Paterek] M. Markiewicz, A. Przysieżna, S. Brierley, and T. Paterek, Genuinely multipoint temporal quantum correlations and universal measurement-based quantum computing, Phys. Rev. A 89, 062319 (2014).
  * [Zurel  _et al._(2020)Zurel, Okay, and Raussendorf] M. Zurel, C. Okay, and R. Raussendorf, Hidden variable model for universal quantum computation with magic states on qubits, Phys. Rev. Lett. 125, 260404 (2020).
  * [Wiesner(1983)] S. Wiesner, Conjugate coding, ACM Sigact News 15, 78 (1983).
  * [Ambainis  _et al._(1999)Ambainis, Nayak, Ta-Shma, and Vazirani] A. Ambainis, A. Nayak, A. Ta-Shma, and U. Vazirani, Dense quantum coding and a lower bound for 1-way quantum automata, in  _Proceedings of the thirty-first annual ACM symposium on Theory of computing_ (1999) pp. 376–383.
  * [Ambainis  _et al._(2002)Ambainis, Nayak, Ta-Shma, and Vazirani] A. Ambainis, A. Nayak, A. Ta-Shma, and U. Vazirani, Dense quantum coding and quantum finite automata, Journal of the ACM (JACM) 49, 496 (2002).
  * [Bowles  _et al._(2015)Bowles, Brunner, and Pawłowski] J. Bowles, N. Brunner, and M. Pawłowski, Testing dimension and nonclassicality in communication networks, Phys. Rev. A 92, 022351 (2015).
  * [Aguilar  _et al._(2018)Aguilar, Farkas, Martínez, Alvarado, Cariñe, Xavier, Barra, Cañas, Pawłowski, and Lima] E. A. Aguilar, M. Farkas, D. Martínez, M. Alvarado, J. Cariñe, G. B. Xavier, J. F. Barra, G. Cañas, M. Pawłowski, and G. Lima, Certifying an irreducible 1024-dimensional photonic state using refined dimension witnesses, Phys. Rev. Lett. 120, 230503 (2018).
  * [Miklin  _et al._(2020)Miklin, Borkała, and Pawłowski] N. Miklin, J. J. Borkała, and M. Pawłowski, Semi-device-independent self-testing of unsharp measurements, Phys. Rev. Research 2, 033014 (2020).
  * [Kleinmann  _et al._(2011)Kleinmann, Gühne, Portillo, Åke Larsson, and Cabello] M. Kleinmann, O. Gühne, J. R. Portillo, J. Åke Larsson, and A. Cabello, Memory cost of quantum contextuality, New J. Phys. 13, 113011 (2011).
  * [Fagundes and Kleinmann(2017)] G. Fagundes and M. Kleinmann, Memory cost for simulating all quantum correlations from the peres–mermin scenario, J. Phys. A 50, 325302 (2017).
  * [Garner  _et al._(2017)Garner, Liu, Thompson, Vedral, and Gu] A. J. P. Garner, Q. Liu, J. Thompson, V. Vedral, and M. Gu, Provably unbounded memory advantage in stochastic simulation using quantum mechanics, New J. Phys. 19, 103009 (2017).
  * [Elliott and Gu(2018)] T. J. Elliott and M. Gu, Superior memory efficiency of quantum devices for the simulation of continuous-time stochastic processes, npj Quantum Information 4, 1 (2018).
  * [Elliott  _et al._(2020)Elliott, Yang, Binder, Garner, Thompson, and Gu] T. J. Elliott, C. Yang, F. C. Binder, A. J. P. Garner, J. Thompson, and M. Gu, Extreme dimensionality reduction with quantum modeling, Phys. Rev. Lett. 125, 260501 (2020).
  * [Spee(2020)] C. Spee, Certifying the purity of quantum states with temporal correlations, Phys. Rev. A 102, 012420 (2020).
  * [Erker  _et al._(2017)Erker, Mitchison, Silva, Woods, Brunner, and Huber] P. Erker, M. T. Mitchison, R. Silva, M. P. Woods, N. Brunner, and M. Huber, Autonomous quantum clocks: Does thermodynamics limit our ability to measure time?, Phys. Rev. X 7, 031022 (2017).
  * [Woods  _et al._(2018)Woods, Silva, Pütz, Stupar, and Renner] M. P. Woods, R. Silva, G. Pütz, S. Stupar, and R. Renner, Quantum clocks are more accurate than classical ones, arXiv (2018), arXiv:1806.00491 [quant-ph] .
  * [Woods(2021)] M. P. Woods, Autonomous Ticking Clocks from Axiomatic Principles, Quantum 5, 381 (2021).
  * [Schwarzhans  _et al._(2021)Schwarzhans, Lock, Erker, Friis, and Huber] E. Schwarzhans, M. P. E. Lock, P. Erker, N. Friis, and M. Huber, Autonomous temporal probability concentration: Clockworks and the second law of thermodynamics, Phys. Rev. X 11, 011046 (2021).
  * [Leggett and Garg(1985)] A. J. Leggett and A. Garg, Quantum mechanics versus macroscopic realism: Is the flux there when nobody looks?, Phys. Rev. Lett. 54, 857 (1985).
  * [Emary  _et al._(2014)Emary, Lambert, and Nori] C. Emary, N. Lambert, and F. Nori, Leggett–Garg inequalities, Rep. Prog. Phys. 77, 016001 (2014).
  * [Bell(1964)] J. S. Bell, On the Einstein-Podolsky-Rosen paradox, Physics 1, 195 10.1103/PhysicsPhysiqueFizika.1.195 (1964).
  * [Brunner  _et al._(2014)Brunner, Cavalcanti, Pironio, Scarani, and Wehner] N. Brunner, D. Cavalcanti, S. Pironio, V. Scarani, and S. Wehner, Bell nonlocality, Rev. Mod. Phys. 86, 419 (2014).
  * [Wilde and Mizel(2012)] M. M. Wilde and A. Mizel, Addressing the clumsiness loophole in a Leggett-Garg test of macrorealism, Found. Phys. 42, 256 (2012).
  * [Budroni  _et al._(2015)Budroni, Vitagliano, Colangelo, Sewell, Gühne, Tóth, and Mitchell] C. Budroni, G. Vitagliano, G. Colangelo, R. J. Sewell, O. Gühne, G. Tóth, and M. W. Mitchell, Quantum nondemolition measurement enables macroscopic leggett-garg tests, Phys. Rev. Lett. 115, 200403 (2015).
  * [Halliwell(2016)] J. J. Halliwell, Leggett-Garg inequalities and no-signaling in time: A quasiprobability approach, Phys. Rev. A 93, 022123 (2016).
  * [Knee  _et al._(2016)Knee, Kakuyanagi, Yeh, Matsuzaki, Toida, Yamaguchi, Saito, Leggett, and Munro] G. C. Knee, K. Kakuyanagi, M.-C. Yeh, Y. Matsuzaki, H. Toida, H. Yamaguchi, S. Saito, A. J. Leggett, and W. J. Munro, A strict experimental test of macroscopic realism in a superconducting flux qubit, Nat. Commun. 7, 13253 (2016).
  * [Emary(2017)] C. Emary, Ambiguous measurements, signaling, and violations of Leggett-Garg inequalities, Phys. Rev. A 96, 042102 (2017).
  * [Uola  _et al._(2019)Uola, Vitagliano, and Budroni] R. Uola, G. Vitagliano, and C. Budroni, Leggett-Garg macrorealism and the quantum nondisturbance conditions, Phys. Rev. A 100, 042117 (2019).
  * [Budroni  _et al._(2019)Budroni, Fagundes, and Kleinmann] C. Budroni, G. Fagundes, and M. Kleinmann, Memory cost of temporal correlations, New J. Phys. 21, 093018 (2019).
  * [Fritz(2010)] T. Fritz, Quantum correlations in the temporal clauser–horne–shimony–holt (chsh) scenario, New J. Phys. 12, 083055 (2010).
  * [Hoffmann  _et al._(2018)Hoffmann, Spee, Gühne, and Budroni] J. Hoffmann, C. Spee, O. Gühne, and C. Budroni, Structure of temporal correlations of a qubit, New J. Phys. 20, 102001 (2018).
  * [Spee  _et al._(2020a)Spee, Siebeneich, Gloger, Kaufmann, Johanning, Kleinmann, Wunderlich, and Gühne] C. Spee, H. Siebeneich, T. F. Gloger, P. Kaufmann, M. Johanning, M. Kleinmann, C. Wunderlich, and O. Gühne, Genuine temporal correlations can certify the quantum dimension, New J. Phys. 22, 023028 (2020a).
  * [Spee  _et al._(2020b)Spee, Budroni, and Gühne] C. Spee, C. Budroni, and O. Gühne, Simulating extremal temporal correlations, New Journal of Physics 22, 103037 (2020b).
  * [Mao  _et al._(2020)Mao, Spee, Xu, and Gühne] Y. Mao, C. Spee, Z.-P. Xu, and O. Gühne, Structure of dimension-bounded temporal correlations, arXiv (2020), arXiv:2005.13964 [quant-ph] .
  * [Budroni  _et al._(2021)Budroni, Vitagliano, and Woods] C. Budroni, G. Vitagliano, and M. P. Woods, Ticking-clock performance enhanced by nonclassical temporal correlations, Phys. Rev. Research 3, 033051 (2021).
  * [Rabin(1963)] M. O. Rabin, Probabilistic automata, Information and Control 6, 230 (1963).
  * [Paz(1971)] A. Paz,  _Introduction to probabilistic automata_ (Academic Press, 1971).
  * [Shallit and Wang(2001)] J. Shallit and M.-W. Wang, Automatic complexity of strings, Journal of Automata, Language and Combinatorics 6, 537 (2001).
  * [Kirchmair  _et al._(2009)Kirchmair, Zähringer, Gerritsma, Kleinmann, Gühne, Cabello, Blatt, and Roos] G. Kirchmair, F. Zähringer, R. Gerritsma, M. Kleinmann, O. Gühne, A. Cabello, R. Blatt, and C. F. Roos, State-independent experimental test of quantum contextuality, Nature (London) 460, 494 (2009).
  * [Gühne  _et al._(2010)Gühne, Kleinmann, Cabello, Larsson, Kirchmair, Zähringer, Gerritsma, and Roos] O. Gühne, M. Kleinmann, A. Cabello, J.-Å. Larsson, G. Kirchmair, F. Zähringer, R. Gerritsma, and C. F. Roos, Compatibility and noncontextuality for sequential measurements, Phys. Rev. A 81, 022121 (2010).
  * [Budroni  _et al._(2021)Budroni, Cabello, Gühne, Kleinmann, and Larsson] C. Budroni, A. Cabello, O. Gühne, M. Kleinmann, and J.-Å. Larsson, Quantum Contextuality, arXiv (2021), arXiv:2102.13036 [quant-ph] .
  * [Budroni  _et al._(2013)Budroni, Moroder, Kleinmann, and Gühne] C. Budroni, T. Moroder, M. Kleinmann, and O. Gühne, Bounding temporal quantum correlations, Phys. Rev. Lett. 111, 020403 (2013).
  * [Budroni and Emary(2014)] C. Budroni and C. Emary, Temporal quantum correlations and Leggett-Garg inequalities in multilevel systems, Phys. Rev. Lett. 113, 050401 (2014).
  * [Schild and Emary(2015)] G. Schild and C. Emary, Maximum violations of the quantum-witness equality, Phys. Rev. A 92, 032101 (2015).
  * [Ringbauer and Chaves(2017)] M. Ringbauer and R. Chaves, Probing the non-classicality of temporal correlations, Quantum 1, 35 (2017).
  * [Sohbi  _et al._(2021)Sohbi, Markham, Kim, and Quintino] A. Sohbi, D. Markham, J. Kim, and M. T. Quintino, Certifying dimension of quantum systems by sequential projective measurements, Quantum 5, 472 (2021).
  * [Gallego  _et al._(2014)Gallego, Würflinger, Chaves, Acín, and Navascués] R. Gallego, L. E. Würflinger, R. Chaves, A. Acín, and M. Navascués, Nonlocality in sequential correlation scenarios, New Journal of Physics 16, 033037 (2014).
  * [Spee(2020)] C. Spee, Signaling between time steps prohibits nonlocality beyond hidden nonlocality, arXiv (2020), arXiv:2011.12774 [quant-ph] .
  * [Bowles  _et al._(2020)Bowles, Baccari, and Salavrakos] J. Bowles, F. Baccari, and A. Salavrakos, Bounding sets of sequential quantum correlations and device-independent randomness certification, Quantum 4, 344 (2020).
  * [Nicaud(1999)] C. Nicaud, Average state complexity of operations on unary automata, in  _Mathematical Foundations of Computer Science 1999_, edited by M. Kutyłowski, L. Pacholski, and T. Wierzbicki (Springer Berlin Heidelberg, Berlin, Heidelberg, 1999) pp. 231–240.
  * [Allouche and Shallit(2003)] J.-P. Allouche and J. Shallit,  _Automatic sequences: theory, applications, generalizations_ (Cambridge University Press, 2003).
  * [Holzer and Kutrib(2009)] M. Holzer and M. Kutrib, Nondeterministic finite automata — recent results on the descriptional and computational complexity, International Journal of Foundations of Computer Science 20, 563 (2009).
  * [Shalizi and Crutchfield(2001)] C. R. Shalizi and J. P. Crutchfield, Computational mechanics: Pattern and prediction, structure and simplicity, Journal of statistical physics 104, 817 (2001).
  * [Kingma and Ba(2014)] D. P. Kingma and J. Ba, Adam: A Method for Stochastic Optimization, arXiv (2014), arXiv:1412.6980 [cs.LG] .
  * [git()] Online repository containing the code used for the optimizations and the data obtained as a result. https://github.com/1ucasvb-research/TCSMS.
  * [Almeida  _et al._(2010)Almeida, Bancal, Brunner, Acín, Gisin, and Pironio] M. L. Almeida, J.-D. Bancal, N. Brunner, A. Acín, N. Gisin, and S. Pironio, Guess your neighbor’s input: A multipartite nonlocal game with no quantum advantage, Phys. Rev. Lett. 104, 230404 (2010).
  * [Domaratzki  _et al._(2002)Domaratzki, Kisman, and Shallit] M. Domaratzki, D. Kisman, and J. Shallit, On the number of distinct languages accepted by finite automata with n states, Journal of Automata, Languages and Combinatorics 7, 469 (2002).
  * [Paszke  _et al._(2019)Paszke, Gross, Massa, Lerer, Bradbury, Chanan, Killeen, Lin, Gimelshein, Antiga, Desmaison, Kopf, Yang, DeVito, Raison, Tejani, Chilamkurthy, Steiner, Fang, Bai, and Chintala] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf, E. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala, Pytorch: An imperative style, high-performance deep learning library, in  _Advances in Neural Information Processing Systems 32_ (Curran Associates, Inc., 2019) pp. 8024–8035.