Minimized state complexity of quantum-encoded cryptic processes

The predictive information required for proper trajectory sampling of a stochastic process can be more efficiently transmitted via a quantum channel than a classical one. This recent discovery allows quantum information processing to drastically reduce the memory necessary to simulate complex classical stochastic processes. It also points to a new perspective on the intrinsic complexity that nature must employ in generating the processes we observe. The quantum advantage increases with codeword length: the length of process sequences used in constructing the quantum communication scheme. In analogy with the classical complexity measure, statistical complexity, we use this reduced communication cost as an entropic measure of state complexity in the quantum representation. Previously difficult to compute, the quantum advantage is expressed here in closed form using spectral decomposition. This allows for efficient numerical computation of the quantum-reduced state complexity at all encoding lengths, including infinite. Additionally, it makes clear how finite-codeword reduction in state complexity is controlled by the classical process's cryptic order, and it allows asymptotic analysis of infinite-cryptic-order processes.

Figure 1

$\epsilon$-Machine for the (4–3)-Golden Mean Process: The cycle's red segment (labeled $R=4$) indicates the “Markov” portion, and the green (labeled $k=3$) the “cryptic” portion. The length scales $R$ and $k$ are tuned by changing the lengths of these two components, respectively. Edges labeled $x\text{:}p$ denote taking the state-to-state transition with probability $p$ while emitting symbol $x\in \mathcal{A}$.

Figure 2

Quantum pairwise-merger machine for the (4–3)-Golden Mean Process. Its depth is related to the cryptic order $k$.

Figure 3

$L$-merge: Two causal state paths, $(a_0,...,a_{L-1},F)$ and $(b_0,...,b_{L-1},F)$ where states $a_i\ne b_i$, for all $i\in \{0,...,L-1\}$, generate the same word $w=x_0{x}_1...x_{L-1}$ and merge only on the last output symbol $x_{L-1}$ into a common final state $F$.

Figure 4

$\epsilon$-Machine for the (7–4)-Lollipop Process. The cycle of 0s on the right leads to infinite Markov and cryptic orders.

Figure 5

Quantum pairwise-merger machine for the (7–4)-Lollipop Process.

Figure 6

Quantum costs $C_q\left(L\right)$ for the ($R–k$)-Golden Mean Process with $R\in \{1,...,6\}$ and $k\in \{1,...,R\}$. $R$ and $k$ are indicated with line width and color, respectively. The probability of the self-loop is $p=0.7$. $C_q\left(L\right)$ roughly linearly decreases until $L=k$ where it is then constant. Note that ($R–k$)-GM agrees exactly with $((R+1)–(k-1))$-GM for $L\le k$, as explained in Appendix pp4.

Figure 7

Quantum costs $C_q\left(L\right)$ for the Lollipop process for $N\in \{3,4,5,6\}, M\in \{2,3,4,5,6\}, p=q=0.5$, and $r=0.1$. $N$ and $M$ are indicated with line width and color, respectively. After a fast initial decrease, these curves approach their asymptotic values more slowly.

Figure 8

(8,8)-Lollipop with transition parameters $p\in [0.1,0.9], q=0.5$, and $r=0.1$. $C_q\left(L\right)-C_q\left(\infty \right)$ on semilog plot illustrates asymptotically exponential behavior. Red dashed lines, $r_1^L$ where $r_1$ (no relation to $r$) is the spectral radius of $\zeta$, quantify the exponential rate of decay. The height of each red dashed line is set equal to $C_q\left(49\right)$; we can see that the decay is very close to exponential even as early as $L\simeq 15$. Vertical dashed line at $L=M=8$ shows change in behavior after the length of the “stick.”

Figure 9

Lollipop with $N\in \{3,4,5,6,7,8\}$ and $M=8$, and transition parameters $p=q=0.5$ and $r=0.1$. $\left(C_q\left(L\right)-C_q\left(\infty \right)\right)/r_1^L$ demonstrates the periodicity of asymptotic behavior. Removing the exponential envelope makes periodicity of the remaining deviation more apparent. For Lollipop, the periodicity $\mathrm{\Psi }=\left|\mathrm{\Lambda }\right(r_1\left)\right|=N$.

Figure 10

$C_q\left(L\right)-C_q\left(\infty \right)$ on a semilog plot for Lollipop with $N=6$ and $M\in \{2,...,20\}$ and transition parameters $p=q=0.5$ and $r=0.1$. $M$ determines the finite-horizon length, where the nilpotent part of $\zeta$ vanishes. Vertical (dashed) lines indicate $L=2$ and 20, the shortest and longest such length in this group.

Figure 11

$\epsilon$-Machine for the Biased Coins Process.

Figure 12

QPMM for the Biased Coins Process.

Figure 13

$\epsilon$-Machine for the ($R–k$)-Golden Mean Process.