# Causal Asymmetry of Classical and Quantum Autonomous Agents

Spiros Kechrimparis<EMAIL_ADDRESS>School of Computational Sciences,
Korea Institute for Advanced Study, Seoul 02455, South Korea  Nanyang Quantum
Hub, School of Physical and Mathematical Sciences, Nanyang Technological
University, 637371, Singapore.  Mile Gu<EMAIL_ADDRESS>Nanyang
Quantum Hub, School of Physical and Mathematical Sciences, Nanyang
Technological University, 637371, Singapore.  Centre for Quantum Technologies,
National University of Singapore, 3 Science Drive 2, 117543, Singapore.
MajuLab, CNRS-UNS-NUS-NTU International Joint Research Unit, UMI 3654, 117543,
Singapore.  Hyukjoon Kwon<EMAIL_ADDRESS>School of Computational Sciences,
Korea Institute for Advanced Study, Seoul 02455, South Korea

###### Abstract

Why is it that a ticking clock typically becomes less accurate when subject to
outside noise but rarely the reverse? Here, we formalize this phenomenon by
introducing _process causal asymmetry_ – a fundamental difference in the
amount of past information an autonomous agent must track to transform one
stochastic process to another over an agent that transforms in the opposite
direction. We then illustrate that this asymmetry can paradoxically be
reversed when agents possess a quantum memory. Thus, the spontaneous direction
in which processes get ‘simpler’ may be different, depending on whether
quantum information processing is allowed or not.

Suppose we observe two streams of data: the first, $\mathcal{A}=\ldots
010101\ldots$, is an alternating stream of $0$ and $1$s, generated by a binary
switch that flips each time-step; the second, $\mathcal{B}=\ldots
01230123\ldots$, represents configurations of a revolving object that
completes a full cycle every four time-steps. We are asked to decide between
two possible causal explanations: (1) $\mathcal{A}$ causes $\mathcal{B}$, such
that each $b_{t}$ of $\mathcal{B}$ at time $t$ is generated by some channel
acting on $a_{t}$ or (2) $\mathcal{B}$ causes $\mathcal{A}$ such that the
input and output of this channel are reversed. While we cannot conclusively
rule out either causal explanation, the two causal structures are not
symmetric. Let $a_{t}$ and $b_{t}$ be the respective outputs of $\mathcal{A}$
and $\mathcal{B}$ at time $t$. A simple channel channel enacting
$a_{t}=b_{t}\mod 2$ transforms $\mathcal{B}$ to $\mathcal{A}$. This channel is
memoryless and time-independent. Any agent implementing it does not need to
adapt its action to $a_{t}$ or $b_{t}$ at times prior to $t$. In contrast,
transforming from $\mathcal{A}$ to $\mathcal{B}$ is more complex. An agent
that sees $a_{t}=0$ cannot decide whether $b_{t}=0$ or $b_{t}=2$ without at
least $1$ bit of information about the past (see Fig. 1).

$\mathcal{A}=\ldots 01010101\ldots$$\mathcal{B}=\ldots
01230123\ldots$$a_{t}$$a_{t}$$b_{t}$$b_{t}$

$m_{0}$$m_{1}$$0|0:1$$2|0:1$$1|1:1$$3|1:1$

$\mathcal{T}$

$m^{\prime}_{0}$$0|0:1$$1|1:1$$0|2:1$$1|3:1$

$\hat{\mathcal{T}}$

Figure 1: Transformation between processes $\mathcal{A}$ and $\mathcal{B}$. To
transform $\mathcal{A}$ to $\mathcal{B}$, memory is necessary, and the memory
state $m_{j}$ is updated as $m_{j}\leftarrow m_{(j+x)\mod 2}$ for the input
bit $x$ while the output is generated as $y=2j+x$. On the other hand, to
transform $\mathcal{B}$ to $\mathcal{A}$, the output is obtained as $y=x\mod
2$, and thus no memory is necessary. Inside the boxes, we show the finite
state machine presentation of the input-output processes. Each transition
emitting output $y$ when receiving input $x$, which occurs with probability
$p$, is represented as $y|x:p$.

In complexity science, each piece of information a machine must track is
considered to be a necessary cause of future behaviour [1, 2]. As such, our
thought experiment highlights a variant of _causal asymmetry_ \- causal
explanations in one direction appear more natural than the other [3, 4, 5].
Here, $\mathcal{A}$ can be thought of as a rudimentary discrete-time clock
that tracks 1-bit of data about the current time, while $\mathcal{B}$ is a
slightly more sophisticated clock that tracks $2$-bits [6, 7]. Causal
asymmetry then represents the intuition that it is easier to degrade a clock
than to make it more accurate. Adding noise needs only a memoryless noise
channel while reversing this requires adaptive operations.

The goal of this article is to (1) formalize the above intuitions using causal
transducers – a mathematical description of autonomous agents that transform
one stochastic process to another [2] and (2) determine how quantum-enhanced
agents can change what causal direction we consider to be more natural. This
involves defining _process causal asymmetry_ as the difference in the amount
of past data an agent must track to transform $\mathcal{A}$ to $\mathcal{B}$
versus from $\mathcal{B}$ to $\mathcal{A}$; and examining how this difference
changes when we deploy agents with quantum memory [8]. We make a surprising
observation: quantum processing can reverse causal asymmetry, such that
$\mathcal{A}$ causing $\mathcal{B}$ may be more natural when considering only
classical agents, while the reverse is the more natural one when quantum
agents are allowed.

Framework.— We adopt computational mechanics to describe stochastic processes
and agents that transform them from one to another [9, 1, 2]. Formally, a
stochastic process $\mathcal{A}$ can be described by a bi-infinite sequence of
random variables $\overleftrightarrow{X}=\ldots X_{-1}X_{0}X_{1}\ldots$, where
$X_{t}$ denotes the probability the process emits $x_{t}\in\mathcal{X}$ at
time $t$. Each instance of a process has a particular past
$\overleftarrow{x}=\ldots x_{-1}x_{0}$, and a conditional future governed by
$\overrightarrow{X}|_{\overleftarrow{x}}$. Here we consider stationary
stochastic processes, such that $\overleftrightarrow{X}$ is time-translation
invariant.

Autonomous agents are finite-state machines that can transform one stochastic
process to another [2, 8]. At each time-step $t$, an agent accepts input
$x_{t}\in\mathcal{X}$ and emits a corresponding output $y_{t}\in\mathcal{Y}$.
Taking the present as $t=0$, the agent then experiences a history
$\overleftarrow{z}={(\overleftarrow{x},\overleftarrow{y})}$. The operational
behaviour of the agent is defined by an _input-output process_ , a family of
random variables
${\overrightarrow{Y}|_{\overrightarrow{x},\overleftarrow{z}}}$, which governs
the probability the agent will emit $\overrightarrow{y}=y_{1}y_{2}\ldots$ when
given future inputs $\overrightarrow{x}=x_{1}x_{2}\ldots$. We say that an
agent transforms $\mathcal{A}$ to $\mathcal{B}$ when, given inputs sampled
from $\mathcal{A}$, its corresponding outputs $\overleftrightarrow{Y}$ align
with $\mathcal{B}$.

When
$\overrightarrow{Y}|{\overrightarrow{x},\overleftarrow{z}}=\overrightarrow{Y}|{\overrightarrow{x}}$
is history independent, the agent is _non-adaptive_. This represents the
simplest input-output process. Agents implementing such transforms can be
_memoryless_. They just need to apply the same transformation on $x_{t}$ at
each time. The set of possible transforms, however, is extremely limited.
There is no capability to generate temporal structure, such as converting a
sequence of $\mathcal{A}=\ldots 0101\ldots$ to $\mathcal{B}=\ldots
01230123\ldots$. To do this would require tracking some information about
$\overleftarrow{z}$. That is, the agent must possess an internal memory
$\mathcal{M}$ that is configured in some state
$s_{\overleftarrow{z}}=k(\overleftarrow{z})$, such that there is a systematic
method to sample from
$\overrightarrow{Y}|_{\overrightarrow{x},\overleftarrow{z}}$ for each possible
$\overrightarrow{x}$ and $\overleftarrow{z}$. Here, we assume that all our
agents are causal, such that $\mathcal{M}$ does not contain any oracular
information - information about the future that is not already contained in
the past [10, 11, 5].

To quantify the memory cost of the transformation, we make use of
$\epsilon$-transducers, the provably optimal classical agents for executing a
given input-output process [2]. An $\epsilon$-transducer operates on the
rationale that an agent needs not distinguish two histories
$\overleftarrow{z}$ and $\overleftarrow{z}^{\prime}$ if its future decisions
never depend on this information, i.e. when
$\overrightarrow{Y}|_{\overrightarrow{x},\overleftarrow{z}}=\overrightarrow{Y}|_{\overrightarrow{x},\overleftarrow{z}^{\prime}}$
for all $\overrightarrow{x}$; which we abbreviate to the equivalence relation
$\overleftarrow{z}\sim_{\epsilon}\overleftarrow{z}^{\prime}$. Thus,
$\epsilon$-transducer features an encoding function $k$ such that
$k(\overleftarrow{z})=k(\overleftarrow{z}^{\prime})$ if and only if
$\overleftarrow{z}\sim_{\epsilon}\overleftarrow{z}^{\prime}$. The resulting
memory states $\mathcal{S}=\\{s_{i}\\}$ are then in $1$-$1$ correspondence
with the equivalence classes induced by $\sim_{\epsilon}$. The dynamics of the
input-output process can be realized by stochastic transitions between causal
states, i.e., a set of transition matrices $\mathcal{T}\equiv\\{T^{(y|x)}\\}$.
Their elements $T^{(y|x)}_{ij}$ then represent the probability an
$\epsilon$-transducer in state $s_{i}$ will emit the symbol $y$ upon receiving
input $x$, and transition to state $s_{j}$.

