Ideal stochastic process modeling with post-quantum quasiprobabilistic theories

1. Problem Statement

In stochastic process modeling, the fundamental goal is to simulate a process's dynamics with minimal memory.

• The Lower Bound: The theoretical lower bound for the memory required to simulate a process is the Excess Entropy ($E$), defined as the mutual information shared between the process's past and future.
• The Gap:
  • Classical Models: The optimal causal classical model, the $\epsilon$-machine, has a statistical complexity ($C_\mu$) that is strictly greater than $E$ for most processes ($C_\mu > E$). This gap arises because causal models cannot store "oracular" information (information about the future not derivable from the past).
  • Quantum Models: Quantum hidden Markov models (q-machines) can reduce memory usage below the classical limit ($C_q < C_\mu$) by encoding states in non-orthogonal quantum states. However, they remain non-ideal, meaning $C_q > E$ for most processes.
• The Core Question: Can an ideal model be constructed where the memory cost exactly equals the excess entropy ($C = E$)? If so, what physical or mathematical constraints must be relaxed to achieve this?

2. Methodology

The authors propose a framework based on Generalized Probabilistic Theories (GPT) that extends beyond classical and quantum mechanics by allowing negative probabilities (quasiprobabilities).

A. Theoretical Framework: $n$-machines

The authors introduce the $n$-machine (negative-machine), a generalization of Hidden Markov Models (HMMs).

• Construction Protocol:
  1. State Splitting: Start with a classical $\epsilon$-machine with causal states $S$. Split each state $\sigma_k$ into a set of sub-states $\{\tilde{\sigma}_{k, l_k}\}$.
  2. Quasiprobabilistic Transitions: Define transition probabilities between these sub-states. Crucially, these probabilities are allowed to be negative (quasiprobabilities), provided they sum to the original positive transition probabilities of the $\epsilon$-machine when aggregated.
  3. Optimization: Minimize the memory cost subject to the constraint that the model generates the exact same stochastic process.

B. Information-Theoretic Measures

To accommodate quasiprobabilities (which can be negative), the authors replace Shannon entropy ($\alpha=1$) with Rényi entropy of order $\alpha=2$ (Collision Entropy).

• 2-Statistical Complexity ($C^{(2)}$): Defined as $H_2[\pi] = -\log \sum \pi_k^2$. This measures the memory cost of the internal state distribution.
• 1/2-Excess Entropy ($E^{1/2}$): Defined using Rényi mutual information with $\alpha=1/2$.
• Justification: Rényi-2 entropy is well-defined for quasiprobability distributions and satisfies necessary axioms (real-valuedness, symmetry, Schur-concavity). It also has operational interpretations in source coding and privacy amplification.

3. Key Contributions

1. Proof of Existence of Ideal Models: The paper demonstrates that by relaxing the positivity constraint on probabilities (allowing quasiprobabilities), one can construct models where the memory cost saturates the lower bound:
   $$C^{(2)}_n = E^{1/2}$$
   This proves that ideal stochastic modeling is possible within the realm of post-quantum GPTs.

2. The $n$-Machine Construction: A general protocol is provided to transform any classical $\epsilon$-machine into an ideal $n$-machine. This involves:

   • Extending the state space.
   • Introducing negative transition probabilities to cancel out "redundant" memory costs while preserving the output statistics.
   • Ensuring the stationary distribution remains a valid quasiprobability (summing to 1, but containing negative entries).

3. Negativity as a Resource: The authors establish a direct quantitative relationship between negativity (measured by the $l_1$-norm of the quasiprobability distribution) and memory advantage.

   • As the amount of negativity in the model increases, the memory advantage (reduction in $C^{(2)}$) increases.
   • Negativity is shown to be a necessary resource for achieving the ideal memory limit, analogous to how negativity is a resource for quantum computational advantage.

4. Operational Interpretation: The paper provides operational meanings for Rényi-2 complexity in the context of synchronizing two independent machines and decoding errors, validating its use even for non-classical models.

4. Results and Examples

The authors validate their theory using two paradigmatic stochastic processes:

• Perturbed Coin Process:

  • Classical ($C^{(2)}_\mu$): 1 bit.
  • Quantum ($C^{(2)}_q$): Less than 1 bit but greater than $E^{1/2}$.
  • $n$-Machine ($C^{(2)}_n$): Constructed to exactly equal $E^{1/2}$.
  • Finding: The memory advantage correlates linearly with the negativity of the stationary distribution.

• Simple Nonunifilar Source (SNS) Process:

  • This process has an infinite number of causal states in its classical $\epsilon$-machine but only two states in its optimal generative machine ($g$-machine).
  • The authors constructed an $n$-machine starting from the $g$-machine that achieves $C^{(2)}_n = E^{1/2}$.
  • Again, the memory compression is directly linked to the introduction of negative probabilities in the transition matrix.

• Counter-Example (Golden Mean Process):

  • The authors show that simply introducing negativity is not sufficient for memory reduction. A "bad" $n$-machine construction with negative transitions but poor state splitting failed to reduce memory, highlighting that the structure of the negativity injection matters.

5. Significance and Implications

• Fundamental Limits of Simulation: The work establishes that the gap between memory cost and excess entropy ($C > E$) is not a fundamental law of physics but a consequence of the positivity constraint on probabilities.
• Post-Quantum Advantage: It suggests that "post-quantum" theories (specifically those allowing quasiprobabilities) offer a distinct advantage over standard quantum mechanics in terms of memory efficiency for stochastic simulation.
• Thermodynamic Implications: Since memory dissipation is linked to heat generation (Landauer's principle), ideal models ($C=E$) would theoretically be the most thermodynamically efficient. The paper suggests that ideal models might violate current thermodynamic bounds if they rely on unrestricted negativity, opening new avenues for studying the thermodynamics of information in GPTs.
• Unification of Models: By using the quasiprobability representation, the authors provide a formalism to compare classical, quantum, and post-quantum models on an equal footing, revealing that quantum memory advantages may stem from similar mechanisms (state splitting and negativity) as post-quantum advantages.

In conclusion, the paper proves that ideal stochastic modeling is achievable if one accepts the physical reality of quasiprobabilities, identifying negativity as the critical resource that enables the saturation of the excess entropy bound.