How Quantum Agents Can Change Which Strategies Are More Complex

Hyukjoon Kwon; Mile Gu; Nix Barnett; Spiros Kechrimparis

REVIEW 1 major objections 4 minor 1 cited by

How Quantum Agents Can Change Which Strategies Are More Complex

T0 review · 1 major / 4 minor · reviewed 2026-08-05 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper establishes that adaptive strategies' relative memory complexity can reverse between classical and quantum agents, with channel excess entropy as a universal lower bound that diagnoses when reversal occurs.

desk verdict Good structural idea, but the flagship numerical example has an arithmetic error that invalidates the plotted results. read the letter →

arxiv 2508.08092 v1 pith:M6H6NRCB submitted 2025-08-11 quant-ph

Spiros Kechrimparis , Nix Barnett , Mile Gu , Hyukjoon Kwon This is my paper

classification quant-ph

keywords quantumcomplexitystatisticalinput-outputprocessesadaptiveagentschannelexcessentropymemoryadvantageclassical-quantumambiguityordering

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper tries to establish that "which of two adaptive strategies is more complex" has no substrate-independent answer: an agent storing classical bits can rank strategies one way, while an agent storing quantum information can rank them the opposite way. To make this precise, the authors introduce the channel excess entropy, $E^A_I = E_J - E_I$, the mutual information between a strategy's joint input-output past and its future output given future input, and prove it lower-bounds both the classical statistical complexity and the quantum complexity of any causal strategy. They then derive a sufficient condition for reversal—if $C^A > C^B$ but $E^B > Q^A$, then $Q^A < Q^B$—and exhibit explicit reversals for two agents facing the same input, one agent facing two inputs, and an agent versus its operational inverse. If correct, complexity rankings are not intrinsic; they depend on the physics of the memory doing the computation, and the channel excess entropy is a universal floor on required memory.

What carries the argument

The central object is the channel excess entropy, $E^A_I = I[\text{joint past}; \text{future output} \mid \text{future input}]$, which for causal channels decomposes as $E^A_I = E_J - E_I$. It functions as a universal lower bound on both classical and quantum memory costs, so the interval $[E^A_I, C^A_I]$ is the room in which quantum encodings can act. The optimal quantum encodings are built by minimising the von Neumann entropy of the average memory state subject to a maximum-fidelity constraint on the overlaps between quantum causal states; saturating that constraint is how each example's claimed quantum complexity is certified.

What would settle it

Take Bob's noisy dead-time detector and search over all quantum circuits, not just the fidelity-saturating two-state encoding, for a faithful implementation whose average memory entropy falls below the claimed $Q^B_I = h\!\left(\frac{c-\sqrt{c+d}}{2c}\right)$. Finding one would refute the claimed optimality in that example; proving that every faithful implementation has entropy at least this value would confirm it.

Watch

Extended reading notes

Core claim

The paper's central claim is that the relative memory cost of executing an adaptive strategy is not an intrinsic property of the strategy: it shifts when the agent's memory is quantum. Formally, for any causal input-output process $A$ driven by an input process $I$, the channel excess entropy $E^A_I = E_J - E_I$ satisfies $E^A_I \leq Q^A_I \leq C^A_I$, where $C^A_I$ is the Shannon entropy of the strategy's causal-state distribution and $Q^A_I$ is the von Neumann entropy of the average quantum memory state. Because the two complexities can sit at different heights inside this interval, the order of two strategies can be $C^A_I > C^B_I$ while $Q^A_I < Q^B_I$. The authors prove this can happen

Load-bearing premise

The arguments assume inputs cannot be influenced by future outputs (causality) and that the best quantum agent is one of the specially restricted class of pure-state memory devices considered here; if a quantum device outside that class uses less memory, some example numbers change.

Editorial extensions

If this is right