The memory states $\\{s_{i}\\}$ are referred to as the causal states, owing to
their interpretation as the minimal set of belief states an agent must hold to
be able to execute
$\overrightarrow{Y}|_{\overrightarrow{x},\overleftarrow{z}}$ to perfect
statistical fidelity. For each input stochastic process $\mathcal{A}$, the
resulting agent memory will be driven to some stationary distribution,
$\\{\pi_{i}\\}$, where $\pi_{i}$ denotes the probability of being at causal
state $s_{i}$ when driven by input process $\mathcal{A}$. The resulting memory
cost $C_{\mathcal{A}}=-\sum\pi_{i}\log_{2}\pi_{i}$ is then known as the
statistical complexity of the process on input $\mathcal{A}$ and is considered
a fundamental measure of structure for
$\overrightarrow{Y}|_{\overrightarrow{x},\overleftarrow{z}}$ that
characterizes how much past information any agent executing
$\overrightarrow{Y}|_{\overrightarrow{x},\overleftarrow{z}}$ must hold in
memory. By minimizing the statistical complexity over all input-output
processes that transform $\mathcal{A}$ to $\mathcal{B}$, we obtain the minimal
memory cost of the transformation, $C_{\mathcal{A}\rightarrow\mathcal{B}}$.

Note also that this quantity can always be bounded above by
$C_{\bf{0}\rightarrow\mathcal{B}}$, the memory cost of transforming a sequence
of $\mathbf{0}=\ldots 0000\ldots$ (or any other i.i.d sequence) to
$\mathcal{B}$. This is because we can always choose to first erase
$\mathcal{A}$ using a memoryless channel at no cost. The resulting machine is
known as the optimal predictive (or causal) model for $\mathcal{B}$ [1, 9, 5].
The states of such a machine are referred to as the causal states of
$\mathcal{B}$. $C_{\bf{0}\rightarrow\mathcal{B}}$ is referred to as the
statistical complexity of $\mathcal{B}$, representing the minimal information
we need to store about its past to generate statistically correct future
predictions [1]. When $C_{A\rightarrow\mathcal{B}}$ saturates this bound, it
suggests that tracking $\mathcal{A}$ has no benefit for making predictions on
$\mathcal{B}$.

Given two processes $\mathcal{A}$ and $\mathcal{B}$, let
$C_{\mathcal{A}\rightarrow\mathcal{B}}$ denote the minimal past data needed to
transform $\mathcal{A}$ to $\mathcal{B}$, and
$C_{\mathcal{B}\rightarrow\mathcal{A}}$ as the equivalent when transforming
from $\mathcal{B}$ to $\mathcal{A}$. Then, we define _process causal
asymmetry_ by the difference

$\displaystyle\Delta_{C}(\mathcal{A},\mathcal{B})=C_{\mathcal{A}\rightarrow\mathcal{B}}-C_{\mathcal{B}\rightarrow\mathcal{A}}\,.$
(1)

A positive $\Delta_{C}(\mathcal{A},\mathcal{B})$ indicates that more memory is
required to transform $\mathcal{A}$ to $\mathcal{B}$ than from $\mathcal{B}$
to $\mathcal{A}$. Our opening example illustrates this, with
$C_{\mathcal{A}\rightarrow\mathcal{B}}=1$ and
$C_{\mathcal{B}\rightarrow\mathcal{A}}=0$, such that
$\Delta_{C}(\mathcal{A},\mathcal{B})=1$.

So far, we assumed that $\mathcal{M}$ stores only classical states. However,
quantum agents encoding each causal state $s_{i}$ to corresponding quantum
state $|s_{i}\rangle$ exhibit a memory advantage [12, 8]. The quantum causal
states can always be taken to be pure states [8], and the quantum complexity
is defined as the von Neumann entropy
$Q_{\mathcal{A}}=S(\rho_{\mathcal{A}})=-\mbox{tr}\left(\rho_{\mathcal{A}}\log\rho_{\mathcal{A}}\right)$
of the average state of the quantum memory,
$\rho_{\mathcal{A}}=\sum_{i}\pi_{\mathcal{A},i}|s_{i}\rangle\\!\langle
s_{i}|$, where $|s_{i}\rangle\\!\langle s_{i}|$ is the quantum state
representing the classical causal state $s_{i}$. A quantum model is at least
as efficient as the best classical model, i.e., $Q_{\mathcal{A}}\leq
C_{\mathcal{A}}$ [12, 8]. By minimizing the quantum complexity over all input-
output processes that transform $\mathcal{A}$ to $\mathcal{B}$, we obtain
$Q_{\mathcal{A}\rightarrow\mathcal{B}}$, the minimal memory needed by quantum
agents to transform $\mathcal{A}$ to $\mathcal{B}$. For certain $\mathcal{A}$
and $\mathcal{B}$, we have that
$Q_{\mathcal{A}\rightarrow\mathcal{B}}<C_{\mathcal{A}\rightarrow\mathcal{B}}$.
In analogy to the classical case, we define process causal asymmetry for
quantum agents as

$\Delta_{Q}(\mathcal{A},\mathcal{B})=Q_{\mathcal{A}\rightarrow\mathcal{B}}-Q_{\mathcal{B}\rightarrow\mathcal{A}}.$

_Main Results.—_ We now state our main results. The first shows that the
direction of causal asymmetry can be reversed by quantum agents.

######  Result 1 (Inconsistent Causal Asymmetry).

There exist processes $\mathcal{A}$ and $\mathcal{B}$ with process causal
asymmetries simultaneously obeying $\Delta_{C}(\mathcal{A},\mathcal{B})>0$ and
$\Delta_{Q}(\mathcal{A},\mathcal{B})<0$, which implies that the classical
memory resources necessary to map $\mathcal{A}$ to $\mathcal{B}$ are higher
than that of mapping $\mathcal{B}$ to $\mathcal{A}$, while quantum
mechanically it is the other way around. Causal asymmetry can thus reverse
depending on whether quantum agents are allowed or not.

Our second result shows that not only an inconsistent causal asymmetry exists,
but the magnitude of this inconsistency can be arbitrarily large.

######  Result 2 (Unbounded Inconsistent Causal Asymmetry).

There exist processes $\mathcal{A}$ and $\mathcal{B}_{n}$, for
$n\in\mathbb{N}$ such that the classical process asymmetry
$\Delta_{C}(\mathcal{A},\mathcal{B})$ diverges with increasing $n$, while the
quantum one, $\Delta_{Q}(\mathcal{A},\mathcal{B})$, remains bounded but with
the opposite sign.

Our results thus illustrate - for the first time to our knowledge - that
quantum and classical theories can result in different conclusions about the
most natural order of causal transformations. The possibility of storing
information on non-orthogonal quantum states, not only leads to a quantitative
reduction of memory cost [12, 8], but to a qualitatively different behaviour
in the direction of causation.

_Explicit Demonstration –_ Let us consider two processes that consist of a
ground state to which the probability of transition is always
$\nicefrac{{1}}{{2}}$ from any of the excited states. The first process has
only one excited state and is a coarse-graining of the second one, which has
multiple excited states.

In detail, let $\mathcal{A}$ be a process with alphabet
$x\in\mathcal{X}=\\{0,1,2\\}$, whose statistics can be generated by a machine
with two internal states, ground state $r_{0}$ and excited state $r_{1}$ (see
Fig. 2). An output of $x=0$ is followed by a transition to state $r_{0}$,
while outputs $x=1$ or $x=2$ lead to a trasition to state $r_{1}$, with
probability $\nicefrac{{1}}{{2}}$.

We also consider a family of stochastic processes, $\mathcal{B}_{n}$, labeled
by an index $n\in\mathbb{N}$ with $n\geq 3$. Each can be modeled by a machine
with $n$ causal states, $s_{0}\,,\ldots,s_{n-1}$, and $n$ outputs,
$y\in\mathcal{Y}=\\{0,\ldots,n-1\\}$ with the following properties: (i) an
emission of symbol $y_{j}$ leads to a transition to the state of the same
index $s_{y_{j}}$, (ii) any excited state $s_{j\neq 0}$ either transitions to
the ground state $s_{0}$ with probability $\nicefrac{{1}}{{2}}$ or transitions
to another excited state $s_{k\neq 0}$ with probability
$\nicefrac{{p_{jk}}}{{2}}$, (iii) $s_{0}$ transitions to one of the excited
states $s_{j\neq 0,2}$ with probability $\nicefrac{{p_{0j}}}{{2}}$, except for
$j=2$ which occurs with probability $\nicefrac{{1+p_{02}}}{{2}}$. Moreover,
the probabilities $p_{jk}$, satisfying $\sum_{k=1}^{n-1}p_{jk}=1$ for all $j$,
are all assumed to be close to the value $\nicefrac{{1}}{{n-1}}$ but different
from each other. These processes are shown in Fig. 2.

$r_{0}$$r_{1}$$\mathcal{A}$$1:\nicefrac{{1}}{{2}}$$2:\nicefrac{{1}}{{2}}$$0:\nicefrac{{1}}{{2}}$$1:\nicefrac{{1}}{{2}}$$s_{j}$$\mathcal{B}_{n}$$s_{2}$$s_{0}$$s_{k}$$j,k=1,3,\ldots,n-1$$\dots$$\dots$$\dots$$0:\frac{1}{2}$$2:\frac{1+p_{02}}{2}$$k:\frac{p_{jk}}{2}$$j:\frac{p_{jj}}{2}$

Figure 2: Processes $\mathcal{A}$ and $\mathcal{B}_{n}$. Labels of transitions
with the same colour share the same pattern.

We now turn to $\epsilon$-transducers that transform $\mathcal{A}$ to
$\mathcal{B}_{n}$. Briefly speaking, such an agent has one state for each
different state of the output $\mathcal{B}_{n}$ and modifies the probabilities
of the outputs of $\mathcal{A}$ accordingly in order to reproduce the
probabilities of $\mathcal{B}_{n}$. These constraints alone are not sufficient
to single out a unique construction, and thus, there exists a family of
$\epsilon$-transducers that take $\mathcal{A}$ to $\mathcal{B}_{n}$ with
minimal complexity. Nevertheless, as they all have the same classical
complexity (see Appendix A), we choose a representative $\epsilon$-transducer
$\mathcal{T}_{n}$ with $n$ states, $\Sigma=\\{\sigma_{i}\\}_{i=0\ldots n-1}$,
a 3-symbol input alphabet $\mathcal{X}=\\{0,1,2\\}$, and an $n$-symbol output
alphabet $\mathcal{Y}=\\{0,\ldots,n-1\\}$ (see Fig. 3). Whenever an emission
of a certain symbol is made, a transition to the internal state of the same
label occurs. Specifically, if a symbol $x\neq 1$ is input, the same symbol
$y=x$ is output, and a transition to state $\sigma_{x}$ is made, respectively.
For input 1, however, output $y=j$ is emitted with probability $p_{ij}$ if the
$\epsilon$-transducers are at state $\sigma_{i}$.

