How Quantum Agents Can Change Which Strategies Are More Complex Spiros Kechrimparis, Nix Barnett, Mile Gu, Hyukjoon Kwon Abstract Whether winning blackjack or navigating busy streets, achieving desired outcomes requires agents to execute adaptive strategies, strategies where actions depend contextually on past events. In complexity science, this motivates memory as an operational quantifier of complexity: given two strategies, the more complex one demands the agent to track more about the past. Here, we show that conclusions about complexity fundamentally depend on whether agents can process and store quantum information. Thus, while classical agents might find Strategy 𝒜 \mathcal{A} more complex to execute than Strategy ℬ \mathcal{B} , quantum agents can reach the opposite conclusion. We derive sufficient conditions for such contradictory conclusions and illustrate the phenomenon across multiple scenarios. As a byproduct, our results yield an information-theoretic lower bound on the minimal memory required by any agent - classical or quantum - to execute a given strategy. I Introduction Agents performing complex tasks surround us, from biological organisms adapting to dynamic environments, artificial intelligence engaging in conversation, to the hypothetical Maxwell’s demon that tracks and sorts fast- and slow-moving molecules to reduce entropy. Fundamentally, such autonomous agents operate by (i) interacting with the environment to gather data, (ii) storing relevant data in memory, and (iii) processing this information to decide appropriate future actions. In this way, an agent can execute complex strategies that demand contextual decisions - decisions that depend not only on what the agent currently sees, but also on what happened many time steps prior. The capability to do so, however, depends crucially on memory. Consider a simple example. An agent observes a coin that is flipped repeatedly at discrete time steps. At each time step, the agent is required to announce if the present outcome matches that of the outcome two steps prior. To achieve an optimal success rate, the agent needs memory capable of storing two bits, which is enough to remember the two outcomes from their immediate past. Should we force such an agent to remember a single bit, its performance will invariably degrade. Memory limitations severely constrain which strategies an agent can and cannot execute. Consequently, the memory needed to implement a target strategy is a key measure of the strategy’s intrinsic complexity Barnett and Crutchfield 2015 . Known as statistical complexity, the measure represents the minimal past information any agent executing the strategy must track about its past inputs and outputs. Such a measure then produces a natural hierarchy of what strategies are simple and what strategies are complex. With the advent of quantum computers, we anticipate that agents harnessing quantum memory can execute strategies with less memory Thompson et al. 2017 ; Elliott et al. 2022 , but we may still expect the relative order of which strategies are more complex to remain the same. Figure 1: Depiction of a scenario involving an agent who is deciding which of two strategies \mathcal{A} and \mathcal{B} to execute. They may in principle use a device with either a classical or a quantum memory to that effect, each type coming with a different operational memory constraint. When reacting to some input stimuli coming from a stochastic process \mathcal{I} , the classical (left) and quantum (right) memory costs C^{\mathcal{A}}_{\mathcal{I}},C^{\mathcal{B}}_{\mathcal{I}} and Q^{\mathcal{A}}_{\mathcal{I}},Q^{\mathcal{B}}_{\mathcal{I}} of executing the two strategies \mathcal{A} and \mathcal{B} by the agent are shown. The red-shaded planes represent the postulated classical (left) and quantum (right) memory constraints. In this visualisation, a classical agent can only execute strategy \mathcal{A} , while a quantum agent can only execute strategy \mathcal{B} ; they arrive at contradictory conclusions on which strategy is harder to implement and thus more complex. Here, we illustrate otherwise. We show that when comparing the relative complexity of two strategies, there is a classical-quantum ambiguity of complexity . Which strategy requires an agent to track more memory depends crucially on whether they are using classical or quantum memory. Varying a given strategy can make it more complex for classical agents and yet be more easily executed by a quantum agent (see Fig. 1 ). Our results generalise a previous finding in predictive modelling of stochastic processes Aghamohammadi et al. 2017 ; Ghafari et al. 2022 to the case of input-output processes. We derive sufficient conditions to detect whether two strategies will exhibit ambiguity of complexity or signal its absence. We demonstrate this phenomenon in various settings, including (i) two agents implementing different strategies while reacting to the same input stimulus, (ii) a single agent implementing a single strategy when reacting to two different input stimuli, and (iii) an agent and their operationally inverse agent implementing the inverse actions. Finally, we show that the absence of an absolute relative ordering of strategies is not always reflected in the output actions of the agents when considered alone as stochastic processes. As a byproduct, our work also establishes channel excess entropy as a non-trivial lower bound on the minimal amount of information any agent, regardless of its underlying physics, must store about the past to execute a given strategy. The article is structured as follows. Sec. II introduces our framework and reviews the agentic realisations of stochastic processes and input-output processes, relevant informational theoretic quantities, as well as the current state-of-the-art quantum generalisations. Sec. III describes our main results, including sufficient conditions that can detect the presence or absence of ambiguity of complexity. In Sec. IV we present scenarios and explicit examples that exhibit such ambiguous ordering between the classical and quantum complexities. Finally, Sec. V shows that this ambiguity is not always reflected in the stochastic processes defined by their outputs. II Framework II.1 Agents In a minimal definition, an agent is a system interacting with their environment, recording received stimuli, and outputting appropriate actions in order to implement desired strategies (see Fig. 2 ). Computational Mechanics formalises these concepts. The inputs the agent receives and their output actions can often be taken to be from a discrete stochastic process and the adaptive strategies that an agent implements are described as input-output processes . In this framework, agents are thus automatons that interact with an environment at discrete time steps Barnett and Crutchfield 2015 ; Thompson et al. 2017 ; Elliott et al. 2022 . An input stimulus x_{t} received from the environment at time t leads to a reaction of the agent, who outputs an action y_{t} , both described by random variables X_{t} and Y_{t} taking values from some discrete alphabets \mathcal{X} and \mathcal{Y} . Thus, from a mathematical point of view, the streams of inputs and outputs of the agents define stochastic processes, while the agents themselves are implementing input-output processes or channels Barnett and Crutchfield 2015 , also referred to as adaptive strategies Elliott et al. 2022 . To optimally characterise the minimum information an agent needs to track, in general, we need to consider semi-infinite histories of joint inputs and outputs (see next section), which we denote by \smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\smash{-} \hfil\displaystyle{(X,Y)}\hfil . We use the following definition of adaptive agents Elliott et al. 2022 : Definition 1 . An adaptive agent is defined by the tuple (\mathcal{X},\mathcal{Y},S,\epsilon,\Lambda) , where i) \mathcal{X} is the set of input stimuli the agent can recognise, ii) \mathcal{Y} is the set of output actions the agent can perform, iii) \mathcal{S}=\{s_{i}\} is the set of memory states in their memory system, labeled by some index i=1,\ldots,N , iv) \epsilon:\vbox{\halign{#\cr$\smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\smash{-}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{(X,Y)}\hfil$\crcr}}\rightarrow\mathcal{S} is an encoding function that determines the memory state to which the agent assigns each history \smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\smash{-} \hfil\displaystyle{(x,y)}\hfil , v) \Lambda:\mathcal{X}\times\mathcal{S}\rightarrow\mathcal{Y}\times S is the agent’s policy, describing how the agent selects action y in response to stimulus x given their current internal state, and how the memory state is updated. The complexity of an agent can then be characterised by how much information the agent must track within its memory - often quantified by the information entropy of \mathcal{S} (see Sec. II.3 ). Fundamentally, this represents the minimal amount of memory needed to execute each instance of such an agent. As we outline in the following sections, this notion of complexity then leads to a natural definition of complexity for an adaptive strategy. Namely, each strategy may be realised by a plethora of different agents – its complexity is then given by the complexity of its agentic realisation, when minimised over all such agents Crutchfield 1994 ; Crutchfield and Young 1989 ; Shalizi and Crutchfield 2001 ; Crutchfield 2012 . Traditionally, the memory is considered to be classical, and minimisation is defined with that in mind. Quantum mechanics, however, allow S to be quantum mechanical - broadening the class of available agents and thus may lower the complexity of a strategy Elliott et al. 2022 . In the following sections, we provide precise mathematical definitions of complexities, as well as other relevant information measures. Figure 2: Visual representation of an agent receiving information from their environment, storing the information to a memory, and outputting appropriate actions after processing the stored information according to a desired strategy. II.2 Classical Modelling of Stochastic Processes 1 2 0:1 1:1 Figure 3: The \epsilon -machine of the Period-2 process. The inputs and outputs of an agent can be thought of as the emissions of a discrete-time, discrete-alphabet stochastic process; however, they can also be considered to be chosen freely. Such a temporal stochastic process \smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\mathord{\rightharpoonup} \hfil\displaystyle{Y}\hfil is an infinite sequence \vbox{\halign{#\cr$\smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\mathord{\rightharpoonup}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{Y}\hfil$\crcr}}\equiv\ldots Y_{-2}Y_{-1}Y_{0}Y_{1}Y_{2}\ldots of discrete random variables Y_{t}\,,t\in\mathbb{Z} that take values over a countable alphabet \mathcal{Y} . By capital symbols, we denote the random variables, while with lowercase symbols, their specific realisations. Finite blocks of outcomes are represented by the sequence of random variables Y_{i}Y_{i+1}\ldots Y_{j-1} , denoted by Y_{i:j} . By \vbox{\halign{#\cr$\smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\smash{-}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{Y}\hfil$\crcr}}=\ldots Y_{-2}Y_{-1} and \vbox{\halign{#\cr$\smash{-}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\mathord{\rightharpoonup}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{Y}\hfil$\crcr}}=Y_{0}Y_{1}\ldots we denote semi-infinite pasts and futures. A stochastic process is defined through its word probabilities \mathrm{Pr}(Y_{t:t+L})\equiv\{\mathrm{Pr}(Y_{t:t+L}=y_{t:t+L})\} . Here we consider stochastic processes that are stationary , processes whose word probabilities are invariant under time translation. Another property we require is ergodicity , processes whose samples give good estimates of the probabilities. For example, consider a Biased Coin Process describing a series of independent coin flips, defined through the word probabilities \mathrm{Pr}(Y_{0:T})=\mathrm{Pr}{(Y_{0})}\ldots\mathrm{Pr}{(Y_{T-1})} , that is, the process is independent and identically distributed (IID), and \mathrm{Pr}{(Y_{t})}=\mathrm{Pr}{(Y_{\tau})} for any t,\tau . Another example is a Period-2 Process that alternates emissions of 0 and 1 and thus its word probabilities are \mathrm{Pr}(Y_{t:\tau})=\mathrm{Pr}{(\ldots 101010\ldots)}=\mathrm{Pr}{(\ldots 010101\ldots)}=\nicefrac{{1}}{{2}} for any t,\tau . Optimal prediction models of stochastic processes are the focus of Computational Mechanics Crutchfield 1994 ; Crutchfield and Young 1989 ; Shalizi and Crutchfield 2001 ; Crutchfield 2012 . Here, each instance of a process with a specific past \smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\smash{-} \hfil\displaystyle{y}\hfil has a corresponding conditional future P(\vbox{\halign{#\cr$\smash{-}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\mathord{\rightharpoonup}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{Y}\hfil$\crcr}}|\vbox{\halign{#\cr$\smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\smash{-}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{y}\hfil$\crcr}}) . The task of prediction is to replicate this conditional future by storing sufficient information about \smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\smash{-} \hfil\displaystyle{y}\hfil . The optimal model is the one that stores the minimal amount of information, while still being able to replicate P(\vbox{\halign{#\cr$\smash{-}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\mathord{\rightharpoonup}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{Y}\hfil$\crcr}}|\vbox{\halign{#\cr$\smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\smash{-}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{y}\hfil$\crcr}}) . This leads to the notion of partitioning pasts into equivalence classes that correspond to identical future predictions, known as causal states . The causal states as well as the transition probabilities between them define the so-called \epsilon -machine . More formally, the \epsilon -machine of a stochastic process is a tuple (\mathcal{Y};\mathcal{S};\mathcal{T}) , where \mathcal{Y} denotes the output alphabet, \mathcal{S} the causal state set, and \mathcal{T} the transition matrix set of the process. The \epsilon -machine is the unique , minimal and unifilar 1 1 1 Unifilarity is the property that guarantees determinism on the next state of the machine given the current state and emission presentation of the stochastic process. The causal states essentially represent equivalent classes of pasts that lead to the same futures through an equivalence relation \sim_{\epsilon} : \displaystyle\vbox{\halign{#\cr$\smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\smash{-}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{y}\hfil$\crcr}}\sim_{\epsilon}\vbox{\halign{#\cr$\smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\smash{-}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{y}\hfil$\crcr}}{}^{\prime}\Longleftrightarrow\mathrm{Pr}(\vbox{\halign{#\cr$\smash{-}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\mathord{\rightharpoonup}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{Y}\hfil$\crcr}}|\vbox{\halign{#\cr$\smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\smash{-}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{Y}\hfil$\crcr}}=\vbox{\halign{#\cr$\smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\smash{-}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{y}\hfil$\crcr}})=\mathrm{Pr}(\vbox{\halign{#\cr$\smash{-}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\mathord{\rightharpoonup}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{Y}\hfil$\crcr}}|\vbox{\halign{#\cr$\smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\smash{-}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{Y}\hfil$\crcr}}=\vbox{\halign{#\cr$\smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\smash{-}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{y}\hfil$\crcr}}^{\prime})\,. With the causal states having been obtained the presentation is mathematically given as an edge-emitting (or Mealy) Hidden Markov Model Travers and Crutchfield 2025 . The transitions between causal states are given by a set of transition matrices , one for each alphabet symbol, \mathcal{T}\equiv\{T^{(y)}\}_{y\in\mathcal{Y}}\,. Their elements are explicitly given by T^{(y)}_{ij}=\Pr(Y_{t}=y,S_{t+1}=s_{j}|S_{t}=s_{i})\,, representing the probability of transitioning from causal state s_{i} to state s_{j} while emitting the symbol y . An \epsilon -machine can be visually represented as a graph consisting of nodes and labelled arrows; the nodes correspond to the causal states and the arrows to the transitions between the causal states with labels of the form y:p , with y be being the output symbol and p the corresponding probability. For instance, the \epsilon -machine of the aforementioned Period-2 process that deterministically alternates between outputting ‘0’ and ‘1’ is shown in Fig. 3 . A quantity of importance is given in the following definition. Definition 2 . The excess entropy \mathbf{E} of a stochastic process is the mutual information between its semi-infinite past, and its semi-infinite future output: \displaystyle\mathbf{E}=I[\vbox{\halign{#\cr$\smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\smash{-}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{Y}\hfil$\crcr}};\vbox{\halign{#\cr$\smash{-}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\mathord{\rightharpoonup}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{Y}\hfil$\crcr}}]. The excess entropy captures the information from the past contained in the future; it represents the minimal amount of information that needs to be captured by any model of a process to correctly reproduce its behaviour. As the mutual information between two variables vanishes if the two variables are independent or share no information, it follows that excess entropy vanishes in the case of full randomness or full predictability and is non-zero between these two extreme cases. In this work, we are interested in the characterisation of complexity or structure. For a stochastic process, this is given by the statistical complexity , C . Intuitively, the statistical complexity is the amount of past information that needs to be stored in a memory to predict the process’ future behaviour. Formally, we have the following definition. Definition 3 . The statistical complexity is the Shannon entropy of the distribution over the causal states of the process’ \epsilon -machine, \displaystyle C=H[\mathcal{S}]=-\sum_{s_{i}\in\mathcal{S}}\pi_{i}\log\pi_{i}\,, (21) where \pi_{i}=\Pr(s_{i}) are the elements of the stationary distribution, the long-term probabilities of the \epsilon -machine being in causal state s_{i} . We remark that the stationary distribution can be directly evaluated as the principal left eigenvector of the total transition matrix T=\sum_{y}T^{(y)} . The statistical complexity is decoupled from the intrinsic randomness of the process; the latter is captured by the entropy rate Ellison et al. 2009 ; Barnett and Crutchfield 2015 , the amount of information or randomness generated per emission. Importantly, the excess entropy bounds from below the statistical complexity, with equality achieved for reversible processes Gu et al. 2012 . Proposition 1 . The excess entropy \mathbf{E} of a stochastic process lower bounds its statistical complexity C , \mathbf{E}\leq C . A proof of this statement was first given in Ref. Shalizi and Crutchfield 2001 and we give a variant of it in Appendix A . Thus, from the point of view of modelling, the last inequality sets an information-theoretic lower bound on the complexity that a model needs to capture to accurately reproduce the process. As the bound is not, in general, saturated even by the provably optimal classical models, we see that there is a fundamental overhead in classical modelling. II.3 Classical Modelling of Input-Output Processes So far we have only discussed the optimal modelling of stochastic processes, corresponding to agents that emit the same output behaviours regardless of input. In this work, we are interested in agents executing adaptive strategies, where output behaviour at each-time step depends on past inputs. From a mathematical point of view, adaptive strategies that agents execute can be described as channels or input-output processes . A channel is a coupling between two stochastic processes \mathcal{X} and \mathcal{Y} , where one is viewed as the input and the other as the output, and their optimal modelling has been considered in Ref. Barnett and Crutchfield 2015 . Specifically, we have the following definition. Definition 4 . Barnett and Crutchfield 2015 A channel or input-output process \vbox{\halign{#\cr$\smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\mathord{\rightharpoonup}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{Y}\hfil$\crcr}}|\vbox{\halign{#\cr$\smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\mathord{\rightharpoonup}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{X}\hfil$\crcr}} with input alphabet \mathcal{X} and output alphabet \mathcal{Y} is a collection of stochastic processes over alphabet \mathcal{Y} , where each process \vbox{\halign{#\cr$\smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\mathord{\rightharpoonup}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{Y}\hfil$\crcr}}|\vbox{\halign{#\cr$\smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\mathord{\rightharpoonup}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{x}\hfil$\crcr}} corresponds to a bi-infinite input sequence in \smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\mathord{\rightharpoonup} \hfil\displaystyle{\mathcal{X}}\hfil : \displaystyle\vbox{\halign{#\cr$\smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\mathord{\rightharpoonup}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{Y}\hfil$\crcr}}|\vbox{\halign{#\cr$\smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\mathord{\rightharpoonup}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{X}\hfil$\crcr}}\equiv\{\vbox{\halign{#\cr$\smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\mathord{\rightharpoonup}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{Y}\hfil$\crcr}}|\vbox{\halign{#\cr$\smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\smash{-}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{x}\hfil$\crcr}}\}_{\vbox{\halign{#\cr$\smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\mathord{\rightharpoonup}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{x}\hfil$\crcr}}\in\vbox{\halign{#\cr$\smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\mathord{\rightharpoonup}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{\mathcal{X}}\hfil$\crcr}}}. In other words, each fixed realisation \vbox{\halign{#\cr$\smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\mathord{\rightharpoonup}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{x}\hfil$\crcr}}=\ldots x_{-1}x_{0}x_{1}\ldots over the input alphabet \mathcal{X} is mapped to a stochastic process \vbox{\halign{#\cr$\smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\mathord{\rightharpoonup}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{Y}\hfil$\crcr}}|\vbox{\halign{#\cr$\smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\mathord{\rightharpoonup}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{x}\hfil$\crcr}} over alphabet \mathcal{Y} . In analogy to the case of stochastic processes, by defining an appropriate equivalence relation over joint input and output pasts, one obtains the channel’s causal states. Specifically, we have the equivalence relation \sim_{\epsilon} over joint pasts \vbox{\halign{#\cr$\smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\smash{-}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{z}\hfil$\crcr}}=\vbox{\halign{#\cr$\smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\smash{-}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{(x,y)}\hfil$\crcr}} : \displaystyle\vbox{\halign{#\cr$\smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\smash{-}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{(x,y)}\hfil$\crcr}}\sim_{\epsilon}\vbox{\halign{#\cr$\smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\smash{-}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{(x,y)}\hfil$\crcr}}^{\prime}\,\,\,\,\Longleftrightarrow \displaystyle\,\,\,\,\Pr\left(\vbox{\halign{#\cr$\smash{-}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\mathord{\rightharpoonup}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{Y}\hfil$\crcr}}|\vbox{\halign{#\cr$\smash{-}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\mathord{\rightharpoonup}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{X}\hfil$\crcr}},\vbox{\halign{#\cr$\smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\smash{-}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{(X,Y)}\hfil$\crcr}}=\vbox{\halign{#\cr$\smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\smash{-}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{(x,y)}\hfil$\crcr}}\right) \displaystyle\,\,\,\,\,\,\,\,=\Pr\left(\vbox{\halign{#\cr$\smash{-}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\mathord{\rightharpoonup}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{Y}\hfil$\crcr}}|\vbox{\halign{#\cr$\smash{-}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\mathord{\rightharpoonup}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{X}\hfil$\crcr}},\vbox{\halign{#\cr$\smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\smash{-}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{(X,Y)}\hfil$\crcr}}=\vbox{\halign{#\cr$\smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\smash{-}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{(x,y)}\hfil$\crcr}}^{\prime}\right)\,, that partitions the set of joint pasts \vbox{\halign{#\cr$\smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\smash{-}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{\mathcal{Z}}\hfil$\crcr}}=\vbox{\halign{#\cr$\smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\smash{-}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{(\mathcal{X},\mathcal{Y})}\hfil$\crcr}} of all input-output pasts into equivalent classes. These classes are the causal states of the input-output process denoted by \mathcal{S} . Transitions between causal states are described by transition matrices \mathcal{T}\equiv\{T^{(y|x)}\}_{x\in\mathcal{X},y\in\mathcal{Y}}\,, with elements T^{(y|x)}_{ij}=\Pr(Y_{t}=y,S_{t+1}=s_{j}|X_{t}=x,S_{t}=s_{i})\,. Note that the transition matrices are input-dependent , as are all informational quantities we are interested in. Definition 5 . The \epsilon -transducer of an input-output process is defined as the tuple (\mathcal{X},\mathcal{Y},\mathcal{S},\mathcal{T}) consisting of the input and output alphabets, the set of causal states, and the conditional transition probabilities. The \epsilon -transducer is the unique and maximally predictive, unifilar 2 2 2 Unifilarity of an \epsilon -transducer is the property that guarantees determinism on the next state of the machine given the current state, as well as current input and emission Barnett and Crutchfield 2015 presentation of a channel that minimises the statistical complexity Barnett and Crutchfield 2015 . As with \epsilon -machines, \epsilon -transducers can be visually represented as graphs consisting of nodes and labelled arrows; the nodes correspond to the causal states and the arrows to the transitions between the causal states with labels of the form y|x:p , where x and y are the input and output symbols, respectively, and p the corresponding probability. For instance, a one-step delay channel , which at each time step outputs the input at the previous time step, is shown in Fig. 4 . 1 2 0|1:1 1|0:1 0|0:1 1|1:1 Figure 4: A one-step delay channel. An input-dependent statistical complexity of the \epsilon -transducer is defined as the Shannon entropy of the stationary distribution, \pi_{\mathcal{I}} , over the causal states of the \epsilon -transducer, where the index \mathcal{I} denotes the fact that the distribution depends on the input process \mathcal{I}=\vbox{\halign{#\cr$\smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\mathord{\rightharpoonup}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{X}\hfil$\crcr}} . In general, different input processes will drive the \epsilon -transducer to different stationary distributions over its causal states. Specifically, we have: Definition 6 . The input-dependent statistical complexity C_{\mathcal{I}} of an \epsilon -transducer, when driven by an input-process \mathcal{I}=\vbox{\halign{#\cr$\smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\mathord{\rightharpoonup}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{X}\hfil$\crcr}} , is given by \displaystyle C_{\mathcal{I}}=H(\pi_{\mathcal{I}})=-\sum_{i=1}^{|\mathcal{S}|}\pi_{\mathcal{I}}(s_{i})\log\pi_{\mathcal{I}}(s_{i})\,, (54) where \pi_{\mathcal{I}}(s_{i}) denotes the probability of being in causal state s_{i} . Finally, one can define an input-independent quantity by taking the supremum over all possible input stochastic processes, obtaining the channel complexity , \overline{C}=\sup_{X}C_{X} , which gives an upper bound on the complexity of the \epsilon -transducer. A further upper bound is given by the topological complexity , C_{0} , obtained as the Shannon entropy of the uniform distribution over the causal states of the \epsilon -transducer. However, not all \epsilon -transducers can be driven to a uniform distribution over causal states, and thus this bound is not always attainable. In this work, we will not use the input-independent quantities as we are interested in the behaviour of the complexities of agents when driven by a specific given input stimulus. II.4 Quantum Modelling of Stochastic Processes and Input-Output Processes Figure 5: Circuit representation of the implementation of a quantum agent (see main text). Recently there has been interest in constructing quantum models of stochastic processes and exploring potential advantages. Several results have emerged: from exhibiting memory advantages for both stochastic Gu et al. 2012 ; Suen et al. 2017 ; Garner et al. 2017 ; Ghafari et al. 2019 ; Elliott et al. 2020 , and input-output processes Thompson et al. 2017 ; Elliott et al. 2022 , to causal asymmetry Thompson et al. 2018 ; Kechrimparis et al. 2023 . Quantum model design assigns the causal states of the optimal classical model to states of a quantum system, along with a quantum evolution and a measurement protocol to extract the classical outputs. A quantum model is said to be faithful if the output conditional word probabilities are indistinguishable from those of the classical one. In contrast to the classical case, proving the optimality of a candidate quantum model among all quantum models is highly nontrivial. The crux of the problem is to choose the quantum causal states so that to minimise the von Neumann entropy while remaining statistically faithful. Given the intricate behaviour of the von Neumann entropy Jozsa and Schlienz 2000 , optimality has only been proven in a few specific cases. Nevertheless, there exist systematic procedures to construct quantum models that perform better than any classical models in the event that optimal classical models still exhibit causal waste. This occurs whenever the process at each time step is logically irreversible Gu et al. 2012 : if there exist two distinct states of the \epsilon -machine such that upon emitting the same symbol, they transition with nonzero probabilities to a coinciding state. Analogously, a quantum model of an input-output process exhibits memory advantage whenever the process is step-wise inefficient Thompson et al. 2017 : there exist two distinct causal states of the \epsilon -transducer such that for any input symbol there is non-zero probability that they transition to the same causal state while emitting a coinciding output. We briefly review quantum models of input-output processes that guarantee improvement over classical models whenever the \epsilon -transducer is step-wise inefficient. Note that the case of stochastic processes is trivially included and corresponds to an input alphabet of exactly one symbol; thus, in the following, the case of passive stochastic processes is implicitly considered. It was previously shown that quantum agents can be optimised by considering only those obeying the following constraints Elliott et al. 2022 : (i) The agent receives input stimuli x_{t} encoded in the computational basis states {|x_{t}\rangle} . (ii) The input stimulus is not consumed by the evolution of the agent; \Lambda preserves the input tape. (iii) The agent delivers output actions y_{t} via projective measurements in the computational basis states {|y_{t}\rangle} . (iv) The memory states are pure and in one-to-one correspondence with the strategy’s causal states \mathcal{S} . For instance, given an \epsilon -transducer with conditional transition probabilities T_{ij}^{(y|x)} , a particular encoding of causal states into quantum states Thompson et al. 2017 is given by \displaystyle|s_{i}\rangle=\otimes_{x}|s_{i}^{x}\rangle\,, (55) with \displaystyle|s_{i}^{x}\rangle=\sum_{k}^{\lvert\mathcal{S}\rvert}\sum_{y}^{\lvert\mathcal{Y}\rvert}\sqrt{T_{ik}^{(y|x)}}|y\rangle|k\rangle\,, (56) where summation over index k runs over the number of causal states (rows or columns of the transition matrices) and summation over y over the output symbols; |y\rangle denotes an orthonormal basis in a Hilbert space of dimension \lvert\mathcal{Y}\rvert while |k\rangle an orthonormal basis of dimension \lvert\mathcal{S}\rvert ; \otimes_{x} denotes the direct product over input symbols, x\in\mathcal{X} . Note that we have dropped the t subscript to not overload notation. A unitary is then acting to the encoded causal states plus ancillas followed by an appropriate measurement that extracts correctly the emissions of the process; in addition, the measurement also prepares the quantum state of the machine to the state that corresponds to the correct next causal state of the \epsilon -transducer. The unitary is implicitly defined through the equation \displaystyle U|s_{i}\rangle|x\rangle|0\rangle|0\rangle=\sum_{y}\sqrt{T_{ij}^{(y|x)}}|s_{j}\rangle|x\rangle|y\rangle|\psi\rangle, (57) where |x\rangle denotes the input stimulus encoded as a quantum state and |\psi\rangle ‘junk’ states that are being discarded. A schematic representation is shown in Fig. 5 , with the details of the encoding given in Ref. Thompson et al. 2017 , and a better approach introduced in Ref. Elliott et al. 2022 . As the process is repeated, the memory state is being updated accordingly, leading to the average state of the quantum memory, \displaystyle\rho=\sum_{i=1}^{|\mathcal{S}|}\pi_{\mathcal{I}}(s_{i})|s_{i}\rangle\!\langle s_{i}|\,, (58) when driven by an input process \mathcal{I}=\vbox{\halign{#\cr$\smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\mathord{\rightharpoonup}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{X}\hfil$\crcr}} , and where \pi_{\mathcal{I}}(s_{i}) is the long-term probability of being in causal state s_{i} . Definition 7 . The quantum complexity of a quantum agent is the von Neumann entropy of the average state of the quantum memory, \displaystyle Q_{\mathcal{I}}=-\mbox{tr}(\rho\log\rho)\,, (59) when driven by an input process \mathcal{I}=\vbox{\halign{#\cr$\smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\mathord{\rightharpoonup}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{X}\hfil$\crcr}} . It is clear that if the quantum states of the encoding are orthogonal, the complexity reduces to the classical complexity, showcasing the source of the quantum improvement. Thus, we generally have Q_{\mathcal{I}}\leq C_{\mathcal{I}} . We note that the same conclusion holds for passive stochastic processes, since a trivial input, i.e. an input process with an alphabet with a single symbol, reduces the case of input-output processes to the case of passive stochastic processes. Returning to the case of passive stochastic processes, even though the quantum complexity of an irreversible process is lower than that of the classical one, it is still lower bounded by the excess entropy. Proposition 2 . The quantum complexity Q of a quantum model is lower bounded by the excess entropy \mathbf{E} , \mathbf{E}\leq Q . This was first pointed out in Ref. Gu et al. 2012 but no proof was provided. Although we give the full proof in Appendix B , we sketch it here. A classical model maps pasts into causal states. Moreover, a quantum model consists of an encoding function that maps classical states of the \epsilon -machine to quantum states, as well as a quantum evolution that extracts the classical emissions. By iteration, the entire future can be generated. As the excess entropy is the mutual information between past and future classical emissions, the result follows from Holevo’s bound Holevo 1973 ; Nielsen and Chuang 2010 . III Classical-Quantum Ambiguity of Complexity of strategies \mathcal{I}_{\mathcal{A}} \mathcal{I}_{\mathcal{B}} \mathcal{A} \mathcal{B} \mathcal{O}_{\mathcal{A}} \mathcal{O}_{\mathcal{B}} Figure 6: The general setting involving two agents implementing strategies \mathcal{A} and \mathcal{B} , while reacting to stimuli \mathcal{I}_{\mathcal{A}} and \mathcal{I}_{\mathcal{B}} , respectively. We now show that scenarios involving agents implementing strategies while reacting to input stimuli can lead to different conclusions regarding the complexity of the behaviour they exhibit, depending on whether they employ classical or quantum memories. Specifically, we consider two agents executing two input-output processes \mathcal{A} and \mathcal{B} , while reacting to stimuli from some input processes \mathcal{I}_{\mathcal{A}} and \mathcal{I}_{\mathcal{B}} , respectively. When driven by these, the agents will emit outputs that define stochastic processes \mathcal{O}_{\mathcal{A}} and \mathcal{O}_{\mathcal{B}} , respectively. This general setting is shown pictorially in Fig. 6 . By C_{\mathcal{I}}^{\mathcal{A}},C_{\mathcal{I}}^{\mathcal{B}} and Q_{\mathcal{I}}^{\mathcal{B}},Q_{\mathcal{I}}^{\mathcal{B}} we denote the classical and quantum complexities of \mathcal{A} and \mathcal{B} when driven by inputs \mathcal{I}_{\mathcal{A}} and \mathcal{I}_{\mathcal{B}} respectively. Then, we have in general that the quantum complexities can be lower than the classical ones, that is, C_{\mathcal{I}}^{\mathcal{A}}\geq Q_{\mathcal{I}}^{\mathcal{A}} and C_{\mathcal{I}}^{\mathcal{B}}\geq Q_{\mathcal{I}}^{\mathcal{B}} . Moreover if, say, C_{\mathcal{I}}^{\mathcal{A}}>C_{\mathcal{I}}^{\mathcal{B}} , which implies that agent \mathcal{A} exhibits more complex behaviour according to a classical description, it is natural to expect a consistently assigned ordering by a quantum description, that is, Q_{\mathcal{I}}^{\mathcal{A}}>Q_{\mathcal{I}}^{\mathcal{B}} . In other words, naturally one would expect classical and quantum models of the two strategies to arrive at similar conclusions regarding which agent’s behaviour is more complex. However, we show that it is possible to arrive at contradictory conclusions. Result 1 . There is a classical-quantum ambiguity in the complexities of adaptive strategies executed by agents. We first derive mathematical conditions that indicate the presence of such an inconsistency and, in the following section, we consider illustrative scenarios and specific examples where this phenomenon manifests. Our approach involves first deriving an analogue of the excess entropy for an input-output process - which then bounds the minimal memory of any agent executing this process. Let \mathcal{I}=\vbox{\halign{#\cr$\smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\mathord{\rightharpoonup}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{X}\hfil$\crcr}} denote the input process to which an agent implementing an input-output process \mathcal{A} is reacting, and by \mathcal{O}=\vbox{\halign{#\cr$\smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\mathord{\rightharpoonup}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{Y}\hfil$\crcr}} the stochastic process defined by the agent’s output actions. We also denote by \mathcal{J}=\vbox{\halign{#\cr$\smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\mathord{\rightharpoonup}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{(X,Y)}\hfil$\crcr}} the stochastic process of joint inputs and outputs Barnett and Crutchfield 2015 . We remark that in the following, our notation is such that informational quantities which have input-dependence, such as those of input-output processes, will have a subscript signaling this fact. Definition 8 . The channel excess entropy \mathbf{E}^{\mathcal{A}}_{\mathcal{I}} from an input process \mathcal{I} to an output process \mathcal{O} is the mutual information between a channel’s infinite bivariate past, and its infinite future output given infinite future input: \displaystyle\mathbf{E}^{\mathcal{A}}_{\mathcal{I}}=I[\vbox{\halign{#\cr$\smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\smash{-}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{(X,Y)}\hfil$\crcr}};\vbox{\halign{#\cr$\smash{-}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\mathord{\rightharpoonup}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{Y}\hfil$\crcr}}|\vbox{\halign{#\cr$\smash{-}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\mathord{\rightharpoonup}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{X}\hfil$\crcr}}]. In analogy to the case of \epsilon -machines, the channel excess entropy captures the minimal amount of information that must be stored by a model of an input-output process in order to correctly reproduce it, given input. We now show that the channel excess entropy lower bounds the classical channel statistical complexity. Proposition 3 . The channel statistical complexity C^{\mathcal{A}}_{\mathcal{I}} of a channel \mathcal{A} given an input \mathcal{I} is lower bounded by the channel’s excess entropy \mathbf{E}^{\mathcal{A}}_{\mathcal{I}} , \mathbf{E}^{\mathcal{A}}_{\mathcal{I}}\leq C^{\mathcal{A}}_{\mathcal{I}} . The proof leverages a conditional version of the data-processing inequality Cover and Thomas 2005 , with full details given in Appendix C . Next, we show that the quantum complexity is also lower bounded by the channel excess entropy (see proof in Appendix D : \mathbf{E}^{\mathcal{A}}_{\mathcal{I}_{1}} Q^{\mathcal{A}}_{\mathcal{I}_{1}} C^{\mathcal{A}}_{\mathcal{I}_{1}} \mathbf{E}^{\mathcal{B}}_{\mathcal{I}_{2}} Q^{\mathcal{B}}_{\mathcal{I}_{2}} C^{\mathcal{B}}_{\mathcal{I}_{2}} Figure 7: A visualization of the sufficient condition for ambiguous ordering of the complexities. In black we show the excess entropy and complexities of \mathcal{A} , while with blue those of \mathcal{B} . Proposition 4 . The quantum complexity Q^{\mathcal{A}}_{\mathcal{I}} of a quantum model is lower bounded by the channel excess entropy \mathbf{E}^{\mathcal{A}}_{\mathcal{I}} , \mathbf{E}^{\mathcal{A}}_{\mathcal{I}}\leq Q^{\mathcal{A}}_{\mathcal{I}} . We remark that, in general, a channel can be such that allows influences to the present from the future, meaning that one can consider input-output processes such that future inputs can, in principle, influence the present behaviour. Although mathematically possible, this does not correspond to expected physical behaviour where causality is a standard assumption Barnett and Crutchfield 2015 . As a result, in this work, we only consider causal or anticipation-free channels. Definition 9 . A causal channel or anticipation-free channel satisfies \displaystyle\Pr(Y_{t:t+L}|\vbox{\halign{#\cr$\smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\mathord{\rightharpoonup}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{X}\hfil$\crcr}})=\Pr(Y_{t:t+L}|\vbox{\halign{#\cr$\smash{\leftharpoonup}\mkern-7.0mu\leaders{\hbox{$\mkern-2.0mu\smash{-}\mkern-2.0mu$}}{\hfill}\mkern-7.0mu\smash{-}$\crcr\kern-1.2pt\cr$\hfil\displaystyle{X}\hfil$\crcr}}_{t+L})\,. That is, the channel is completely characterised by its behaviour on semi-infinite pasts. The meaning of the last definition is clear: the conditional probabilities of future output sequences of any length depend only on the past and present inputs, but not on inputs from the future. For causal channels, we have the following useful decomposition for the excess entropy: Proposition 5 . Given a causal input-output process, its excess entropy \mathbf{E}^{\mathcal{A}}_{\mathcal{I}} decomposes in terms of the excess entropies of the joint and input processes, \mathbf{E}^{\mathcal{J}} and \mathbf{E}^{\mathcal{I}} respectively, as \displaystyle\mathbf{E}^{\mathcal{A}}_{\mathcal{I}}=\mathbf{E}^{\mathcal{J}}-\mathbf{E}^{\mathcal{I}}. (70) The proof is given in Appendix E and follows by using the definition of the excess entropies involved and applying known mutual information identities. We find that the excess entropy decomposes in alignment with the intuition that the minimum memory the agent needs to store equals the minimum memory needed for the process over joint inputs and outputs, in excess of what is provided by the input. Proposition 5 shows that the channel excess entropy is directly related to the excess entropies of two different stochastic processes, the input process and the stochastic process of over joint inputs and outputs, allowing us to evaluate it with existing methods for \epsilon -machines Ellison et al. 2009 ; Crutchfield et al. 2009 . We can summarise the last three propositions in the following result: Result 2 . The excess entropy of a causal channel \mathbf{E}^{\mathcal{A}}_{\mathcal{I}} provides a lower bound on both the classical and quantum complexities of the channel given an input, denoted by C_{\mathcal{I}}^{\mathcal{A}} and Q_{\mathcal{I}}^{\mathcal{A}} . That is, we have \displaystyle\mathbf{E}^{\mathcal{A}}_{\mathcal{I}}=\mathbf{E}^{\mathcal{J}}-\mathbf{E}^{\mathcal{I}}\leq Q^{\mathcal{A}}_{\mathcal{I}}\leq C^{\mathcal{A}}_{\mathcal{I}}\,. (71) We can use the last inequality to derive sufficient conditions for ambiguity to occur or not. We denote with C_{\mathcal{I}_{\mathcal{A}}}^{\mathcal{A}} and \mathbf{E}_{\mathcal{I}_{\mathcal{A}}}^{\mathcal{A}} the classical complexity and excess entropy of \mathcal{A} when driven by \mathcal{I}_{\mathcal{A}} , and similarly with C_{\mathcal{I}_{\mathcal{B}}}^{\mathcal{B}} and \mathbf{E}_{\mathcal{I}_{\mathcal{B}}}^{\mathcal{B}} for input-output process \mathcal{B} when driven by \mathcal{I}_{\mathcal{B}} . Moreover, assume without loss of generality that C_{\mathcal{I}_{\mathcal{A}}}^{\mathcal{A}}>C_{\mathcal{I}_{\mathcal{B}}}^{\mathcal{B}} . We have the following result: Result 3 . Let \mathcal{A} and \mathcal{B} denote two input-output processes driven by inputs from two stochastic processes \mathcal{I}_{\mathcal{A}} and \mathcal{I}_{\mathcal{B}} , respectively. Let their excess entropies be denoted by \mathbf{E}^{\mathcal{A}}_{\mathcal{I}_{\mathcal{A}}},\mathbf{E}^{\mathcal{B}}_{\mathcal{I}_{\mathcal{B}}} , and their quantum complexities by Q^{\mathcal{A}}_{\mathcal{I}_{\mathcal{A}}},Q^{\mathcal{B}}_{\mathcal{I}_{\mathcal{B}}} . Moreover, without loss of generality, assume that C^{\mathcal{A}}_{\mathcal{I}_{\mathcal{A}}}>C^{\mathcal{B}}_{\mathcal{I}_{\mathcal{B}}} . Then, if the inequality \displaystyle\mathbf{E}^{\mathcal{B}}_{\mathcal{I}_{\mathcal{B}}}>Q^{\mathcal{A}}_{\mathcal{I}_{\mathcal{A}}}\,, (72) is satisfied, we have an ambiguous ordering between classical and quantum complexities. That is, we simultaneously have \displaystyle C^{\mathcal{A}}_{\mathcal{I}_{\mathcal{A}}}>C^{\mathcal{B}}_{\mathcal{I}_{\mathcal{B}}}\ \ \text{and}\ \ Q^{\mathcal{A}}_{\mathcal{I}_{\mathcal{A}}}C^{\mathcal{B}}_{\mathcal{I}_{\mathcal{B}}} . Then, if the inequality \displaystyle\mathbf{E}^{\mathcal{A}}_{\mathcal{I}_{\mathcal{A}}}>Q^{\mathcal{B}}_{\mathcal{I}_{\mathcal{B}}} (74) is satisfied, we have a consistent ordering between classical and quantum complexities. That is, we have \displaystyle C^{\mathcal{A}}_{\mathcal{I}_{\mathcal{A}}}>C^{\mathcal{B}}_{\mathcal{I}_{\mathcal{B}}}\ \ \text{and}\ \ Q^{\mathcal{A}}_{\mathcal{I}_{\mathcal{A}}}>Q^{\mathcal{B}}_{\mathcal{I}_{\mathcal{B}}}\,. (75) The last condition is also only sufficient. The usefulness of both conditions, Eqs. ( 72 ) and ( 74 ), lies in the following fact. Given that it is, in general, a hard problem to obtain the optimal quantum model for a given input-output process, these sufficient conditions can be used to detect the presence or absence of an ambiguous ordering between the classical and quantum complexities, whenever only one of the optimal quantum models for a pair of input-output processes is known. In fact, given that the statistical complexity of the optimal model lower bounds the complexity of any quantum model, Results 3 and 4 hold for the quantum complexities of any quantum model on the RHS of Eqs. ( 72 ) and ( 74 ), not necessarily an optimal one. In the next section we demonstrate the results by considering specific scenarios and explicit examples involving classical and quantum agents that can exhibit classical-quantum ambiguity of complexity. IV Illustrative Scenarios We now demonstrate the results of the last section with different scenarios and particular examples. Let \mathcal{I}_{\mathcal{A}},\mathcal{I}_{\mathcal{B}} be stochastic processes that are taken as inputs of the input-output stochastic processes \mathcal{A} and \mathcal{B} , respectively. We will show the inconsistency between classical and quantum complexities in three scenarios, which can be seen as special cases of the general setting shown in Fig. 6 . The first consists of two different strategies that are executed by agents reacting to the same environmental stimulus. This corresponds to taking the two inputs \mathcal{I}_{\mathcal{A}} and \mathcal{I}_{B} in the general setting shown in Fig. 6 to be the same, i.e., \mathcal{I}_{\mathcal{A}}=\mathcal{I}_{\mathcal{B}}=\mathcal{I} . The second consists of an agent that implements a single strategy when reacting to two different inputs, and corresponds to identifying \mathcal{A}=\mathcal{B} . The last scenario is that of an agent implementing a certain strategy and an agent implementing their operational inverse actions. This case corresponds to letting \mathcal{I}_{\mathcal{A}}=\mathcal{O}_{B} and \mathcal{I}_{\mathcal{B}}=\mathcal{O}_{A} . This is because for the agent that is implementing the operational inverse of the first, the role of inputs and outputs is reversed. IV.1 Two agents reacting to the same stimulus The first scenario we consider consists of two agents implementing two strategies \mathcal{A} and \mathcal{B} , driven by the same stimulus \mathcal{I} and outputting actions \mathcal{O}_{\mathcal{A}} and \mathcal{O}_{\mathcal{B}} , respectively. In its general form, this scenario is depicted in Fig. 8 . We will show the following. \mathcal{I} \mathcal{A} \mathcal{B} \mathcal{O}_{\mathcal{A}} \mathcal{O}_{\mathcal{B}} Figure 8: Two agents executing strategies \mathcal{A} and \mathcal{B} while reacting to the same stimulus. Result 5 . There exist pairs of input-output processes \mathcal{A} and \mathcal{B} and an input process \mathcal{I} such that that the difference of their classical complexities C_{\mathcal{I}}^{\mathcal{A}} and C_{\mathcal{I}}^{\mathcal{B}} when driven by input \mathcal{I} is positive, C_{\mathcal{I}}^{\mathcal{A}}-C_{\mathcal{I}}^{\mathcal{B}}>0 , while the difference of their quantum complexities Q_{\mathcal{I}}^{\mathcal{A}} and Q_{\mathcal{I}}^{\mathcal{B}} is negative, Q_{\mathcal{I}}^{\mathcal{A}}-Q_{\mathcal{I}}^{\mathcal{B}}<0 . As a concrete example, let us consider that the two agents, Alice and Bob, wish to simulate the behaviour of two particle detectors. Here we consider input and output alphabets consisting of the same two symbols \mathcal{X},\mathcal{Y}=\{0,1\} . Symbol 0 (1) should be interpreted to mean that the particle was not (was) present. 1 (a) 0:r 1:1-r 1 (b) 2 0|1:1 1|0:1 0|0:1 1|1:1 1 (c) 2 1|1:1-\alpha 0|0:1 0|1:1 0|0:1 \,\,\,\,0|1:\alpha Figure 9: (a) The Biased Coin process. (b) Alice is implementing a noiseless detector with delay. (c) Bob is implementing a noisy detector with dead time. Alice is simulating a noiseless detector \mathcal{A} with one time step delay : the detector stores the information about the presence or absence of the particle at the current time step and announces it as its output at the next time step. In order to successfully implement the behaviour of \mathcal{A} , Alice needs to store 1 bit, her memory needs to have two states, and the corresponding \epsilon -transducer is shown in Fig. 9 . On the other hand, Bob is simulating the behaviour of a noisy detector with dead time Knoll 2010 ; Migdall 2013 : the presence of an input stimulus 1 (presence of the particle) is detected correctly with probability 1-\alpha , followed by a one time step relaxation period, during which the device is reset to its normal state and no detection is possible. More specifically, detector \mathcal{B} correctly identifies the absence of the signal and emits 0. In the presence of a particle, however, it introduces two different types of noise. Specifically, (i) if \mathcal{B} is in its first state, with probability \alpha it will incorrectly detect a 0 (no presence of a particle) and remain in the first state, otherwise correctly output a 1 (detection of particle) and transition to the second state, (ii) while if \mathcal{B} is in its second state, i.e. detected a particle in the previous time step, it completely ignores the input and always outputs a 0 (no particle detection) while resetting back to the first state. In Fig. 9 we depict the \epsilon -transducer that consists of two causal states and two-symbol input and output alphabets. Let us also assume that the original series of input stimuli \mathcal{I} is generated by a simple IID process, the Biased Coin process, which consists of a series of biased coin flips with some bias r , shown in Fig. 9 . That is, a particle is randomly generated (or not) at each time step with some probability 1-r (or r ). For this input, the statistical complexity of the agents can be readily calculated. Alice’s and Bob’s classical complexities are found to be (see Appendix F ) \displaystyle C_{\mathcal{I}}^{\mathcal{A}}=h(r)\qquad C_{\mathcal{I}}^{\mathcal{B}}=h(b), (76) where h(q)=-q\log q-(1-q)\log(1-q) denotes the binary entropy and b=\nicefrac{{1}}{{(1+(1-r)(1-\alpha))}} . Note that the complexity of Bob depends on both the bias r of the input as well as the parameter \alpha . Figure 10: The classical and quantum complexities of the agents. In orange are both the classical and quantum complexity of Alice, C_{\mathcal{I}}^{\mathcal{A}},Q_{\mathcal{I}}^{\mathcal{A}} . In blue is the classical complexity of Bob, C_{\mathcal{I}}^{\mathcal{B}} , while in green is his quantum complexity, Q_{\mathcal{I}}^{\mathcal{B}} . Figure 11: Classical and quantum complexities of the agents for a biased coin input with bias r=\nicefrac{{1}}{{5}} . In black are the classical and quantum complexities of Alice, C_{\mathcal{I}}^{\mathcal{A}},Q_{\mathcal{I}}^{\mathcal{A}} . In blue is the classical complexity, C_{\mathcal{I}}^{\mathcal{B}} , of Bob with varying parameter \alpha while in red is his quantum complexity, Q_{\mathcal{I}}^{\mathcal{B}} . In the region between the dashed lines ambiguity of complexity is exhibited. Figure 12: Classical and quantum complexities of the agents driven by a biased coin input of varying bias r . In black are the classical and quantum complexities of Alice, C_{\mathcal{I}}^{\mathcal{A}},Q_{\mathcal{I}}^{\mathcal{A}} . In blue is the classical complexity, C_{\mathcal{I}}^{\mathcal{B}} , of Bob with fixed parameter \alpha=\nicefrac{{1}}{{2}} while in red is his quantum complexity, Q_{\mathcal{I}}^{\mathcal{B}} . In the region between the dashed lines ambiguity of complexity is exhibited. We now turn to the derivation of the quantum complexities. From the above optimal classical description of the agents we can construct the optimal quantum models Thompson et al. 2017 , Elliott et al. 2022 . First, it is easy to show that an optimal quantum model of Alice will have the same complexity as the classical one. This follows from the fact that the fidelity between the conditional futures of the two causal states is equal to zero, forcing any quantum model to have orthogonal causal states as well (see Appendix F ). However, this will not be the case in general for Bob. In both cases, to prove the optimality of the quantum model we show that it saturates a maximum fidelity constraint Elliott et al. 2022 . Optimality then follows from the fact that for two states, the von Neumann entropy is a decreasing function of the overlap between the states. Concretely, for Alice, the fidelity constraint is equal to 0 which means that the quantum states have to be orthogonal. Thus, a quantum model cannot lead to a memory reduction over the classical model and Q_{\mathcal{I}}^{\mathcal{A}}=C_{\mathcal{I}}^{\mathcal{A}} . This is true whenever the channel excess entropy equals the classical complexity for a certain input, and it can be shown that this always holds for processes with deterministic transitions between states. In particular, as any delay channel of n time steps is deterministic, its classical and quantum complexities coincide for any input. For Bob we find that the maximum fidelity constraint gives the value F_{12}=\sqrt{\alpha} (see Appendix F ). At the same time, the quantum causal states from Eqs. ( 55 )-( 56 ), can be encoded in a single qubit as: \displaystyle|\sigma_{1}\rangle=\sqrt{\alpha}|0\rangle+\sqrt{1-\alpha}|1\rangle \displaystyle|\sigma_{2}\rangle=|0\rangle\,. (77) It is straightforward to verify that they obey \langle\sigma_{1}|\sigma_{2}\rangle=\sqrt{\alpha} , thus saturating the fidelity constraint and minimising the von Neumann entropy: the quantum encoding of the quantum model is optimal. Having obtained an optimal classical to quantum state encoding, we can now derive the quantum complexity. In the case of Bob, the quantum complexity differs from the classical one and is explicitly found to be \displaystyle Q_{\mathcal{I}}^{\mathcal{B}}=h\left(\frac{c-\sqrt{c+d}}{2c}\right)\,, (78) where c=2+r-\alpha r and d=-4r(2-4\alpha+2\alpha^{2}) . Note that for Bob the classical and quantum complexities depend on both the bias of the coin r , as well as the parameter \alpha . We can now show that there are regions of the parameters where an inconsistency in the ordering of the complexities occurs. This ambiguous ordering of the classical and quantum complexities of Alice and Bob is shown in Fig. 10 . In orange, we have plotted the coinciding classical and quantum complexities of Alice, while with blue and green the classical and quantum complexities of Bob, respectively. It is clear that there are values of the bias of the input r and the parameter \alpha of Bob, for which an inconsistent ordering occurs. The region of ambiguity of complexity is shown in purple in Fig. 10 . In Figs. 12 and 12 , we further demonstrate two specific cases where ambiguity arises. Specifically, in Fig. 12 we fix the value of the bias of the input to r=\nicefrac{{1}}{{5}} and observe that any detector \mathcal{B} with noise parameter values \alpha between 0.3 and 0.68 exhibit ambiguity in the ordering of the complexities. Similarly, in Fig. 12 we consider a specific detector with noise parameter \alpha=\nicefrac{{1}}{{2}} and vary the probability r that controls whether a particle is generated or not as an input. We see that conflicting ordering between classical and quantum complexities occurs for value of the bias r between ~0.12 and 0.26 . Figure 13: The regions of ambiguity and consistency as detected through the conditions of Results 3 and 4 . Regions of ambiguity and consistency, \mathcal{R}_{1} and \mathcal{R}_{2} , are shown in blue and orange, when the quantum complexity of \mathcal{B} , Q_{\mathcal{I}}^{\mathcal{B}} is known. Region of consistency \mathcal{R}_{4} is shown in red, when the quantum complexity of \mathcal{A} , Q_{\mathcal{I}}^{\mathcal{A}} , is known instead. We note that the regions of ambiguity and consistency could have been predicted without having to derive both of the quantum complexities, directly by applying Results 3 and 4 . For instance, consider the case where we could only derive the optimal quantum complexity of \mathcal{B} but not of \mathcal{A} . As the excess entropy of the input is zero, i.e. \mathbf{E}^{\mathcal{I}}=0 , we have from Proposition 5 that \mathbf{E}^{\mathcal{A}}_{\mathcal{I}}=\mathbf{E}^{\mathcal{J}}-\mathbf{E}^{\mathcal{I}}=\mathbf{E}^{\mathcal{J}} . As the input-output process \mathcal{A} is deterministic, the excess entropy equals the classical (and quantum) complexity for any input. That is, \mathbf{E}^{A}_{\mathcal{I}}=C^{A}_{\mathcal{I}}=Q^{A}_{\mathcal{I}}=h(r) . Using Result 3 , we define the region of ambiguity, \mathcal{R}_{1} , the region in the parameter space (\alpha,r) \displaystyle\mathcal{R}_{1}:\{C_{\mathcal{I}}^{\mathcal{B}}>C_{\mathcal{I}}^{\mathcal{A}}\text{ and }\mathbf{E}^{\mathcal{A}}_{\mathcal{I}}\geq Q_{\mathcal{I}}^{\mathcal{B}}\}\,. (79) Similarly, from Result 4 we can define the region of consistency of the complexities, \mathcal{R}_{2} , as \displaystyle\mathcal{R}_{2}:\{C_{\mathcal{I}}^{\mathcal{A}}>C_{\mathcal{I}}^{\mathcal{B}}\text{ and }\mathbf{E}^{\mathcal{A}}_{\mathcal{I}}\geq Q_{\mathcal{I}}^{\mathcal{B}}\}\,. (80) The two regions \mathcal{R}_{1} and \mathcal{R}_{2} are shown in blue and orange, respectively, in Fig. 13 . Were we able to evaluate the quantum complexity of \mathcal{A} but not that of \mathcal{B} , Results 3 and 4 would imply instead two regions \mathcal{R}_{3} and \mathcal{R}_{4} of ambiguity and consistency, respectively, defined as \displaystyle\mathcal{R}_{3}:\{C_{\mathcal{I}}^{\mathcal{A}}>C_{\mathcal{I}}^{\mathcal{B}}\text{ and }\mathbf{E}^{\mathcal{B}}_{\mathcal{I}}\geq Q_{\mathcal{I}}^{\mathcal{A}}\} (81) and \displaystyle\mathcal{R}_{4}:\{C_{\mathcal{I}}^{\mathcal{B}}>C_{\mathcal{I}}^{\mathcal{A}}\text{ and }\mathbf{E}^{\mathcal{B}}_{\mathcal{I}}\geq Q_{\mathcal{I}}^{\mathcal{A}}\}\,. (82) The excess entropies are given in Appendix J . The region \mathcal{R}_{4} is shown in red in Fig. 13 , while the conditions of \mathcal{R}_{3} are not satisfied for any values of \alpha an r . The blue, orange and red regions in Fig. 13 cover the largest area in the parameter space, demonstrating that the sufficient conditions of our Results 3 and 4 are able to successfully detect most of the paramater space. In the white region of Fig. 13 , Results 3 and 4 are agnostic about the ordering of the complexities. Having demonstrated this ambiguous ordering in the complexities, it is natural to ask how common this phenomenon is. We have the following result, which shows that this phenomenon is not isolated. Result 6 . Given an input stochastic process \mathcal{I} and an input-output process \mathcal{A} with non-equal optimal classical and quantum complexities when driven by \mathcal{I} , i.e. Q^{\mathcal{A}}_{\mathcal{I}}0 , while the difference of quantum complexities is negative, Q_{\mathcal{I}_{1}}^{\mathcal{A}}-Q_{\mathcal{I}_{2}}^{\mathcal{A}}<0 . To derive the optimal quantum model, we first evaluate the maximum fidelity constraint for each pair of causal states, that is, the maximum allowed value of the overlap that the quantum states of a quantum model can attain while faithfully reproducing the behaviour of the classical model. Specifically, we find the values (see Appendix G ) \displaystyle F_{fu} \displaystyle=F_{eu}=0 \displaystyle F_{fe} \displaystyle=\min\left\{\sqrt{\frac{4}{7}},\frac{\sqrt{99(1-q_{1})}}{10}\right\}. (83) From the first two it follows that one of the states must be orthogonal to the other two in the quantum model as well. In other words, the quantum causal states |\sigma_{i}\rangle=\{|f\rangle,|e\rangle,|u\rangle\} must obey \langle f|u\rangle=\langle e|u\rangle=0 , while \langle f|e\rangle=c with \lvert c\rvert\in[0,F_{f}e] . That is, we need to construct a triple of states obeying the above constraints with a value of c that minimises the entropy. Assume that the quantum agent is driven by an input that leads to a stationary distribution over the causal states of the \epsilon -transducer with probabilities \pi=\{\pi_{f},\pi_{e},\pi_{u}\} . Then, the quantum complexity can be calculated through the eigenvalues of the Gram matrix, which shares non-zero eigenvalues with the state \rho=\sum_{x\in\{f,e,u\}}\pi_{x}|x\rangle\!\langle x| Jozsa and Schlienz 2000 . The Gram matrix in this case is \displaystyle G=\begin{pmatrix}\pi_{f}&\sqrt{\pi_{f}\pi_{e}}c&0\\ \sqrt{\pi_{f}\pi_{e}}c^{*}&\pi_{e}&0\\ 0&0&\pi_{u}\end{pmatrix}\,, (84) and with \pi_{u}=1-\pi_{f}+\pi_{e} its eigenvalues are found to be \displaystyle e_{i}=\{ \displaystyle 1-\pi_{f}-\pi_{e}\,, \displaystyle\frac{1}{2}\left(\pi_{f}+\pi_{e}\pm\sqrt{(\pi_{1}-\pi_{e})^{2}+4\lvert c\rvert^{2}\pi_{f}\pi_{e}}\right)\}\,. (85) As the von Neumann entropy has a strictly negative derivative with respect to \lvert c\rvert , it is a decreasing function of \lvert c\rvert . Thus the quantum complexity is minimised for the maximum allowed overlap, \lvert c\rvert=F_{fe} . Next, one needs to construct a set of quantum states that achieve these overlaps. It is straightforward to check that such a triple is \displaystyle|f\rangle \displaystyle=|1\rangle, \displaystyle|e\rangle \displaystyle=F_{fe}|1\rangle+\sqrt{1-F_{fe}^{2}}|2\rangle \displaystyle|u\rangle \displaystyle=|3\rangle, (86) where \{|j\rangle\}_{j=1,\ldots,3} denotes an orthonormal basis. Figure 16: The difference of classical and quantum complexities of the adaptive strategies of two agents reacting to different stimuli as a function of the free parameter q_{1} . In blue we plot the difference of the classical complexities, C_{\mathcal{I}_{1}}^{\mathcal{A}}-C_{\mathcal{I}_{2}}^{\mathcal{A}} , while in red we show the difference of quantum complexities in the two cases, Q_{\mathcal{I}_{1}}^{\mathcal{A}}-Q_{\mathcal{I}_{2}}^{\mathcal{A}} . The vertical dashed lines represent the points that the graphs intersect with the horizontal line at zero, thus changing sign. In Fig. 16 we plot the difference of the classical and quantum complexities as a function of the parameter q_{1} of the input-output process. We find that there is a class of such processes, i.e., a region of values of q_{1} , with inconsistent ordering. Specifically, if the free parameter q_{1} in the input-output process takes value in 0.22\leq q_{1}\leq 0.54 , the two graphs have opposite signs, and as a result inconsistent ordering of the classical and quantum complexities occurs. Result 7 . There exists an input-output process \mathcal{A} and two input processes \mathcal{I}_{1} and \mathcal{I}_{2} such that the difference of the classical complexities of \mathcal{A} when driven by \mathcal{I}_{1} , C_{\mathcal{I}_{1}}^{\mathcal{A}} , and when driven by \mathcal{I}_{2} , C_{\mathcal{I}_{2}}^{\mathcal{A}} , is positive, C_{\mathcal{I}_{1}}^{\mathcal{A}}-C_{\mathcal{I}_{2}}^{\mathcal{A}}>0 , while the difference of the respective quantum complexities Q_{\mathcal{I}_{1}}^{\mathcal{A}} and Q_{\mathcal{I}_{2}}^{\mathcal{A}} is negative, Q_{\mathcal{I}_{1}}^{\mathcal{A}}-Q_{\mathcal{I}_{2}}^{\mathcal{A}}<0 . It is natural to ask whether given an input-output process that can exhibit different classical and quantum complexities for some input, there are always input processes that can lead to an inconsistent ordering of the complexities. We only have the following partial answer. Observation 1 . There exist input-output processes that can have non-equal classical and quantum complexities, which however cannot lead to ambiguity in the ordering of the complexities for any pair of IID input processes. We demonstrate this observation with a specific example in Appendix I . IV.3 An Agent and Their Operational Inverse Given an agent that reacts to inputs from an input process \mathcal{I} and executing an input-output process \mathcal{A} , their output actions also define a stochastic process \mathcal{O} . Thus, in effect the input-output process \mathcal{A} that the agent is implementing maps the input process \mathcal{I} to an output process \mathcal{O} . Often, an agent that implements an inverse transformation which maps \mathcal{O} back to \mathcal{I} is useful. Here we consider such an agent that implements an inverse input-output process, more formally defined as follows: Definition 10 . An inverse of an input-output process \mathcal{A} for a given input \mathcal{I} which is mapped to an output process \mathcal{O} though \mathcal{A} , is an input-output process \mathcal{A}^{-1} such that when driven by the stochastic process \mathcal{O} it maps to the original stochastic process \mathcal{I} . Although an input process \mathcal{I} and an input-output \mathcal{A} , do not uniquely specify an inverse process in general, there is a way to infer such inverse channels. This can be done by considering the implied stochastic process over the joint inputs and outputs. From the joint and output stochastic processes one can infer an input-output process that implements the inverse map that takes outputs to inputs by appropriately conditionalising the joint process over outputs. Note that, in general, one cannot infer a unique channel this way, and thus a class of different input-output processes will be obtained. Moreover, in some cases the map from outputs back to inputs could be completely trivial, in the sense that it will be equivalent to ignoring all inputs and just outputting the target output process. Regardless, in this case, too, we show that ambiguous ordering of the complexities between the maps can exist. We remark that here we will show that this ambiguity can exist between an agent implementing an input-output process for a given input stimulus and an agent implementing the inverse actions, but a closely related scenario was considered in Ref. Kechrimparis et al. 2023 . There, given a pair of stochastic processes, it was shown that this phenomenon persists for the memory minimal channels between the processes, which demonstrated an inconsistent causal asymmetry . Thus, in the scenario considered here we start with an input stochastic process and an input-output process as given, while in Ref. Kechrimparis et al. 2023 the starting point was a pair of stochastic processes. In Ref. Kechrimparis et al. 2023 minimisation of the classical and quantum complexities over all possible forward and inverse input-output processes was considered, while here we have an asymmetric scenario as one of the input-output processes is fixed and, in addition, minimisation over all inverse input-output processes is not demanded. Consider an input process \mathcal{I} as well as an input-output process \mathcal{A} . If M^{(x)} denote the transition matrices of \mathcal{I} and T^{(y|x)} are the transition matrices describing the input-output process \mathcal{A} , then we can derive the transition matrices of the process over joint inputs and outputs, \mathcal{J} , through \displaystyle J^{(x,y)}=T^{(y|x)}\otimes M^{(x)}\,. (87) By marginalising over inputs, we can obtain a presentation of the outputs of the input-output process, \mathcal{O} , \displaystyle N^{(y)}=\sum_{x}T^{(y|x)}\otimes A^{(x)}\,, (88) where N^{(y)} denote the transition matrices of \mathcal{O} . Note that in both cases some states may be transients, i.e. they have zero long-term probability of occurrence, and thus can be removed. Moreover, the resulting presentation may not be minimal, so one would also need to check for equivalence of the states James et al. 2014 . r_{0} r_{1} 1:\nicefrac{{1}}{{2}} 2:\nicefrac{{1}}{{2}} 0:\nicefrac{{1}}{{2}} 1:\nicefrac{{1}}{{2}} Figure 17: The input stimulus described by the process \mathcal{I} . \sigma_{0} \sigma_{1} \sigma_{2} 0|0:1 2|1:1-p 2|2:1 1|1:p 0|0:1 1|1:r 2|1:1-q 2|2:1 0|0:1 2|1:1-r 2|2:1 1|1:q Figure 18: The \epsilon -transducer of an input-output process \mathcal{A} with three states. s_{0} s_{1} s_{2} (0,0):\frac{1}{2} (1,2):\frac{1-p}{2} (2,2):\frac{1}{2} (1,1):\frac{p}{2} (0,0):\frac{1}{2} (1,1):\frac{r}{2} (1,2):\frac{1-q}{2} (1,2):\frac{1-r}{2} (1,1):\frac{q}{2} Figure 19: The \epsilon -machine of the joint process \mathcal{J} over inputs and outputs. \chi_{0} \chi_{1} \chi_{2} 0:\frac{1}{2} 2:1-\frac{p}{2} 1:\frac{p}{2} 0:\frac{1}{2} 1:\frac{r}{2} 2:\frac{1-q}{2} 2:\frac{1-r}{2} 1:\frac{q}{2} Figure 20: The \epsilon -machine \mathcal{O} of the process describing the outputs of the input-output process \mathcal{A} when driven by \mathcal{I} . Given the output \mathcal{O} , we can conditionalise \mathcal{J} to get a presentation of the inverse input-output process that upon receiving inputs from \mathcal{O} , it outputs \mathcal{I} . This can be achieved by looking at the transitions between states of \mathcal{J} and using the probabilities from the corresponding transitions from \mathcal{O} to obtain the conditional probabilities of the postulated inverse input-output process, \mathcal{A}^{-1} . Specifically, we have the following inversion algorithm. Algorithm 1 . Given an input-output process \mathcal{A} driven by some input process \mathcal{I} , and producing outputs that define an output process \mathcal{O} , inverse input-output processes \mathcal{A}^{-1} that map \mathcal{O} back to \mathcal{I} can be derived with the following steps 1. For a pair of states s_{i} and s_{j} of \mathcal{J} , identify the corresponding states \chi_{k},\chi_{l} in the output process, \mathcal{O} . 2. Define the postulated inverse input-output states with labels (s_{i},\chi_{k}) and (s_{j},\chi_{l}) . 3. For each transition between states s_{i},s_{j} of \mathcal{J} , divide the probability in all emissions (x,y) with the corresponding probability of emission y between \chi_{k} and \chi_{l} of \mathcal{O} and obtain the probabilities of conditional emissions x|y between (s_{i},\chi_{k}) and (s_{j},\chi_{l}) of \mathcal{A}^{-1} . 4. Repeat until all pairs of states of \mathcal{J} have been considered. Note that this algorithm will give an input-output process that maps \mathcal{O} to \mathcal{I} but there may be undefined transitions, which can are essentially free parameters. This reflects the fact that there is no unique channel between two stochastic processes. In addition, it is possible that some of the states of the inverse input-output process are equivalent. Thus, to obtain a minimal presentation, that is, the \epsilon -transducer of an inverse input-output process, the states have to be checked for equivalence James et al. 2014 . We have thus shown that Result 8 . Given an input-output process \mathcal{A} which maps an input stochastic process \mathcal{I} to a stochastic process \mathcal{O} , a family of inverse input-output processes \mathcal{A}^{-1} that map \mathcal{O} back to \mathcal{I} can be found through Algorithm 1. We demonstrate this result with an explicit example. Consider the input stimulus \mathcal{I} whose \epsilon -machine is shown in Fig. 20 and the input-output process \mathcal{A} shown in Fig. 20 . Note that the input is Markovian since each emitted symbol identifies a unique state of the \epsilon -machine. Similarly, the input-output process is Markovian on output symbols. The joint and output process can be found through Eqs. ( 87 ) and ( 88 ). To derive their \epsilon -machines, states need to be checked for equivalence James et al. 2014 . In the particular case that we are examining, all the resulting states are inequivalent. The \epsilon -machines of the resulting processes \mathcal{J} and \mathcal{O} are shown in Figs. 20 and 20 . We now apply Algorithm 1 to find an inverse input-output process of \mathcal{A} . We first note that in the example we are considering, careful inspection reveals that a state s_{i} of \mathcal{J} corresponds to a state \chi_{i} of \mathcal{O} . First, we consider the transition from state s_{0} to s_{2} of \mathcal{J} , which implies the two conditional transitions of 1|2:\frac{1-p}{2-p} and 2|2:\frac{1}{2-p} . Repeating for all states, we find • s_{0} to s_{2} : 1|2:\frac{1-p}{2-p} and 2|2:\frac{1}{2-p} and s_{0} to s_{1} : 1|1:1 • s_{1} to s_{1} : 1|1:1 , s_{1} to s_{2} : 1|2:1 and s_{1} to s_{0} : 0|0:1 . • s_{2} to s_{2} : 1|2:1 , s_{2} to s_{1} : 1|1:1 and s_{2} to s_{0} : 0|0:1 . Noting that the \epsilon -transducer of the inverse agent is Markovian and checking for equivalence, we find that the states (s_{1},\chi_{1}) and (s_{2},\chi_{2}) are in fact equivalent and can be merged. To check for equivalence we need to check that for all inputs, all outputs words of length one are statistically indistinguishable James et al. 2014 ; Travers and Crutchfield 2011 . Finally, note that from state s_{0} there is no implied transition over 0 as input. This means that whichever way we add this transition, it will not affect the output. We choose to add a self transition of s_{0} as 0|0:1 . The resulting \epsilon -transducer is shown in Fig. 21 . \phi_{1} \phi_{0} 0|0:1 1|1:1 1|2:\frac{1-p}{2-p} 2|2:\frac{1}{2-p} 1|1:1 1|2:1 0|0:1 Figure 21: The \epsilon -transducer of the implied inverse input-output process \mathcal{A}^{-1} that maps \mathcal{O} back to \mathcal{I} , with \phi_{0}=(s_{0},\chi_{0}) and \phi_{1}=(s_{1},\chi_{1}) . When it comes to the ordering of classical and quantum complexities, we have the following result: Result 9 . There exist an input stochastic process \mathcal{I} and an input-output process \mathcal{A} that maps \mathcal{I} to some output stochastic process \mathcal{O} , and inverse maps \mathcal{A}^{-1} of \mathcal{A} in the sense of Definition 10 , such that that the difference of the classical complexities of \mathcal{A} when driven by \mathcal{I} , C_{\mathcal{I}}^{\mathcal{A}} , and of its inverse \mathcal{A}^{-1} when driven by \mathcal{O} , C_{\mathcal{O}}^{\mathcal{A}^{-1}} , is positive, C_{\mathcal{I}}^{\mathcal{A}}-C_{\mathcal{O}}^{\mathcal{A}^{-1}}>0 , while the difference of the respective quantum complexities Q_{\mathcal{I}}^{\mathcal{A}} and Q_{\mathcal{O}}^{\mathcal{A}^{-1}} is negative, Q_{\mathcal{I}}^{\mathcal{A}}-Q_{\mathcal{O}}^{\mathcal{A}^{-1}}<0 . To demonstrate the ambiguous ordering between the complexities, we take the following values of the free parameters of input-output process \mathcal{A} : p=0,\,q=\nicefrac{{1}}{{3}},\,r=\nicefrac{{1}}{{4}} . A direct evaluation of the stationary distributions of \mathcal{A} and \mathcal{A}^{-1} leads to the classical complexities C_{\mathcal{I}}^{\mathcal{A}}=1.290 and C_{\mathcal{O}}^{\mathcal{A}^{-1}}=0.918 , which implies that C_{\mathcal{I}}^{\mathcal{A}}>C_{\mathcal{O}}^{\mathcal{A}^{-1}} , that is, a classical agent executing \mathcal{A} is more complex than a classical agent implementing its operational inverse, \mathcal{A}^{-1} . On the other hand, encoding the quantum states as in Eqs. ( 55 )-( 56 ) and calculating the quantum complexities, we find the values Q_{\mathcal{I}}^{\mathcal{A}}=0.336 and Q_{\mathcal{O}}^{\mathcal{A}^{-1}}=0.550 . Note that for the case of \mathcal{A}^{-1} , the quantum causal states saturate the maximum fidelity constraint and thus correspond to an optimal encoding. A similar statement about optimality can not be made about the encoding of \mathcal{A} , but since the optimal quantum model will have at most the same complexity as our encoding, it suffices. We conclude that Q_{\mathcal{I}}^{\mathcal{A}}\varphi_{0}>\min(\varphi_{0}^{\prime},\varphi_{1}^{\prime}) and \varphi_{1}^{\prime}>\varphi_{0}^{\prime} , it is easy to show that \displaystyle\varphi_{0}>\varphi_{0}^{\prime}\Longrightarrow r\varphi_{0}^{\prime} , we readily obtain that the classical complexities of the agent when driven by the biased coins with biases r and r^{\prime} are \displaystyle C_{r}\varphi_{0}>\varphi_{0}^{\prime} we have that \lambda_{+}<\lambda_{+}^{\prime} , which implies that \displaystyle Q_{r}\varphi_{0}>\min(\varphi_{0}^{\prime},\varphi_{1}^{\prime}) and \min(\varphi_{0}^{\prime},\varphi_{1}^{\prime})=\varphi_{1}^{\prime} . This follows, however, directly from a symmetry argument. Appendix J Excess entropies for scenario A We derive the excess entopies for scenario A in Section IV.1 . As the excess entropy of the input is zero, i.e. \mathbf{E}_{I}=0 , we have from Proposition 5 that \mathbf{E}^{\mathcal{A}}_{\mathcal{I}}=\mathbf{E}^{\mathcal{J}}-\mathbf{E}^{\mathcal{I}}=\mathbf{E}^{\mathcal{J}} . As the input-output process \mathcal{A} is deterministic, the excess entropy equals the classical (and quantum) complexity for any input. That is, \displaystyle\mathbf{E}^{A}_{\mathcal{I}} \displaystyle=C^{A}_{\mathcal{I}}=Q^{A}_{\mathcal{I}}=h(r) \displaystyle=-\frac{(1-r)\log(1-r)+r\log r}{\log 2}\,. (261) For the excess entropy \mathbf{E}^{\mathcal{B}}_{\mathcal{I}} , we find \displaystyle\mathbf{E}^{\mathcal{B}}_{\mathcal{I}}= \displaystyle\frac{(r-1)}{(\alpha(r-1)-r+2)\log(2)}\cdot\Bigg(\log\left(\frac{1}{2-r+\alpha(r-1)}\right) \displaystyle+(\alpha-1)r\log\left(\frac{(1-\alpha)(1-r)}{2-r+\alpha(r-1)}\right) \displaystyle-\alpha\log\left(\frac{\alpha}{1+r(\alpha-1)}\right) \displaystyle-(\alpha-1)\log\left(\frac{1-r+\alpha(r-1)}{2-r+\alpha(r-1)}\right)\Bigg)\,. (262)