For any two strategies $A$ and $B$ driven by inputs, if $C^A_I > C^B_I$ and $E^B_I > Q^A_I$, the order flips: $Q^A_I < Q^B_I$.
Strategies with deterministic transitions, such as delay detectors, have equal classical and quantum complexities for every input, making them stable reference points in comparisons.
A single strategy can be judged simpler under one input and more complex under another, depending only on whether the agent uses classical or quantum memory.
Executing a strategy and executing its operational inverse can reverse complexity ranking between classical and quantum agents.
No agent, classical or quantum, can execute a causal strategy with less memory than its channel excess entropy; quantum memory can close but not breach that gap.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The result implies that common complexity comparisons—which behavior is more sophisticated—are ambiguous unless the storage substrate is specified; a complexity label may flip under an upgrade to quantum memory.
The same machinery could be applied to reward-driven agents: the memory needed to attain a given expected reward might exhibit the same classical-quantum reversal, since the paper notes this as an open direction.
The single-agent two-input example suggests that even relabelling or reweighting an input distribution can reverse quantum-classical rankings, so experimental demonstrations could use a fixed physical device and only change the input statistics.
Channel excess entropy is substrate-independent, so it offers a candidate scalar measure for comparisons when classical and quantum rankings conflict.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Quick take: the core idea is good and the structural results are worth a look, but the main quantitative example has an arithmetic error that invalidates the reported numbers.

What is actually new: channel excess entropy E^A_I, the decomposition E^A_I = E_J - E_I for causal channels, and the sufficient conditions in Results 3 and 4. Generalizing the ambiguity-of-simplicity phenomenon from passive stochastic processes to adaptive input-output processes is a natural step, and the paper is honest about inheriting the epsilon-transducer framework and the quantum-agent class from prior work. The lower bound E^A_I ≤ Q^A_I ≤ C^A_I is a useful addition.

The soft spot: Eq. (21) for Q_B in Scenario A is not the entropy of the paper's own quantum state. At α=1, Bob's detector always outputs 0 and stays in state 1, so the process is a constant zero and Q_B must be 0. The formula gives h((2−√2)/4) ≈ 0.61 bits. Recomputing from their |σ1⟩, |σ2⟩ at r=0.2, α=0.5 gives Q_B ≈ 0.516 bits, not the ≈0.700 reported. That makes the plotted curves, the ambiguity ranges, and Result 5 as demonstrated unsupported. The structural inequalities and sufficient conditions do not depend on this formula, but Scenario A is the paper's flagship illustration, so this is a major flaw, not a typo.

Secondary issues: the abstract claims the bound applies to 'any agent', but the proof is for the restricted quantum-agent class of assumptions (i)-(iv) in Sec. II.D. Appendix C's proof of Proposition 3 has a conditional-DPI step that misstates equalities; the intended inequality chain works. Result 6's statement seems to contradict its own range (the text says 'for any value in [Q^A_I, C^A_I]' but the formula says C^A_I − Q^A_I + ε, which would exceed the upper range); Appendix H supports the construction, so this is fixable. Scenarios B and C I did not fully recheck; the reader's independent checks suggest they may hold, but all numerical examples need a careful redo after Scenario A's error.

Verdict: the paper is not desk-reject material. The conceptual claim is important enough and the structural results seem sound. It needs major revision before publication.

Referee Report

1 major / 4 minor

Summary. The paper introduces the channel excess entropy E^A_I for causal input-output processes and proves (Propositions 3–5, Result 2) that it lower-bounds both the classical statistical complexity C^A_I and the quantum complexity Q^A_I (in the quantum-agent class of Elliott et al.) of an agent executing a strategy A under input I. Using the decomposition E^A_I = E_J − E_I and the inequalities E ≤ Q ≤ C, the authors derive sufficient conditions (Results 3 and 4) for classical and quantum agents to rank two strategies in opposite orders. They demonstrate the phenomenon in three analytic scenarios: two detectors driven by a biased coin (Result 5), one investor-type transducer driven by two IID inputs (Result 7), and an agent versus its operational inverse (Result 9). A final section shows that the agent-level ambiguity need not be reflected in the statistics of the output processes alone.

Significance. If the technical results stand, the paper makes a useful conceptual contribution: relative memory-based complexity of strategies is not intrinsic but depends on whether the executing agent stores classical or quantum information, and the channel excess entropy gives a universal lower bound on the required memory. The sufficient conditions in Results 3 and 4 are elegant and practically useful, since they let one detect ambiguity using only excess entropies and one known quantum complexity. The analytic constructions are transparent, and the paper explicitly acknowledges the prior thesis [32] in defining E^A_I. However, the primary quantitative demonstration in Scenario A is undermined by an incorrect closed-form expression for Q_B (Eq. (21)), so the paper as written does not support the stated numerical ranges and plots. The general framework and the other scenarios are not affected by this arithmetic error, but the example needs to be corrected before the claims can be accepted as presented.