$\tau_{0}$$\tau_{1}$$\hat{\mathcal{T}}_{n}$$1|1:\nicefrac{{1}}{{2}}$$2|1:\nicefrac{{1}}{{2}}$⋮$1|n-1:\nicefrac{{1}}{{2}}$$2|n-1:\nicefrac{{1}}{{2}}$$0|0:1$$1|1:1$⋮$1|n-1:1$$\sigma_{j}$$\mathcal{T}_{n}$$\sigma_{2}$$\sigma_{0}$$\sigma_{k}$$j,k=1,3,\ldots,n-1$$\dots$$\dots$$\dots$$0|0:1$$2|1:p_{j2}$$2|2:1$$k|1:p_{jk}$$j|1:p_{jj}$

Figure 3: The $\epsilon$-transducers $\mathcal{T}$ and
$\hat{\mathcal{T}}_{n}$. Labels of transitions with the same colour share the
same pattern.

Similarly, the $\epsilon$-transducers that transform $\mathcal{B}_{n}$ to
$\mathcal{A}$ keep intact the emissions of symbol $0$ but have to ‘erase’ all
the probabilities associated with the remaining $n-1$ outputs. We denote this
with $\hat{\mathcal{T}}_{n}$, and a graphic representation is shown in Fig. 3.
Once again, more than one channel yielding the same transformation exists, but
they all have the same classical statistical complexity (see Appendix A).

We now show that the classical complexities
$C_{\mathcal{A}\rightarrow\mathcal{B}_{n}}$ of the $\epsilon$-transducers
$\mathcal{T}_{n}$ that transform from $\mathcal{A}$ to $\mathcal{B}_{n}$ are
increasing with $n$, while the quantum complexities
$Q_{\mathcal{A}\rightarrow\mathcal{B}_{n}}$ get arbitrarily close to 0 when
the probabilities $p_{ij}$ get closer. In the other direction, however, both
classical, $C_{\mathcal{B}_{n}\rightarrow\mathcal{A}}$, and quantum,
$Q_{\mathcal{B}_{n}\rightarrow\mathcal{A}}$, complexities assume a finite
value between 0 and 1.

We start with the classical complexity of the $\epsilon$-transducer
$\hat{\mathcal{T}}_{n}$ from $\mathcal{A}$ to $\mathcal{B}_{n}$. We first
obtain the stationary distribution of the process $\mathcal{A}$ itself and
then the long-term probabilities of symbol $x$ being emitted. We explicitly
find the values
$\left\\{\Pr(0),\Pr(1),\Pr(2)\right\\}=\left\\{\nicefrac{{1}}{{3}},\nicefrac{{1}}{{2}},\nicefrac{{1}}{{6}}\right\\}$.
By also noting that every output of the $\epsilon$-transducers leads to a
transition to the state with the same label, the stationary distribution of
the $\epsilon$-transducers can be evaluated (see Appendix B). For $n\geq 3$
and under the assumption $p_{i,j}\approx\nicefrac{{1}}{{n-1}}~{}\forall i,j,$
we find the stationary distribution
$\varphi_{0}=\Pr(0),\varphi_{2}=\nicefrac{{\Pr(1)}}{{n-1}}+\Pr(2)$, and
$\varphi_{j}=\nicefrac{{\Pr(1)}}{{n-1}}$, for $j=1,3,\ldots,n-1$. The
complexity is obtained as
$C_{\mathcal{A}\rightarrow\mathcal{B}_{n}}=-\sum_{i}\varphi_{i}\log\varphi_{i}$;
in the limit of large $n$ it grows logarithmically with $n$, i.e.,
$C_{\mathcal{A}\rightarrow\mathcal{B}_{n}}\sim\log n$, and thus it is
unbounded.

On the other hand, the $\epsilon$-transducers that map $\mathcal{B}_{n}$ to
$\mathcal{A}$ can be shown to have a classical complexity independent of $n$.
The stationary distribution is
$\hat{\varphi}_{0}=\Pr(0)=1/3\,,\hat{\varphi}_{1}=1-\Pr(0)=2/3$, where now
$\Pr(0)$ is the probability of process $\mathcal{B}_{n}$ emitting a 0.
However, since $\mathcal{T}_{n}$ preserved the emissions with 0, $\Pr(0)$ for
$\mathcal{B}_{n}$ is the same as that of the input $\mathcal{A}$, from which
we obtain
$C_{\mathcal{B}_{n}\rightarrow\mathcal{A}}=-\sum_{i=0,1}\hat{\varphi}_{i}\log\hat{\varphi}_{i}\approx
0.918$ independent of $n$. It follows that the classical process causal
asymmetry is

$\Delta_{C}(\mathcal{A},\mathcal{B}_{n})\sim\log n,$

which grows as the logarithm of $n$. In other words, transforming process
$\mathcal{A}$ to $\mathcal{B}_{n}$ is increasingly costly in terms of memory
when a classical memory is employed.

We now turn to the derivation of the quantum complexity,
$Q_{\mathcal{A}\rightarrow\mathcal{B}_{n}}$. We explicitly construct the
following quantum models where the classical causal states are encoded as
$|s_{i}\rangle=\otimes_{x}|s_{i}^{x}\rangle$ with
$|s_{i}^{x}\rangle=\sum_{k}\sum_{y}\sqrt{T_{ik}^{(y|x)}}|y\rangle|k\rangle$
[8, 5]. The $\epsilon$-transducers $\mathcal{T}_{n}$ are such that for inputs
$x=0,2$ we have that $|s_{i}^{x}\rangle=|x\rangle|x\rangle$ independent of the
state index $i$. Also, one can easily check that
$|s_{i}^{1}\rangle=\sum_{j\neq 0}\sqrt{p_{ij}}|j\rangle|j\rangle$. As a
result, the overlap between causal states is given by $\langle
s_{i}|s_{j}\rangle=\sum_{k\neq 1}\sqrt{p_{ik}\,p_{jk}}$. The quantum
complexity is the von Neumann entropy of the state
$\rho=\sum_{i}\varphi_{i}|s_{i}\rangle\\!\langle s_{i}|$ where $\varphi_{i}$
denotes the $i-$th element of the stationary distribution of the
$\epsilon$-transducer $\mathcal{T}_{n}$ when driven by the input
$\mathcal{A}$. From the fact that state $\rho$ and the Gram matrix of
overlaps, with elements $G_{ij}=\sqrt{\varphi_{i}\varphi_{j}}\langle
s_{i}|s_{j}\rangle$, have the same non-zero eigenvalues [13], thereby their
von Neumann entropies coincide. When all the probabilities $p_{ij}$ get
arbitrarily close to each other, we have that
$G_{ij}\approx\sqrt{\varphi_{i}\varphi_{j}}$. In this case, the Gram matrix
$G\approx vv^{\top}$, with
$v^{\top}=(\sqrt{\varphi_{1}}\,,\ldots\,,\sqrt{\varphi_{n}})$ has
approximately one eigenvalue equal to 1 and all others equal to 0, leading to
a quantum complexity of 0. In Appendix C we give a precise argument and
provide an upper bound for a small perturbation of the probabilities around
the value $\nicefrac{{1}}{{n-1}}$ so that $p_{ij}=\frac{1+\delta_{ij}}{n-1}$,
with $\lvert\delta_{ij}\rvert\leq\delta$ for some small $\delta>0$, and we
show that the optimal quantum complexity is bounded as

$\displaystyle
Q_{\mathcal{A}\rightarrow\mathcal{B}_{n}}^{\text{upper}}(\delta)\geq
Q_{\mathcal{A}\rightarrow\mathcal{B}_{n}}\geq 0\,,$ (2)

where $Q_{\mathcal{A}\rightarrow\mathcal{B}_{n}}^{\text{upper}}(\delta)$ can
be made arbitrarily small by an appropriate choice of $\delta$.

Figure 4: (a) Classical complexities
$C_{\mathcal{A}\rightarrow\mathcal{B}_{n}}$ (blue, solid line) and
$C_{\mathcal{B}_{n}\rightarrow\mathcal{A}}$ (red, solid line), as well as the
quantum complexities, $Q_{\mathcal{A}\rightarrow\mathcal{B}_{n}}$ (light blue
shaded area) and $Q_{\mathcal{B}_{n}\rightarrow\mathcal{A}}$ (orange shaded
area). (b) Classical and quantum process causal asymmetries between
$\mathcal{A}$ and $\mathcal{B}_{n}$. In magenta we show
$\Delta_{C}(\mathcal{A},\mathcal{B}_{n})$, while
$\Delta_{Q}(\mathcal{A},\mathcal{B}_{n})$ lies in the brown-shaded area.

Turning to the quantum complexity of the $\epsilon$-transducers from $B_{n}$
to $\mathcal{A}$, the situation is more intricate. We consider all possible
classical channels and show that the complexity of all possible quantum models
is bounded (see Appendix A). This follows from a maximal fidelity constraint
that any model has to obey to correctly reproduce the channel [8].
Specifically, we can show that the optimal quantum complexity is bounded from
below and above according to the inequality

$\displaystyle Q_{\mathcal{B}_{n}\rightarrow\mathcal{A}}^{\text{upper}}\geq
Q_{\mathcal{B}_{n}\rightarrow\mathcal{A}}\geq 0.55\,,$ (3)

where $Q_{\mathcal{B}_{n}\rightarrow\mathcal{A}}^{\text{upper}}$ depends on
the value of $n$; it takes the value 0.682 for $n=3$ and approaches the
classical complexity of 0.918 with increasing values of $n$.

Using Eqs. (2) and (3), we obtain the following bounds on the quantum process
causal asymmetry, $\Delta_{Q}(\mathcal{A},\mathcal{B}_{n})$,