major comments (1)

[§IV.A, Eq. (21); Appendix F, Eq. (F8)] The closed-form formula for Bob's quantum complexity is incorrect. At α=1, the detector never outputs 1 and its stationary state is the single state |σ1>=|0>, so both classical and quantum complexities must vanish. Substituting α=1 into Eq. (21) gives c=2, d=0, and Q_B=h((2−√2)/4)≈0.61 bits. Also at α=0 the formula does not reduce to Q_B=C_B=h(b) with b=1/(1+(1−r)(1−α)), as it must for orthogonal states. From the states in Eq. (20) and the stationary weight b, the correct eigenvalues of ρ=b|σ1><σ1|+(1−b)|0><0| are (1±√(1−4b(1−b)(1−α)))/2, so Q_B=h((1−√(1−4b(1−b)(1−α)))/2). This error propagates to Figures 10–13 and the stated ambiguity intervals α∈0.3–0.68 and r∈0.12–0.26. The sufficient-condition framework of Section III is not affected, but the example's quantitative evidence must be recomputed.

minor comments (4)

[Appendix C, Eq. (C9)] In the proof of Proposition 3, the entropy terms should involve the causal-state variable S: the right-hand side should read H[S|⇀X]−H[S|⇀X,⇀Y], and the following line should be H[S|⇀X] ≤ H[S]. As written, the joint past ↼(X,Y) appears where S is intended.
[Result 6] The statement 'C_B⃗q_I = Q_B⃗q_I = C_A^I − Q_A^I + ε, for all ε∈[Q_A^I,C_A^I]' is dimensionally inconsistent: as ε ranges over [Q_A^I,C_A^I], the quantity C_A^I−Q_A^I+ε ranges over [C_A^I, C_A^I+C_A^I−Q_A^I], not [Q_A^I,C_A^I]. It should be formulated as 'for every value v∈[Q_A^I,C_A^I] there is a parameter choice with C=Q=v' (or 'Q_A^I+ε with ε∈[0,C_A^I−Q_A^I]').
[§V, first paragraph] The statement that for the previous section's examples 'the complexities of the output process follow the complexities of the input-output processes for IID inputs' appears incorrect at least for Alice's delay detector: the output process is an IID biased coin with zero statistical complexity, while C_A^I=h(r)>0. Please clarify what is meant by 'follow'.
[Abstract and §II.D] The claims about 'any agent' and 'quantum agents' are stated very broadly. The universal lower bound E^A_I≤Q^A_I is robust, but the specific quantum complexities in the examples are optimized only within the restricted agent class of Ref. [3] (pure memory states in one-to-one correspondence with causal states, preserved input tape, projective measurements). A sentence qualifying this scope would improve precision.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central bounds and examples are derived from stated information-theoretic definitions and external, independently published quantum-agent results.

full rationale

The paper's central claims do not reduce to their inputs by construction. Result 2 (Eq. 14) is assembled from Propositions 3–5, which are proven in Appendices C–E from the definitions of channel excess entropy (Eq. 11), statistical complexity (Eq. 5), and quantum complexity (Eq. 10), using the data processing inequality and Holevo's bound. The decomposition E^A_I = E_J − E_I (Eq. 13) is derived from mutual information identities plus the causal-channel condition (Eq. 12), not imposed as a definition. The examples in Sec. IV are explicit analytic evaluations of transducers, with quantum encodings constructed from Eqs. (6)–(7) and optimality argued by saturating the maximum fidelity constraint of Ref. [3]. That constraint is an external, published, assumption-stated result and is not the target claim of this paper; using it is therefore not circular self-citation. The reliance on Refs. [2,3] for the quantum-agent class and on thesis [32] for the channel excess entropy concept is acknowledged self-citation, but the present paper supplies proofs and does not treat those citations as unverified substitutes for its own derivations. No fitted parameter is renamed as a prediction, and no uniqueness theorem from the authors' prior work is invoked to force a conclusion. The arithmetic concern raised about Eq. (21) is a correctness or verifiability issue, not a circularity, and is therefore outside this pass.