$\displaystyle
Q^{\text{upper}}_{\mathcal{A}\rightarrow\mathcal{B}_{n}}(\delta)-0.55\geq\Delta_{Q}(\mathcal{A},\mathcal{B}_{n})\geq-
Q_{\mathcal{B}_{n}\rightarrow\mathcal{A}}^{\text{upper}}.$ (4)

On the left hand side and for any $n$, there exists a range of $\delta$ that
make this difference negative (see Appendix A). This implies that mapping
processes $\mathcal{B}_{n}$ to $\mathcal{A}$ has a higher memory cost than
that of mapping $\mathcal{A}$ to $\mathcal{B}_{n}$, when a quantum memory is
employed.

In Fig. 4, we plot the difference of classical and quantum process causal
asymmetries, $\Delta_{C}(\mathcal{A},\mathcal{B}_{n})$ and
$\Delta_{Q}(\mathcal{A},\mathcal{B}_{n})$, for $n=3,\ldots,20$ and
$\delta=10^{-2}$. We see that the classical one grows logarithmically with $n$
while the quantum approaches a finite negative value.

Discussion.— Transforming one stochastic process into another generally
requires memory. Here, we introduced _process causal asymmetry_ to investigate
the difference in memory costs required for transformations between a pair of
stochastic processes $\mathcal{A}$ and $\mathcal{B}$. We demonstrated that
agents with quantum memory exhibit dramatically different behaviour from those
with classical memory. In particular, we provided the first explicit example
where the direction of causation is flipped between classical and quantum
models, and the gap grows unboundedly with system size.

There are several natural directions for further research. The first involves
linking our work to that of causal asymmetry in the context of causal vs.
retrocausal models – where memory costs of modeling stochastic processes in
forward-time vs. reverse-time can differ [3]. Here, quantum models could
remove this asymmetry, but a full reversal remains unknown [5]. Meanwhile, our
quantum agents transform classical data to classical data - while quantum
agents (combs) that transform quantum processes also exist [14, 15, 16]. It
would be exciting to unify such settings, considering causal asymmetry when
both time and input-outputs are reversed in contexts of both classical and
quantum outputs.

Conceptually, process causal asymmetry also hints at some underlying resource
theory on temporal correlations. For example, a sequence of i.i.d. random
variables would take no memory to generate, while transforming this to a
highly non-Markovian process requires adaptive agents with increasing memory
resources [17, 18]. This opens an interesting research direction towards
constructing a formal hierarchy of non-adaptive agents and relating it to
existing ideas from resource theories of non-Markovianity [19, 20]. Indeed,
the power of memory and adaptive operations has already been recognized in
quantum state preparation [21, 22], gate synthesis [23, 24], exhibiting
contextuality [11, 25, 26, 27], and generating data-strings [18] as well as
being a key differentiator between quantum error mitigation and error
correction [28]. Therefore, this direction could provide valuable insights on
when quantum agents have greatest advantage and where they are most useful.

Acknowledgements.— We thank Paul Riechers, Jayne Thompson, Thomas Eliott,
Andrew Garner, Felix Binder and Alec Boyd for interesting discussions. This
work is supported by the National Research Foundation of Singapore, and the
Agency for Science, Technology and Research (A*STAR) under its QEP2.0
programme (NRF2021-QEP2-02-P06), the Singapore Ministry of Education Tier1
Grant RG77/22, the Singapore Ministry of Education Tier 2 Grant
MOET2EP50221-0005, FQxI under grant nos. FQXi-RFP-IPW-1903 (“Are quantum
agents more energetically efficient at making predictions?”) and FQXi-RFP-1809
(“The role of quantum effects in simplifying adaptive agents”) from the
Foundational Questions Institute and Fetzer Franklin Fund (a donor-advised
fund of Silicon Valley Community Foundation). H.K. and S.K. are supported by
KIAS Individual Grant Nos. CG085301 (H.K.) and CG086201 (S.K.) at the Korea
Institute for Advanced Study.

## References

  * Crutchfield and Young [1989] J. P. Crutchfield and K. Young, Phys. Rev. Lett. 63, 105 (1989), publisher: American Physical Society.
  * Barnett and Crutchfield [2015] N. Barnett and J. P. Crutchfield, J Stat Phys 161, 404 (2015).
  * Crutchfield  _et al._ [2009] J. P. Crutchfield, C. J. Ellison, and J. R. Mahoney, Phys. Rev. Lett. 103, 094101 (2009), publisher: American Physical Society.
  * Ellison  _et al._ [2009] C. J. Ellison, J. R. Mahoney, and J. P. Crutchfield, J Stat Phys 136, 1005 (2009).
  * Thompson  _et al._ [2018] J. Thompson, A. J. Garner, J. R. Mahoney, J. P. Crutchfield, V. Vedral, and M. Gu, Phys. Rev. X 8, 031013 (2018), publisher: American Physical Society.
  * Woods  _et al._ [2022] M. P. Woods, R. Silva, G. Pütz, S. Stupar, and R. Renner, PRX Quantum 3, 010319 (2022).
  * Yang  _et al._ [2018] Y. Yang, G. Chiribella, and M. Hayashi, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 474, 20170773 (2018).
  * Elliott  _et al._ [2022] T. J. Elliott, M. Gu, A. J. Garner, and J. Thompson, Phys. Rev. X 12, 011007 (2022), publisher: American Physical Society.
  * Crutchfield [2012] J. P. Crutchfield, Nature Phys 8, 17 (2012), number: 1 Publisher: Nature Publishing Group.
  * Crutchfield  _et al._ [2010] J. P. Crutchfield, C. J. Ellison, R. G. James, and J. R. Mahoney, Chaos: An Interdisciplinary Journal of Nonlinear Science 20 (2010).
  * Cabello  _et al._ [2016] A. Cabello, M. Gu, O. Gühne, J.-A. Larsson, and K. Wiesner, Phys. Rev. A 94, 052127 (2016).
  * Thompson  _et al._ [2017] J. Thompson, A. J. P. Garner, V. Vedral, and M. Gu, npj Quantum Inf 3, 1 (2017), number: 1 Publisher: Nature Publishing Group.
  * Jozsa and Schlienz [2000] R. Jozsa and J. Schlienz, Phys. Rev. A 62, 012301 (2000).
  * Paparo  _et al._ [2014] G. D. Paparo, V. Dunjko, A. Makmal, M. A. Martin-Delgado, and H. J. Briegel, Physical Review X 4, 031002 (2014).
  * Breuer  _et al._ [2016] H.-P. Breuer, E.-M. Laine, J. Piilo, and B. Vacchini, Reviews of Modern Physics 88, 021002 (2016).
  * Chiribella  _et al._ [2009] G. Chiribella, G. M. D’Ariano, and P. Perinotti, Physical Review A 80, 022339 (2009).
  * Yang and Renner [2020] Y. Yang and R. Renner, arXiv preprint arXiv:2004.07857 (2020).
  * Vieira and Budroni [2022] L. B. Vieira and C. Budroni, Quantum 6, 623 (2022).
  * Berk  _et al._ [2021] G. D. Berk, A. J. Garner, B. Yadin, K. Modi, and F. A. Pollock, Quantum 5, 435 (2021).
  * Anand and Brun [2019] N. Anand and T. A. Brun, arXiv preprint arXiv:1903.03880 (2019).
  * Høyer and Špalek [2005] P. Høyer and R. Špalek, Theory of Computing 1, 81 (2005).
  * Bravyi  _et al._ [2022] S. Bravyi, I. Kim, A. Kliesch, and R. Koenig, Adaptive constant-depth circuits for manipulating non-abelian anyons (2022), arXiv:2205.01933 [quant-ph] .
  * Jones [2013] C. Jones, Phys. Rev. A 87, 022328 (2013).
  * Gidney [2018] C. Gidney, Quantum 2, 74 (2018).
  * Kleinmann  _et al._ [2011] M. Kleinmann, O. Guehne, J. R. Portillo, J.-Å. Larsson, and A. Cabello, New Journal of Physics 13, 113011 (2011).
  * Budroni [2019] C. Budroni, Philosophical Transactions of the Royal Society A 377, 20190141 (2019).
  * Cabello  _et al._ [2018] A. Cabello, M. Gu, O. Gühne, and Z.-P. Xu, Physical review letters 120, 130401 (2018).
  * Takagi  _et al._ [2022] R. Takagi, S. Endo, S. Minagawa, and M. Gu, npj Quantum Information 8, 114 (2022).
  * Travers and Crutchfield [2011] N. F. Travers and J. P. Crutchfield, J Stat Phys 145, 1181 (2011).
  * Audenaert [2007] K. M. R. Audenaert, J. Phys. A: Math. Theor. 40, 8127 (2007).

##  Appendix A Appendix A: Derivation of minimal $\epsilon$-transducers
$\mathcal{T}_{n}$ and $\hat{\mathcal{T}}_{n}$

We derive all minimal $\epsilon$-transducers from process $\mathcal{A}$ to
process $\mathcal{B}_{n}$ and vice versa. We go through all the details of the
calculation for the $\epsilon$-transducers $\hat{\mathcal{T}}_{n}$ from
$\mathcal{B}_{n}$ to $\mathcal{A}$ and only describe the general
characteristics the other way around. Although we show the derivation
explicitly in the case with $n=3$, the proof remains valid for any $n$ and
comment on the general case in the end.

Since each output of $\mathcal{A}$ and $\mathcal{B}_{3}$ synchronises to a
unique state [29], this needs to be reflected in the structure of the
$\epsilon$-transducer. As a result, regardless of input, outputs of 1 or 2
need to synchronize to state $r_{1}$ say of the $\epsilon$-transducer, while
conditional outputs of 0, need to synchronize to the other state, $r_{0}$. In
practice, this also suffices to show that no memoryless $\epsilon$-transducer
that maps $\mathcal{B}_{3}$ to $\mathcal{A}$ exists, but we also show it
explicitly. Assume that such an $\epsilon$-transducer exists. In this case,
transition matrices are just a collection of probabilities since there is only
one state and have the general form