Assumptions & free parameters 5 free parameters · 7 assumptions · 1 invented entities

The central results consume: (a) the computational-mechanics framework (causal states, epsilon-transducers, statistical complexity) as background; (b) the Ref. [3] quantum-agent class and its max-fidelity optimality criterion, from the authors' own prior work (M. Gu is a co-author of [3], and the thesis [32] of co-author Barnett introduced E and E <= C, explicitly acknowledged); and (c) standard information-theoretic inequalities. No parameters are fitted to data; the listed parameters are construction values scanned to exhibit the phenomenon. The main auditable assumption is that the fidelity criterion fully characterizes minimal quantum memory.

free parameters (5)

alpha (Bob's detector noise parameter) = scanned, e.g. alpha in [0.3, 0.68] for r = 1/5
Free parameter of the noisy-detector family in scenario A; ambiguity claimed over a range. Construction parameter scanned to exhibit the phenomenon, not fitted to data.
r (biased-coin input bias) = scanned, e.g. r in [0.12, 0.26] for alpha = 1/2
Bias of the IID input process; ambiguity region in (r, alpha) space. Chosen by hand, not fitted.
q1 (investor strategy free parameter) = ambiguity for q1 in [0.22, 0.54]
Free parameter of the 6-parameter transducer in scenario B; scanned to exhibit opposite signs of the classical and quantum complexity differences.
p, q, r (inverse example parameters) = p = 0, q = 1/3, r = 1/4
Chosen values in scenario C where C^A_I > C^(A^-1)_O but Q^A_I < Q^(A^-1)_O. Construction values, not fitted.
q_i (T_n family transition probabilities) = varied to cover the complexity range (0, log n)
Free parameters of the constructed family in Appendix H used to prove Result 6; chosen to realize arbitrary stationary distributions over causal states.

assumptions (7)

domain assumption The epsilon-transducer and its input-dependent statistical complexity C^A_I are the minimal classical memory characterization of an adaptive strategy (Refs. [1,6-9]).
All complexity claims are measured by Shannon entropy of the causal-state distribution; the whole paper operates inside the computational mechanics framework.
domain assumption The optimal quantum agent for a strategy can be restricted to the class of Ref. [3]: pure memory states in one-to-one correspondence with causal states, preserved input tape, projective measurements (constraints (i)-(iv), Sec. II.D).
Definition 7's quantum complexity Q is the von Neumann entropy of rho = sum_i pi(s_i)|s_i><s_i| (Eq. 9) within this class; the 'minimal memory of any quantum agent' reading of the abstract depends on this restriction.
domain assumption Saturating the maximum-fidelity constraint of Ref. [3] certifies optimality of a quantum model (F12 = sqrt(alpha) for Bob, F_fe for the investor, etc.).
Appendices F, G, I rely on max-fidelity saturation plus monotonicity of von Neumann entropy in overlap to conclude optimality and hence exact Q values.
domain assumption Channels are causal (anticipation-free), Definition 9.
Used in Proposition 5 to kill the term I[future inputs; past outputs | past inputs] and obtain E^A_I = E_J - E_I; if future inputs could influence present outputs the decomposition fails.
domain assumption Processes are stationary and ergodic.
Word probabilities and stationary distributions over causal states are assumed time-invariant; stated in Sec. II.B.
standard math Holevo bound, (conditional) data processing inequality, concavity of von Neumann entropy, unifilarity of epsilon-machines.
Backbone of the proofs of Propositions 1-4 and of the fidelity constraints; accepted background results.
domain assumption For deterministic transitions between states, classical and quantum complexities coincide and equal the excess entropy for any input.
Asserted in Sec. IV A and used to set Alice's Q^A_I = C^A_I = h(r); plausible from orthogonality of perfectly distinguishable states but stated, not derived.

invented entities (1)

Channel excess entropy E^A_I
purpose: Lower bound on the memory of any classical or quantum agent executing an input-output process; used in the sufficient conditions of Results 3 and 4.
A new informational quantity defined as I[(X,Y)_past; Y_future | X_future] from standard mutual information. It is a definitional tool, not a physical entity with an independent falsifiable handle; it is the paper's main conceptual contribution.

how reviews work

0 comments

Cite this review

Pith. "Pith review of How Quantum Agents Can Change Which Strategies Are More Complex." pith.science (2026). https://pith.science/paper/M6H6NRCB

@misc{pith2026250808092,
  author       = {Pith},
  title        = {Pith review of: How Quantum Agents Can Change Which Strategies Are More Complex},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/M6H6NRCB}},
  note         = {Machine review of arXiv:2508.08092}
}