$\displaystyle\hat{T}:\\{$ $\displaystyle
p_{00},\,p_{10},\,p_{20}=1-p_{00}-p_{10}\,$ $\displaystyle
p_{01},\,p_{11},\,p_{21}=1-p_{01}-p_{11}\,$ $\displaystyle
p_{02},\,p_{12},\,p_{22}=1-p_{02}-p_{12}\\}\,,$ (5)

where the symbols $p_{ij}$ have subscripts that are shorthand for $i|j$
denoting the probability of outputting symbol $i$ while receiving symbol $j$.

The transition matrices of a process $\mathcal{A}$ are

$\displaystyle A^{(x)}=\left\\{\begin{pmatrix}0&0\\\
\nicefrac{{1}}{{2}}&0\end{pmatrix},\begin{pmatrix}0&\nicefrac{{1}}{{2}}\\\
0&\nicefrac{{1}}{{2}}\end{pmatrix},\begin{pmatrix}0&\nicefrac{{1}}{{2}}\\\
0&0\end{pmatrix}\right\\}\,,$ (6)

with $x=0,1,2$ and similarly for $\mathcal{B}_{3}$:

$\displaystyle B_{3}^{(x)}=\left\\{\begin{pmatrix}0&0&0\\\
\nicefrac{{1}}{{2}}&0&0\\\ \nicefrac{{1}}{{2}}&0&0\\\
\end{pmatrix},\begin{pmatrix}0&\nicefrac{{p_{0}}}{{2}}&0\\\
0&\nicefrac{{p_{1}}}{{2}}&0\\\ 0&\nicefrac{{p_{2}}}{{2}}&0\\\
\end{pmatrix},\begin{pmatrix}0&0&1-\nicefrac{{p_{0}}}{{2}}\\\
0&0&\nicefrac{{(1-p_{1})}}{{2}}\\\ 0&0&\nicefrac{{(1-p_{2})}}{{2}}\\\
\end{pmatrix}\right\\}\,,$ (7)

where $p_{i}=p_{i1}$.

Taking the process $\mathcal{B}_{3}$ with transition matrices $B_{3}^{(x)}$ as
input to the $\epsilon$-transducer $\hat{\mathcal{T}}_{3}$ with transition
matrices $\hat{T}^{(y|x)}$ one can construct the transition matrices
$J^{(x,y)}$ of the joint process over joint inputs and outputs as

$\displaystyle J^{(x,y)}=\hat{T}^{(y|x)}\otimes B_{3}^{(x)}\,.$ (8)

This follows by noting that element-wise this is equivalent to the statement
about conditional probabilities

$\displaystyle J^{(x,y)}_{(i,j)\rightarrow(k,l)}$
$\displaystyle=\Pr(Y_{t}=y,X_{t}=x,S_{t+1}=s_{k},$
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\Sigma_{t+1}=\sigma_{l}|,S_{t}=s_{i},\Sigma_{t}=\sigma_{j})$
$\displaystyle=\Pr(Y_{t}=y,S_{t+1}=s_{k}|X_{t}=x,S_{t}=s_{i})\cdot$
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\Pr(\Sigma_{t+1}=\sigma_{l},X_{t}=x|\Sigma_{t}=\sigma_{j})$
(9)

From the joint process, one can trace over inputs, $x$, to obtain a
presentation of the process over outputs alone:

$\displaystyle\tilde{A}^{(y)}=\sum_{x}J^{(x,y)}\,.$ (10)

We put a tilde to the output process obtained this way to signify the fact
that in general this will not be a minimal presentation and some of the states
of the output may be _transient_ , that is, have long term probability of
occurrence equal to zero. Moreover, some states may also be equivalent to
others, that is, belong to the same equivalence class. In order to obtain the
minimal presentation, the $\epsilon$-machine, of the output process, one needs
to remove transients and merge equivalent states. Both processes $\mathcal{A}$
and $\mathcal{B}_{3}$ are given in their minimal presentation and thus upon
removing transient states and merging equivalent states, the resulting
matrices of the output should be the same as those of $\mathcal{A}$.
Explicitly, for output $y=0$ we have

$\displaystyle\tilde{A}^{(0)}$ $\displaystyle=\sum_{x}\hat{T}^{(0|x)}\otimes
B_{3}^{(x)}=\sum_{x}p_{0x}B_{3}^{(x)}$
$\displaystyle=p_{00}B^{(0)}+p_{01}B^{(1)}+p_{02}B^{(2)}$
$\displaystyle=\frac{1}{2}\begin{pmatrix}0&p_{01}p_{0}&p_{02}(2-p_{0})\\\
p_{00}&p_{01}p_{1}&p_{02}(1-p_{1})\\\
p_{00}&p_{01}p_{2}&p_{02}(1-p_{2})\end{pmatrix}$

Examining the structure of $A^{(0)}$, the target output, and the output
$\tilde{A}^{(0)}$ of the memoryless $\epsilon$-transducer, we see that the
only possibility is that states 2 and 3 of $\tilde{A}$ are in the same
equivalence class, call it class 2, corresponding to the second state of the
target process $\mathcal{A}$. Moreover, since there are no transitions from
class 1 to class 2, we must necessarily have $p_{01}=p_{02}=0$. Similarly, for
output $x=2$ we have

$\displaystyle\tilde{A}^{(2)}$
$\displaystyle=p_{20}B^{(0)}+p_{21}B^{(1)}+p_{22}B^{(2)}$
$\displaystyle=\frac{1}{2}\begin{pmatrix}0&p_{21}p_{0}&p_{22}(2-p_{0})\\\
p_{20}&p_{21}p_{1}&p_{22}(1-p_{1})\\\
p_{20}&p_{21}p_{2}&p_{22}(1-p_{2}).\end{pmatrix}$

Since at equivalence class 2 there are no self transitions while emitting
symbol 2, we must have that $p_{21}=p_{22}=0$, which however implies that no
transition from class 2 to class 1 can happen. This shows that the output can
not be correctly reproduced with a memoryless $\epsilon$-transducer. Thus the
$\epsilon$-transducer must have at least two states.

A general Markovian on outputs (more precisely, of _pure feedback Markov
order_ 1 [2]) $\epsilon$-transducer with two states has the following
transition matrices