read the original 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 A more complex to execute than Strategy 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.

Figures

Figures reproduced from arXiv: 2508.08092 by the authors.

**Figure 2.** FIG. 2. Visual representation of an agent receiving information from their environment, storing the information to a memory, [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗

**Figure 3.** FIG. 3. The [PITH_FULL_IMAGE:figures/full_fig_p003_3.png] view at source ↗

Figures from the paper (21 more)

**Figure 4.** Figure 4: FIG. 4. A one-step delay channel [PITH_FULL_IMAGE:figures/full_fig_p005_4.png]

**Figure 5.** Figure 5: FIG. 5. Circuit representation of the implementation of a quantum agent (see main text). [PITH_FULL_IMAGE:figures/full_fig_p006_5.png]

**Figure 6.** Figure 6: FIG. 6. The general setting involving two agents implement [PITH_FULL_IMAGE:figures/full_fig_p007_6.png]

**Figure 7.** Figure 7: FIG. 7. A visualization of the sufficient condition for ambiguous ordering of the complexities. In black we show the excess [PITH_FULL_IMAGE:figures/full_fig_p008_7.png]

**Figure 8.** Figure 8: We will show the following. Result 5. There exist pairs of input-output processes A and B and an input process I such that that the difference of their classical complexities C A I and C B I when driven by input I is positive, C A I − C B I > 0, while the difference of…

**Figure 9.** Figure 9: On the other hand, Bob is simulating the behaviour of a noisy detector with dead time [26, 27]: the presence of an input stimulus 1 (presence of the particle) is detected correctly with probability 1 − α, followed by a one time step relaxation period, during which the …

**Figure 9.** Figure 9: FIG. 9. (a) The Biased Coin process. (b) Alice is implementing a noiseless detector with delay. (c) Bob is implementing a [PITH_FULL_IMAGE:figures/full_fig_p010_9.png]

**Figure 10.** Figure 10: FIG. 10. The classical and quantum complexities of the agents. In orange are both the classical and quantum complexity of [PITH_FULL_IMAGE:figures/full_fig_p010_10.png]

**Figure 11.** Figure 11: FIG. 11. Classical and quantum complexities of the [PITH_FULL_IMAGE:figures/full_fig_p010_11.png]

**Figure 10.** Figure 10: In orange, we have plotted the coinciding clas [PITH_FULL_IMAGE:figures/full_fig_p011_10.png]

**Figure 15.** Figure 15: FIG. 15. A 6-parameter family of input-output processes that [PITH_FULL_IMAGE:figures/full_fig_p012_15.png]

**Figure 14.** Figure 14: FIG. 14. A single agent reacting to two different stimuli. [PITH_FULL_IMAGE:figures/full_fig_p012_14.png]

**Figure 16.** Figure 16: FIG. 16. The difference of classical and quantum complexities [PITH_FULL_IMAGE:figures/full_fig_p013_16.png]

**Figure 17.** Figure 17: FIG. 17. The input stimulus described by the process [PITH_FULL_IMAGE:figures/full_fig_p015_17.png]

**Figure 20.** Figure 20: FIG. 20. The [PITH_FULL_IMAGE:figures/full_fig_p015_20.png]

**Figure 21.** Figure 21: FIG. 21. The [PITH_FULL_IMAGE:figures/full_fig_p015_21.png]

**Figure 23.** Figure 23: FIG. 23. The Ising spin chain process [PITH_FULL_IMAGE:figures/full_fig_p016_23.png]

**Figure 22.** Figure 22: FIG. 22. Input-output process that maps a biased coin to the [PITH_FULL_IMAGE:figures/full_fig_p016_22.png]

**Figure 24.** Figure 24: FIG. 24. The difference of classical and quantum complexi [PITH_FULL_IMAGE:figures/full_fig_p017_24.png]

**Figure 25.** Figure 25: FIG. 25. The [PITH_FULL_IMAGE:figures/full_fig_p022_25.png]

**Figure 26.** Figure 26: FIG. 26. An input-output process that does not exhibit am [PITH_FULL_IMAGE:figures/full_fig_p023_26.png]

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Dimension Reduction for Quantum Adaptive Agents
quant-ph 2026-07 accept novelty 7.0 of 10

A route–truncate–repair pipeline converts quantum adaptive agents' entropic memory savings into a smaller physical memory dimension with a certified fidelity-divergence rate.

Reference graph

Works this paper leans on

40 extracted references · 37 canonical work pages · cited by 1 Pith paper

[32]

T. M. Cover and J. A. Thomas,Elements of Information Theory(John Wiley & Sons, Ltd, 2005)

work page 2005
[1]

For a pair of statess i ands j ofJ, identify the corresponding statesχ k, χl in the output process, O

work page
[2]

Define the postulated inverse input-output states with labels (s i, χk) and (s j, χl)

work page
[3]

For each transition between statess i, sj ofJ, di- vide the probability in all emissions (x, y) with the corresponding probability of emissionybetweenχ k andχ l ofOand obtain the probabilities of condi- tional emissionsx|ybetween (s i, χk) and (sj, χl) of A−1

work page
[4]

Note that this algorithm will give an input-output pro- cess that mapsOtoIbut there may be undefined tran- sitions, which can are essentially free parameters

Repeat until all pairs of states ofJhave been con- sidered. Note that this algorithm will give an input-output pro- cess that mapsOtoIbut there may be undefined tran- sitions, 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 stat...

work page
[5]

Error-tolerant witnessing of divergences in classical and quantum statistical complexity

F. Ghafari, M. Gu, J. Ho, J. Thompson, W. Y. Suen, H. M. Wiseman, and G. J. Pryde, Error-tolerant wit- nessing of divergences in classical and quantum statistical complexity (2022), arXiv:1711.03661 [quant-ph]

work page Pith review arXiv 2022
[6]

This corresponds to taking the two inputsI A andI B in the general setting shown in Fig

The first consists of two different strategies that are executed by agents reacting to the same environmental stimulus. This corresponds to taking the two inputsI A andI B in the general setting shown in Fig. 6 to be the same, i.e.,I A =I B =I. The second consists of an agent that implements a single strategy when reacting to two different inputs, and cor...

work page
[7]

It remains to show this for the case withφ 1 > φ0 > min(φ′ 0, φ′

and φ′ 1 > φ′ 0, it is easy to show that φ0 > φ′ 0 =⇒r < r′.(I4) Then, withr < r′ andφ 0 > φ′ 0, we readily obtain that the classical complexities of the agent when driven by the biased coins with biasesrandr ′ are Cr < Cr′ .(I5) For the quantum complexities, we first obtain the eigenvalues of the average memory stateρ=φ 0|s0⟩ ⟨s0|+ φ1|s1⟩ ⟨s1|, which are...

work page

Show all 40 references

[8]

Appendix J: Excess entropies for scenario A We derive the excess entopies for scenario A in Section IV A

This follows, how- ever, directly from a symmetry argument. Appendix J: Excess entropies for scenario A We derive the excess entopies for scenario A in Section IV A. As the excess entropy of the input is zero, i.e.E I = 0, we have from Proposition 5 thatE A I =E J −E I =E J . ...
[9]

Barnett and J

N. Barnett and J. P. Crutchfield, Computational Me- chanics of Input–Output Processes: Structured Trans- formations and theϵ-Transducer, J Stat Phys161, 404 (2015)

2015
[10]

Thompson, A

J. Thompson, A. J. P. Garner, V. Vedral, and M. Gu, Us- ing quantum theory to simplify input–output processes, npj Quantum Inf3, 1 (2017), number: 1 Publisher: Na- ture Publishing Group

2017
[11]

T. J. Elliott, M. Gu, A. J. Garner, and J. Thomp- son, Quantum Adaptive Agents with Efficient Long-Term Memories, Phys. Rev. X12, 011007 (2022), publisher: American Physical Society

2022
[12]

Aghamohammadi, J

C. Aghamohammadi, J. R. Mahoney, and J. P. Crutch- field, The ambiguity of simplicity in quantum and classi- cal simulation, Physics Letters A381, 1223 (2017)

2017
[13]

M. Gu, K. Wiesner, E. Rieper, and V. Vedral, Quantum mechanics can reduce the complexity of classical models, Nat Commun3, 762 (2012)

2012
[14]

J. P. Crutchfield, The calculi of emergence: Computa- tion, dynamics and induction, Physica D: Nonlinear Phe- nomena75, 11 (1994)

1994
[15]

J. P. Crutchfield and K. Young, Inferring statistical complexity, Phys. Rev. Lett.63, 105 (1989), publisher: American Physical Society

1989
[16]

C. R. Shalizi and J. P. Crutchfield, Computational Me- chanics: Pattern and Prediction, Structure and Simplic- ity, Journal of Statistical Physics104, 817 (2001)

2001
[17]

J. P. Crutchfield, Between order and chaos, Nature Phys 8, 17 (2012), number: 1 Publisher: Nature Publishing Group

2012
[18]

Are quantum agents more energeti- cally efficient at making predictions?

Note that the input is Markovian since each emitted symbol identifies a unique state of theϵ-machine. Sim- ilarly, the input-output process is Markovian on output symbols. The joint and output process can be found through Eqs. (30) and (31). To derive theirϵ-machines, states n...

1903
[19]

Unifilarity is the property that guarantees determinism on the next state of the machine given the current state and emission
[20]

N. F. Travers and J. P. Crutchfield, Equivalence of history and generatorϵ-machines, Symmetry17, 10.3390/sym17010078 (2025)

2025 doi
[21]

C. J. Ellison, J. R. Mahoney, and J. P. Crutchfield, Pre- diction, Retrodiction, and the Amount of Information Stored in the Present, J Stat Phys136, 1005 (2009)

2009
[22]

Unifilarity of anϵ-transducer is the property that guaran- tees determinism on the next state of the machine given the current state, as well as current input and emission [1]
[23]

W. Y. Suen, J. Thompson, A. J. P. Garner, V. Vedral, and M. Gu, The classical-quantum divergence of com- plexity in modelling spin chains, Quantum1, 25 (2017)

2017
[24]

A. J. P. Garner, Q. Liu, J. Thompson, V. Vedral, and m. Gu, Provably unbounded memory advantage in stochastic simulation using quantum mechanics, New Journal of Physics19, 103009 (2017)

2017
[25]

Ghafari, N

F. Ghafari, N. Tischler, J. Thompson, M. Gu, L. K. Shalm, V. B. Verma, S. W. Nam, R. B. Patel, H. M. Wiseman, and G. J. Pryde, Dimensional Quantum Mem- ory Advantage in the Simulation of Stochastic Processes, Phys. Rev. X9, 041013 (2019)

2019
[26]

T. J. Elliott, C. Yang, F. C. Binder, A. J. P. Garner, J. Thompson, and M. Gu, Extreme Dimensionality Re- duction with Quantum Modeling, Phys. Rev. Lett.125, 260501 (2020)

2020
[27]

Thompson, A

J. Thompson, A. J. Garner, J. R. Mahoney, J. P. Crutch- field, V. Vedral, and M. Gu, Causal Asymmetry in a Quantum World, Phys. Rev. X8, 031013 (2018), pub- lisher: American Physical Society

2018
[28]

Kechrimparis, M

S. Kechrimparis, M. Gu, and H. Kwon, Causal Asym- metry of Classical and Quantum Autonomous Agents (2023), arXiv:2309.13572 [quant-ph]

2023 arXiv
[29]

Jozsa and J

R. Jozsa and J. Schlienz, Distinguishability of states and von Neumann entropy, Phys. Rev. A62, 012301 (2000)

2000
[30]

A. S. Holevo, Bounds for the quantity of information transmitted by a quantum communication channel, Prob- lemy Peredachi Informatsii9, 3 (1973), in Russian. En- glish translation: Problems of Information Transmission, vol. 9, no. 3, pp. 177–183, 1973

1973
[31]

M. A. Nielsen and I. L. Chuang,Quantum Computa- tion and Quantum Information: 10th Anniversary Edi- tion(Cambridge University Press, 2010)

2010
[33]

J. P. Crutchfield, C. J. Ellison, and J. R. Mahoney, Time’s Barbed Arrow: Irreversibility, Crypticity, and Stored Information, Phys. Rev. Lett.103, 094101 (2009), publisher: American Physical Society

2009
[34]

G. F. Knoll,Radiation Detection and Measurement (John Wiley & Sons, 2010)

2010
[35]

Migdall,Single-Photon Generation and Detection, Ex- perimental Methods in the Physical Sciences, Volume 45 (Academic Press, Waltham, MA, 2013)

A. Migdall,Single-Photon Generation and Detection, Ex- perimental Methods in the Physical Sciences, Volume 45 (Academic Press, Waltham, MA, 2013)

2013
[36]

C. J. Ellison, J. R. Mahoney, R. G. James, J. P. Crutch- field, and J. Reichardt, Information symmetries in irre- versible processes, Chaos21, 037107 (2011)

2011
[37]

R. G. James, J. R. Mahoney, C. J. Ellison, and J. P. Crutchfield, Many roads to synchrony: Natural time scales and their algorithms, Phys. Rev. E89, 042135 (2014), publisher: American Physical Society

2014
[38]

N. F. Travers and J. P. Crutchfield, Exact Synchroniza- tion for Finite-State Sources, J Stat Phys145, 1181 (2011)

2011
[39]

Thompson, P

J. Thompson, P. M. Riechers, A. J. Garner, T. J. Elliott, and M. Gu, Energetic advantages for quantum agents in online execution of complex strategies, arXiv preprint arXiv:2503.19896 (2025)

2025 arXiv
[40]

N. Barnett,Mechanisms within the Black Box: Pre- diction, Computation, Randomness, and Complexity of Input-Output Processes via theε-Transducer(Unpub- lished doctoral dissertation, University of California, 2016)

2016

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.

[1] [32]

T. M. Cover and J. A. Thomas,Elements of Information Theory(John Wiley & Sons, Ltd, 2005)

work page 2005

[2] [1]

For a pair of statess i ands j ofJ, identify the corresponding statesχ k, χl in the output process, O

work page

[3] [2]

Define the postulated inverse input-output states with labels (s i, χk) and (s j, χl)

work page

[4] [3]

For each transition between statess i, sj ofJ, di- vide the probability in all emissions (x, y) with the corresponding probability of emissionybetweenχ k andχ l ofOand obtain the probabilities of condi- tional emissionsx|ybetween (s i, χk) and (sj, χl) of A−1

work page

[5] [4]

Note that this algorithm will give an input-output pro- cess that mapsOtoIbut there may be undefined tran- sitions, which can are essentially free parameters

Repeat until all pairs of states ofJhave been con- sidered. Note that this algorithm will give an input-output pro- cess that mapsOtoIbut there may be undefined tran- sitions, 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 stat...

work page

[6] [5]

Error-tolerant witnessing of divergences in classical and quantum statistical complexity

F. Ghafari, M. Gu, J. Ho, J. Thompson, W. Y. Suen, H. M. Wiseman, and G. J. Pryde, Error-tolerant wit- nessing of divergences in classical and quantum statistical complexity (2022), arXiv:1711.03661 [quant-ph]

work page Pith review arXiv 2022

[7] [6]

This corresponds to taking the two inputsI A andI B in the general setting shown in Fig

The first consists of two different strategies that are executed by agents reacting to the same environmental stimulus. This corresponds to taking the two inputsI A andI B in the general setting shown in Fig. 6 to be the same, i.e.,I A =I B =I. The second consists of an agent that implements a single strategy when reacting to two different inputs, and cor...

work page

[8] [7]

It remains to show this for the case withφ 1 > φ0 > min(φ′ 0, φ′

and φ′ 1 > φ′ 0, it is easy to show that φ0 > φ′ 0 =⇒r < r′.(I4) Then, withr < r′ andφ 0 > φ′ 0, we readily obtain that the classical complexities of the agent when driven by the biased coins with biasesrandr ′ are Cr < Cr′ .(I5) For the quantum complexities, we first obtain the eigenvalues of the average memory stateρ=φ 0|s0⟩ ⟨s0|+ φ1|s1⟩ ⟨s1|, which are...

work page