$\displaystyle\hat{T}:\\{$ $\displaystyle\begin{pmatrix}t^{00}_{11}&0\\\
t^{00}_{21}&`\end{pmatrix}\,,\begin{pmatrix}0&t^{10}_{12}\\\
0&t^{10}_{22}\end{pmatrix}\,,\begin{pmatrix}0&t^{20}_{12}\\\
0&t^{20}_{22}\end{pmatrix}\,,$ $\displaystyle\begin{pmatrix}t^{01}_{11}&0\\\
t^{01}_{21}&0\end{pmatrix}\,,\begin{pmatrix}0&t^{11}_{12}\\\
0&t^{11}_{22}\end{pmatrix}\,,\begin{pmatrix}0&t^{21}_{12}\\\
0&t^{21}_{22}\end{pmatrix}\,,$ $\displaystyle\begin{pmatrix}t^{02}_{11}&0\\\
t^{02}_{21}&0\end{pmatrix}\,,\begin{pmatrix}0&t^{12}_{12}\\\
0&t^{12}_{22}\end{pmatrix}\,,\begin{pmatrix}0&t^{22}_{12}\\\
0&t^{22}_{22}\end{pmatrix}\\}\,,$ (11)

where in the matrix elements, $t_{ij}^{yx}$, superscripts stand for
conditional outputs given inputs, $y|x$, and subscripts $ij$ denote transition
from causal state $i$ to causal state $j$. Conservation of probability and
unifilarity imposes the constraints

$\displaystyle t^{00}_{11}+t^{10}_{12}+t^{20}_{12}$
$\displaystyle=1\,,\,\,t^{00}_{21}+t^{10}_{22}+t^{20}_{22}=1\,,$
$\displaystyle t^{01}_{11}+t^{11}_{12}+t^{21}_{12}$
$\displaystyle=1\,,\,\,t^{01}_{21}+t^{11}_{22}+t^{21}_{22}=1\,,$
$\displaystyle t^{02}_{11}+t^{12}_{12}+t^{22}_{12}$
$\displaystyle=1\,,\,\,t^{02}_{21}+t^{12}_{22}+t^{22}_{22}=1\,.$

We calculate the output of the $\epsilon$-transducer when driven with
$\mathcal{B}_{3}$ by using the composition and marginalization equation,

$\displaystyle\tilde{A}^{(y)}$ $\displaystyle=\sum_{x}\hat{T}^{(y|x)}\otimes
B_{3}^{(x)}\,.$ (13)

Explicitly we obtain the 6 state output process with transition matrices:

$\displaystyle\tilde{A}^{(0)}=\frac{1}{2}\begin{pmatrix}0&t^{01}_{11}p_{0}&t^{02}_{11}(2-p_{0})&0&0&0\\\
t^{00}_{11}&t^{01}_{11}p_{1}&t^{02}_{11}(1-p_{1})&0&0&0\\\
t^{00}_{11}&t^{01}_{11}p_{2}&t^{02}_{11}(1-p_{2})&0&0&0\\\
0&t^{01}_{21}p_{0}&t^{02}_{21}(2-p_{0})&0&0&0\\\
t^{00}_{21}&t^{01}_{21}p_{1}&t^{02}_{21}(1-p_{1})&0&0&0\\\
t^{00}_{21}&t^{01}_{21}p_{2}&t^{02}_{21}(1-p_{2})&0&0&0\\\ \end{pmatrix}\,,$
(14)
$\displaystyle\tilde{A}^{(1)}=\frac{1}{2}\begin{pmatrix}0&0&0&0&t^{11}_{12}p_{0}&t^{12}_{12}(2-p_{0})\\\
0&0&0&t^{10}_{12}&t^{11}_{12}p_{1}&t^{12}_{12}(1-p_{1})\\\
0&0&0&t^{10}_{12}&t^{11}_{12}p_{1}&t^{12}_{12}(1-p_{1})\\\
0&0&0&0&t^{11}_{22}p_{0}&t^{12}_{22}(2-p_{0})\\\
0&0&0&t^{10}_{22}&t^{11}_{22}p_{1}&t^{12}_{22}(1-p_{1})\\\
0&0&0&t^{10}_{22}&t^{11}_{22}p_{1}&t^{12}_{22}(1-p_{1})\\\ \end{pmatrix}\,,$
(15)
$\displaystyle\tilde{A}^{(2)}=\frac{1}{2}\begin{pmatrix}0&0&0&0&t^{21}_{12}p_{0}&t^{22}_{12}(2-p_{0})\\\
0&0&0&t^{20}_{12}&t^{21}_{12}p_{1}&t^{22}_{12}(1-p_{1})\\\
0&0&0&t^{20}_{12}&t^{21}_{12}p_{1}&t^{22}_{12}(1-p_{1})\\\
0&0&0&0&t^{21}_{22}p_{0}&t^{22}_{22}(2-p_{0})\\\
0&0&0&t^{20}_{22}&t^{21}_{22}p_{1}&t^{22}_{22}(1-p_{1})\\\
0&0&0&t^{20}_{22}&t^{21}_{22}p_{1}&t^{22}_{22}(1-p_{1})\\\ \end{pmatrix}\,.$
(16)

From the synchronization properties of the input and output processes and the
fact that minimal presentation of the target output has only two causal
states, it follows that states $1,2,3$ and $4,5,6$ of the
$\tilde{\mathcal{A}}$ must belong to the same equivalent class and correspond
to causal states $r_{0}$ and $r_{1}$ of the target output, $\mathcal{A}$,
respectively. However, one needs to separately check the possibility for some
states being _transient_ , that is, have long term probability of occurrence
equal to 0. These states can be removed, which is equivalent to removing the
corresponding row and columns of the transition matrices $\tilde{A}^{(x)}$.

We first examine the case where all states in each equivalence class are
_recurrent_ , i.e. have long term probability of occurrence greater than zero.
That is, we have the two classes of states, $r_{0}=\\{1,2,3\\}$ and
$r_{1}=\\{4,5,6\\}$, consisting of non-transient states. This means that the
the transition matrices have a block structure with $3\times 3$ sub-blocks.
Note that in general two states $r$ and $r^{\prime}$ are equivalent, $r\sim
r^{\prime}$, if the probabilities, $\Pr(w|r)=\Pr(w|r^{\prime})$, assigned to
every future word $w$ of length $l\in\mathbb{Z}^{+}$ when the machine is in
state $r$ or $r^{\prime}$, are equal [29]. However, due to the Markov property
our task of checking equivalence is greatly simplified, as we only need to
compare states for equivalence up to words of length 1. Thus, for each state
its future transition probabilities for each output must match the ones of
other states in the same class. Under the assumption that all states are
recurrent, examining the self transition of equivalence class $r_{0}$ with
output $y=0$, we obtain $t^{01}_{11}=t^{01}_{11}=t^{02}_{11}=0$. Similarly,
from the transition from $r_{1}$ to $r_{0}$ of output $y=0$ we obtain the
conditions,

$\displaystyle t^{01}_{21}p_{0}+t^{02}_{21}(2-p_{0})$
$\displaystyle=t^{00}_{21}+t^{01}_{21}p_{1}+t^{02}_{21}(1-p_{1})$
$\displaystyle=t^{00}_{21}+t^{01}_{21}p_{2}+t^{02}_{21}(1-p_{2})=1\,,$ (17)

which imply that $t^{00}_{21}=t^{01}_{21}=t^{01}_{21}=\nicefrac{{1}}{{2}}$.
Similarly, the $r_{0}$ to $r_{0}$ and $r_{1}$ to $r_{1}$ transitions of output
$y=0$ imply that $t^{10}_{12}=t^{12}_{12}=t^{22}_{12}=\nicefrac{{1}}{{2}}$ and
$t^{10}_{22}=t^{11}_{22}=t^{12}_{22}=\nicefrac{{1}}{{2}}$, respectively.
Finally, from output $y=2$ we find the conditions
$t^{20}_{12}=t^{21}_{12}=t^{22}_{12}=\nicefrac{{1}}{{2}}$ and
$t^{20}_{22}=t^{21}_{22}=t^{22}_{22}=0$. By noting the fact that in the
solution $T^{(y|x)}=T^{(y|x^{\prime})}$ for all $x,x^{\prime}$ we see that
this is an input-independent channel. In other words, it completely ignores
input and always outputs the target output process $\mathcal{A}$ and thus
corresponds to the trivial solution. It remains to examine the cases with
transient states.

Even though in principle there are many different cases that one needs to
consider separately, we can show that only one family of solutions exists,
this time input-independent. To show this we can prove the following
statements sequentially (each statement assumes the validity of the previous
one):

  1. 1.

At least one state from each of the two classes, $r_{0}=\\{1,2,3\\}$ and
$r_{1}=\\{4,5,6\\}$, needs to be recurrent.

  2. 2.

States 5 and 6 of equivalence class $r_{1}$ can not be transient.

  3. 3.

State 1 of equivalence class $r_{0}$ can not be transient.

  4. 4.

With states 1,5,6 recurrent, states 2 or 3 of class $r_{0}$ alone can not be
transient: they are either both recurrent or both transient.

  5. 5.

If states 2 and 3 are both transient, state 4 of equivalence class $r_{1}$
can’t be recurrent.

All of the above statements follow from examining the transition matrices of
the resulting outputs. For example, statement 2 follows by assuming that one
of the states 5 and 6 is recurrent and the other transient or both are
transient, and verifying that it is impossible to find parameter values that
correctly reproduce the target outputs. Specifically, the self transition from
equivalence class 2 while emitting output 2 is 0 while the target output has a
self transition with probability $\nicefrac{{1}}{{2}}$.

In view of the above statements only two possibilities remain:

  1. 1.

All states are recurrent.

  2. 2.

Only states 1,5 and 6 are recurrent.

We have already examined the first possibility and showed that it leads to the
trivial solution. It remains to explore the second case. Since, by assumption,
states 2,3,4 are transient, there can be no flow of probability from the
recurrent states as this would make them recurrent as well. This implies that
$t^{01}_{21}=t^{02}_{21}=t^{10}_{22}=t^{20}_{22}=0$. Moreover, since states
2,3,4 are transient we can remove the corresponding rows and columns from the
transition matrices, which reduces them to

$\displaystyle\tilde{A}^{(0)}=\frac{1}{2}\begin{pmatrix}0&0&0\\\
t^{00}_{21}&0&0\\\ t^{00}_{21}&0&0\\\
\end{pmatrix},\,\tilde{A}^{(1)}=\frac{1}{2}\begin{pmatrix}0&t^{11}_{12}p_{0}&t^{12}_{12}(2-p_{0})\\\
0&t^{11}_{22}p_{1}&t^{12}_{22}(1-p_{1})\\\
0&t^{11}_{22}p_{1}&t^{12}_{22}(1-p_{1})\\\ \end{pmatrix}\,,$ (18)

and

$\displaystyle\tilde{A}^{(2)}=\frac{1}{2}\begin{pmatrix}0&t^{21}_{12}p_{0}&t^{22}_{12}(2-p_{0})\\\
0&t^{21}_{22}p_{1}&t^{22}_{22}(1-p_{1})\\\
0&t^{21}_{22}p_{1}&t^{22}_{22}(1-p_{1})\\\ \end{pmatrix}\,.$ (19)

After removing states 2,3 and 4 we are left with three states. State 1 must
correspond to state $r_{0}$ of the target while states 2 and 3 must belong to
the same class and correspond to state $r_{1}$ of the target. With these
observations, to correctly reproduce the transitions associated with output 0,
we have that $t^{00}_{21}=1$. Similarly, from the transitions from class 1 to
class 2 and the self transition of class 2 with output 1 we obtain the
conditions $t^{11}_{22}=t^{12}_{22}=1$ and
$t^{11}_{12}p_{0}+t^{12}_{12}(2-p_{0})=1$. Finally, from the transition with
output 2 we find $t^{21}_{22}=t^{22}_{22}=0$ and
$t^{21}_{12}p_{0}+t^{22}_{12}(2-p_{0})=1$. From the preceding conditions and
unifilarity it also follows that $t^{01}_{11}=t^{02}_{11}=0$. Thus, the
general form of the 3-parameter family of $\epsilon$-transducers that take
$\mathcal{B}_{3}$ to $\mathcal{A}$ have the general form

$\displaystyle\hat{T}:\\{$ $\displaystyle\begin{pmatrix}t^{00}_{11}&0\\\
1&0\end{pmatrix}\,,\begin{pmatrix}0&t^{10}_{12}\\\
0&0\end{pmatrix}\,,\begin{pmatrix}0&1-t^{00}_{11}-t^{10}_{12}\\\
0&0\end{pmatrix}\,,$ $\displaystyle\begin{pmatrix}0&0\\\
0&0\end{pmatrix}\,,\begin{pmatrix}0&t^{11}_{12}\\\
0&1\end{pmatrix}\,,\begin{pmatrix}0&1-t^{11}_{12}\\\ 0&0\end{pmatrix}\,,$
$\displaystyle\begin{pmatrix}0&0\\\
0&0\end{pmatrix}\,,\begin{pmatrix}0&1-t^{22}_{12}\\\
0&1\end{pmatrix}\,,\begin{pmatrix}0&t^{22}_{12}\\\ 0&0\end{pmatrix}\\}\,,$
(20)

with

$\displaystyle t^{22}_{12}=\frac{1-(1-t^{11}_{12})p_{0}}{2-p_{0}}\,.$ (21)

All these classical $\epsilon$-transducers correctly reproduce the output
$\mathcal{A}$ and moreover are minimal as they all have the same statistical
complexity of approximately 0.918. The complexity follows from the fact that
the stationary distribution of all these channels is essentially
$\\{\nicefrac{{1}}{{3}},\nicefrac{{2}}{{3}}\\}$ for input $\mathcal{B}_{3}$,
independent of the free parameters of the family of models.

The situation is different, however, when one considers the corresponding
quantum models. The reason for that is that the quantum complexity will depend
on the free parameters $t^{00}_{11}\,,t^{10}_{12}$ and $t^{11}_{12}$ of the
classical $\epsilon$-transducers. However, there is a theoretical upper bound
on the overlap between the quantum causal states which is given by the maximum
fidelity constraint [8], explicitly found as

$\displaystyle F_{12}$
$\displaystyle=\min\left\\{\sqrt{t^{00}_{11}},\sqrt{t^{11}_{12}},\sqrt{1-t^{22}_{12}}\right\\}$
$\displaystyle=\min\left\\{\sqrt{t^{00}_{11}},\sqrt{t^{11}_{12}},\sqrt{\frac{1-t^{11}_{12}p_{0}}{2-p_{0}}}\right\\}\,.$
(22)

The maximal minimum value of the second and third terms is simultaneously
achieved for the value $t^{11}_{12}=\nicefrac{{1}}{{2}}$ irrespective of the
value of $p_{0}$. To obtain this value, the unconstrained first term may
assume any value $t^{00}_{11}\geq t^{11}_{12}$. If we set $t^{00}_{11}=1$, it
corresponds precisely to the $\epsilon$-transducer in the main text. With the
maximal allowed overlap being $\langle
s_{1}|s_{2}\rangle=\nicefrac{{1}}{{\sqrt{2}}}$, we find that there can not be
a quantum model with complexity less than 0.55. That is, we have shown that
for any of these $\epsilon$-transducers

$\displaystyle F_{12}\leq F_{12}^{\max}=\frac{1}{\sqrt{2}}$ (23)

which implies that the quantum complexity of the optimal model,
$Q^{\text{opt}}$ must obey

$\displaystyle Q^{\text{opt}}\geq Q^{\min}\approx 0.55$ (24)

Note, however, that the fidelity constraint can not be saturated in general
even by the optimal quantum model and thus will underestimate the optimal
quantum complexity. Nevertheless, it suffices for our purposes as we just need
to show that in the other direction there exists a quantum model that can go
below this bound.

In addition, in can be shown that the optimal quantum complexity has an upper
bound. Specifically, if we encode classical causal states to quantum states
according to

$\displaystyle|s_{1}\rangle=\left(\sqrt{t^{00}_{11}}|01\rangle+\sqrt{t^{10}_{12}}|12\rangle+\sqrt{1-t^{00}_{11}-t^{10}_{12}}|22\rangle\right)$
$\displaystyle\times\left(\sqrt{t^{11}_{12}}|12\rangle+\sqrt{1-t^{11}_{12}}|22\rangle\right)$
$\displaystyle\times\left(\sqrt{1-t^{22}_{12}}|12\rangle+\sqrt{t^{22}_{12}}|22\rangle\right)$
(25)

and

$\displaystyle|s_{2}\rangle=|01\rangle|12\rangle|12\rangle\,.$ (26)

their overlap is readily computed

$\displaystyle\langle
s_{1}|s_{2}\rangle=\sqrt{t^{00}_{11}t^{11}_{12}(1-t^{22}_{12})}=\sqrt{t^{00}_{11}t^{11}_{12}\frac{(1-t^{11}_{12}p_{0})}{2-p_{0}}}\,,$
(27)

and attains its maximal value for $t^{00}_{11}=1$ and

$\displaystyle\langle
s_{1}|s_{2}\rangle=\begin{cases}\sqrt{\frac{1-p_{0}}{2-p_{0}}}\,,&t^{11}_{12}=\frac{1}{2p_{0}}\,,\text{when
}0<p_{0}\leq\nicefrac{{1}}{{2}}\\\
\frac{1}{\sqrt{4p_{0}(2-p_{0})}}\,,&t^{11}_{12}=1\,,\,\,\,\,\,\,\text{when
}\nicefrac{{1}}{{2}}<p_{0}\leq 1.\end{cases}$ (28)

In either case, for values of $p_{0}$ close to $\nicefrac{{1}}{{2}}$, which we
assume in the main text, we find that the overlap is close to
$\nicefrac{{1}}{{\sqrt{3}}}$ and thus the quantum model can reach a quantum
complexity of approximately 0.682. We have thus obtained the following
inequality that upper and lower bounds the optimal quantum complexity,

$\displaystyle 0.682\geq
Q^{\text{opt}}_{\mathcal{B}_{3}\rightarrow\mathcal{A}}\geq 0.55\,.$ (29)

It follows that the quantum complexity of the optimal quantum model is
strictly less than the classical complexity but it can never reach a value
less than about 0.55.

So far, we have only discussed the case with $n=3$ but the proof generalises
in a straight forward manner in the case with $n>3$. Specifically, first it
can be shown that no memoryless channel that takes $\mathcal{B}_{n}$ to
$\mathcal{A}$ exists, that is, the minimal $\epsilon$-transducer has to have
at least two causal states and is Markovian. Then, one can evaluate the output
and the states will split in two classes $r_{1}=\\{1,\ldots,n\\}$ and
$r_{2}=\\{n+1,\ldots,2n\\}$ that correspond to the two causal states of the
output. As with the case of $n=3$ it can be shown that

  1. 1.

At least one state from each of the two classes, $r_{1}=\\{1,\ldots,n\\}$ and
$r_{2}=\\{n+1,\ldots,2n\\}$, needs to be recurrent.

  2. 2.

States $n+2,\ldots,2n$ of equivalence class $r_{2}$ can not be transient.

  3. 3.

State 1 of equivalence class $r_{1}$ can not be transient.

  4. 4.

With states $1,5,\ldots,2n$ recurrent, states $2,\dots,n$ of class $r_{1}$
alone can not be transient: they are either all recurrent or all transient.

  5. 5.

If states $2,\dots,n$ are all transient, state $n+1$ of equivalence class
$r_{2}$ can’t be recurrent.

which once again leads to two possibilities:

  1. 1.

All states are recurrent.

  2. 2.

Only states $1,n+2,\ldots,n$ are recurrent.

The first always corresponds to the trivial solution while the second leads to
a family of input-dependent solutions, all of which have a classical
complexity of 0.918 when driven by $\mathcal{B}_{n}$ as in the case with
$n=3$. From the structure of the obtained solutions, the maximal fidelity
constraint is found as

$\displaystyle F_{12}=\min$
$\displaystyle\left\\{\sqrt{t^{00}_{11}},\sqrt{t^{11}_{12}},\sqrt{t^{12}_{12}},\ldots,\sqrt{t^{1,n-2}_{12}}\,,\right.$
$\displaystyle\,\,\,\,\,\,\,\,\,\left.\sqrt{\frac{1-t^{11}_{12}p_{01}-\ldots-t^{1,n-2}_{12}p_{n-2}}{2-p_{01}-\ldots-
p_{n-2}}}\right\\}\,.$ (30)

The maximal minimum value is attained when
$t_{12}^{11}=\ldots=t_{1,n-2}^{11}=\nicefrac{{1}}{{2}}$ and the unconstrained
first term obeys $t_{12}^{11}\geq\nicefrac{{1}}{{2}}$. Once again, if we set
$t_{12}^{11}=1$ we obtain the $\epsilon$-transducer described in the main
text.

We can also derive an upper bound on the quantum complexity, which is between
the value $Q_{\mathcal{B}_{3}\rightarrow\mathcal{A}}\approx 0.833$ for the
case $n=4$ and approaches the classical complexity from below for increasing
$n$. To see that, consider the $\epsilon$-transducers of the main text and the
encoding of causal states of the classical $\epsilon$-transducers to the
quantum states as $|s_{i}\rangle=\otimes_{x}|s_{i}^{x}\rangle$ with
$|s_{i}^{x}\rangle=\sum_{k}\sum_{y}\sqrt{T_{ik}^{(y|x)}}|y\rangle|k\rangle$
[8, 5], from which we explicitly obtain

$\displaystyle|s_{0}^{x}\rangle$
$\displaystyle=\frac{1}{\sqrt{2}}|1\rangle\left(|1\rangle+|2\rangle\right)\,,$
$\displaystyle|s_{1}^{x}\rangle$ $\displaystyle=|1\rangle|1\rangle$ (31)

for all $x\neq 0$, while

$\displaystyle|s_{0}^{0}\rangle=|s_{1}^{0}\rangle=|0\rangle|0\rangle\,,$ (32)

when $x=0$. It follows that

$\displaystyle\langle
s_{1}|s_{2}\rangle=\left(\frac{1}{\sqrt{2}}\right)^{n-1}.$ (33)

The Gram matrix is:

$\displaystyle
G=\begin{pmatrix}\frac{1}{3}&\frac{\sqrt{2}}{3}\left(\frac{1}{\sqrt{2}}\right)^{n-1}\\\
\frac{\sqrt{2}}{3}\left(\frac{1}{\sqrt{2}}\right)^{n-1}&\frac{2}{3}\\\
\end{pmatrix}\,,$ (34)

and its eigenvalues are

$\displaystyle\lambda_{\pm}=\frac{1}{2}\pm\frac{\sqrt{1+2^{-n+4}}}{6}.$ (35)

The quantum entropy is then

$\displaystyle
Q_{\mathcal{B}_{n}\rightarrow\mathcal{A}}^{\text{upper}}=-\sum_{i=\pm}\lambda_{i}\log\lambda_{i}\,.$
(36)

For $n=4$ we obtain the value
$Q_{\mathcal{B}_{3}\rightarrow\mathcal{A}}^{\text{upper}}\approx 0.833$. The
value increases with increasing $n$ and in the limit of large $n$ we recover
the classical distribution
$\hat{\varphi}=\\{\nicefrac{{1}}{{3}},\nicefrac{{2}}{{3}}\\}$ as expected.
Thus the quantum complexity of an optimal model will assume a value
constrained by the double inequality

$\displaystyle Q_{\mathcal{B}_{n}\rightarrow\mathcal{A}}^{\text{upper}}\geq
Q^{\text{opt}}_{\mathcal{B}_{n}\rightarrow\mathcal{A}}\geq 0.55\,.$ (37)

The process to obtain the channels from $\mathcal{A}$ to $\mathcal{B}_{n}$ is
in principle the same but the number of classical solutions is in general
bigger than that of the case from $\mathcal{B}_{n}$ to $\mathcal{A}$, which
makes a systematic presentation not practical. However, for our purposes it
suffices to show that there do not exist $\epsilon$-transducers that can beat
the classical complexity of producing $\mathcal{B}_{n}$ regardless of input.
We first note that in process $\mathcal{A}$ all probabilities are
$\nicefrac{{1}}{{2}}$, while, on the other hand, by assumption all emissions
of $\mathcal{B}_{n}$ happen with probabilities $p_{i,j}\neq
p_{k,l}\neq\nicefrac{{1}}{{2}}$ for all $i,j,k,l$. With increasing $n$ it
becomes obvious that more states are necessary to correctly reproduce the
output process $\mathcal{B}_{n}$. In fact, one needs at least the same number
of states, $n$, as that of $B_{n}$, otherwise the probabilities can not be
reproduced. It remains to show that the distribution over the causal states of
the $\epsilon$-transducers and of $B_{n}$ do in fact coincide. Since the
$\epsilon$-transducers that map $\mathcal{A}$ to $\mathcal{B}_{n}$ are of pure
feedback Markov order 1, the transition matrices of the joint process
$J^{(x,y)}$ are split into sub-blocks, each of which, corresponds to a unique
state of the output process $B_{n}$, as well as a unique state of the
$\epsilon$-transducers. Since the flow of probability in and out of these sub-
blocks follows that of the output process, they must have the same stationary
distribution and thus the same statistical complexity. Thus, all these maps
when driven by $\mathcal{A}$ have the same statistical complexity as that of
the process $\mathcal{B}_{n}$.

##  Appendix B Appendix B: Classical complexity of $\hat{T}_{n}$

First we obtain the stationary distribution of process $\mathcal{A}$ by
solving the simultaneous equations $\pi_{0}=\nicefrac{{\pi_{1}}}{{2}}$ and
$\pi_{0}+\pi_{1}=1$ the first of which follows directly from Fig. 2 and the
second reflects the fact that $\pi$ is a probability distribution. The
solution is
$\pi=(\pi_{0},\pi_{1})=\left(\nicefrac{{1}}{{3}},\nicefrac{{2}}{{3}}\right)\,.$
Having obtained the stationary distribution, we can calculate the
probabilities of emitting a certain symbol through
$\Pr(x)=\sum_{i=0,1}\pi_{i}\Pr(x|\pi_{i})\,.$ We explicitly find the values
$\left\\{\Pr(0),\Pr(1),\Pr(2)\right\\}=\left\\{\nicefrac{{1}}{{3}},\nicefrac{{1}}{{2}},\nicefrac{{1}}{{6}}\right\\}$.
Then, by using the properties of the $\epsilon$-transducers $\mathcal{T}_{n}$,
we can evaluate the stationary distribution given the input $\mathcal{A}$.
Specifically, by noting that every output of the $\epsilon$-transducers leads
to a transition to the state with the same label, the equations for the
stationary distribution $\varphi$ are given in terms of the probabilities of
receiving a symbol 0,1 or 2 from the input, $\Pr(0),\Pr(1)$ and $\Pr(2)$. For
$n\geq 3$ and under the assumption
$p_{i,j}\approx\nicefrac{{1}}{{n-1}}\,,\forall i,j$ we have the stationary
distribution

$\displaystyle\varphi_{0}$
$\displaystyle=\Pr(0)\,\,,\,\,\varphi_{2}=\frac{\Pr(1)}{n-1}+\Pr(2)\,\,,$
$\displaystyle\varphi_{j}$
$\displaystyle=\frac{\Pr(1)}{n-1}\,,j=1,3,\ldots,n-1\,.$ (38)

The classical complexity follows

$\displaystyle C_{\mathcal{A}\rightarrow\mathcal{B}_{n}}=$
$\displaystyle-\Pr(0)\log\Pr(0)$ $\displaystyle-$
$\displaystyle(n-2)\left(\frac{\Pr(1)}{n-1}\right)\log\left(\left(\frac{\Pr(1)}{n-1}\right)\right)$
$\displaystyle-$
$\displaystyle\left(\frac{\Pr(1)}{n-1}+\Pr(2)\right)\log\left(\frac{\Pr(1)}{n-1}+\Pr(2)\right).$
(39)

##  Appendix C Appendix C: The upper bound
$Q^{\text{upper}}_{\mathcal{A}\rightarrow\mathcal{B}_{n}}$.

We can derive an explicit upper bound,
$Q^{\text{upper}}_{\mathcal{A}\rightarrow\mathcal{B}_{n}}$, on the quantum
entropy of the $\epsilon$-transducer from $\mathcal{A}$ to $\mathcal{B}_{n}$
in terms of a small perturbation parameter $\delta$.

Note that in the limit where all probabilities are the same, i.e.
$p_{ij}=p_{kl}=\nicefrac{{1}}{{n-1}}\,,\forall i,j,k,l$, the memory state
becomes pure since $\rho=\sum_{i}\varphi_{i}|s_{i}\rangle\\!\langle
s_{i}|=|s\rangle\\!\langle s|$, as all quantum causal states reduce to the
same state
$|s_{i}\rangle\equiv|s\rangle=|0\rangle|0\rangle\left(\sum_{j=1}^{n}\frac{|j\rangle|j\rangle}{\sqrt{n-1}}\right)|2\rangle|2\rangle\ldots|n\rangle|n\rangle$
for all $i$.

On the other hand, if we make a small perturbation of the probabilities around
the value $\nicefrac{{1}}{{n-1}}$ so that $p_{ij}=\frac{1+\delta_{ij}}{n-1}$,
with $\lvert\delta_{ij}\rvert\leq\delta$ for some small $\delta>0$, we have
the state of the memory $\sigma=\sum_{i}\varphi_{i}|s_{i}\rangle\\!\langle
s_{i}|$. Then, the fidelity of the perturbed state, $\sigma$, with the memory
state at the limit, $\rho$, is lower bounded according to

$\displaystyle F(\rho,\sigma)$ $\displaystyle=\langle
s|\sigma|s\rangle=\sum_{i}\varphi_{i}\left(\sum_{j=1}^{n-1}\sqrt{\frac{p_{ij}}{n-1}}\right)^{2}$
$\displaystyle\geq\frac{1}{2}+\frac{1}{2}\sqrt{1-\delta^{2}}\equiv
F_{\text{min}}(\delta)\,,$ (40)

where we have used the fact that the minimum of a concave function over a
convex set must be attained at the boundary. Specifically, the minimum occurs
when half the $p_{ij}$ are equal to $\frac{1+\delta}{n-1}$ and the other half
to $\frac{1-\delta}{n-1}$ for the even case, while for the odd case one is
equal to $\frac{1}{n-1}$. This immediately implies an upper bound on the trace
distance between the two states, $T\equiv
T(\rho,\sigma)=\nicefrac{{\left\lVert\rho-\sigma\right\rVert_{1}}}{{2}}$,
through the inequality $T(\rho,\sigma)\leq\sqrt{1-F(\rho,\sigma)}$, that is,

$\displaystyle T(\rho,\sigma)\leq
T_{\max}(\delta)=\sqrt{1-F_{\min}(\delta)}\,.$ (41)

Up to third order in $\delta$ we see that
$T_{\max}(\delta)=\frac{\delta}{2}+\mathcal{O}(\delta^{3})$.

Finally we employ a result that upper bounds the difference of von Neumann
entropies in terms of their trace norm distance [30]. Specifically,

$\displaystyle\lvert S(\rho)-S(\sigma)\rvert\leq T\log_{2}(d-1)+H({T,1-T})\,,$
(42)

where $T\equiv T(\rho,\sigma)$ denotes the trace norm distance and $H$ denotes
the Shannon entropy, $H(p)=-\sum_{i}p_{i}\log_{2}p_{i}$. Noting that the
function on the right hand side of last inequality is monotonically increasing
in the range $T\in[0,\nicefrac{{d-1}}{{d}}]$ and the fact that for
sufficiently small $\delta$ and large $n$, $T_{\max}(\delta)$ is always inside
this range, an upper bound is obtained by substituting $T_{\max}(\delta)$ for
$T$.

Since the von Neumann entropy of $\rho=|s\rangle\\!\langle s|$ is zero as it
is a pure state, we have the upper bound on the quantum entropy of $\sigma$,
$S(\sigma)\equiv Q_{\mathcal{A}\rightarrow\mathcal{B}_{n}}\leq
Q^{\text{upper}}_{\mathcal{A}\rightarrow\mathcal{B}_{n}}$,

$\displaystyle
Q^{\text{upper}}_{\mathcal{A}\rightarrow\mathcal{B}_{n}}=T_{\max}(\delta)\log_{2}(n-1)+H(T_{\max}(\delta),1-T_{\max}(\delta))\,.$
(43)

For example, in the case of $n=3$ and for perturbations no larger than
$\delta=10^{-2}$ the quantum complexity is upper bounded as $Q=S(\sigma)\leq
0.097$. In practice, however, the quantum complexity can be significantly
lower than the bound predicts. Nevertheless, it suffices for our purposes.

Note that even though the causal states as defined in the main text are
embedded in a Hilbert space of dimension
$(\lvert\mathcal{Y}\rvert\lvert\mathcal{S}\rvert)^{\lvert\mathcal{X}\rvert}$,
there exists a unitary transformation that maps them to a subspace of
dimension of at most $\lvert\mathcal{S}\rvert$ [12]. Thus, we can set $d=n$
and the last bound follows.

The above inequality bound should be interpreted in the following way: given a
value of $n$ there exists a choice of $\delta$ that upper and lower bounds the
perturbation of the probabilities of the family of processes $\mathcal{B}_{n}$
around the value $\frac{1}{n-1}$ such that the quantum complexities of the
models for all values of $n^{\prime}\leq n$ are sufficiently close to 0. This
in turn shows, that for every value of $n$ there exist processes $\mathcal{A}$
and $\mathcal{B}_{n}$ such that the channels from $\mathcal{A}$ to
$\mathcal{B}_{n}$ have classical complexities logarithmically diverging with
$n$ while their quantum complexities are sufficiently close to 0, and
certainly less than the minimum theoretical bound for the quantum complexity
of the channels from $\mathcal{B}_{n}$ to $\mathcal{A}$.