Entropy rate of message sources driven by quantum walks

The amount of information generated by a discrete time stochastic processes in a single step can be quantified by the entropy rate. We investigate the differences between two discrete time walk models, the discrete time quantum walk and the classical random walk, in terms of entropy rate. We develop analytical methods to calculate and approximate it. This allows us to draw conclusions about the differences between classical stochastic and quantum processes in terms of the classical information theory.

Figure 1

Convergence of the numerically calculated partial entropy rate $H_2$ for $w=2$ waiting time. We have evaluated the definition of Eq. (1) for the first $n$ iteration steps, using the joint probability distribution in Eq. (17). We used the 1D QW with Hadamard coin [see Eq. (16)]; the triangles and circles correspond to the walk started from initial states $|{\psi }_0\rangle =|0,L\rangle$ and $|{\psi }_0\rangle =\frac{1}{\sqrt{2}}\left(|0,L\rangle +|0,R\rangle \right)$, respectively. The continuous line corresponds to the analytically determined rate for the simulated model: $H_2^{\text{QW}}=4/3$ bits. The dashed line corresponds to the rate of the CW: $H_2^{\text{CW}}=3/2$ bits.

Figure 2

Entropy rates $H_w$ of the frequently measured walks on a 1D line as functions of waiting time $w$. The circles correspond to the entropy rate $H_w^{\text{CW}}$ [see Eq. (6)] of the classical walk. We used the Hadamard coin of Eq. (16) for the quantum walk. The black disks corresponds to the exactly calculated entropy rate $H_w^{\text{QW}}$ given by Eq. (28), while the vertical line segments correspond to the interval defined by the lower and upper bound on the entropy rate in Eq. (39). The triangles correspond to the upper bound entropy rate $H_w^{\text{bound}}$ defined in Sec. 5, while the continuous line represents the analytic approximation $H_w^{\text{approx}}$ of Eq (49).

Figure 3

Entropy rate $H_w$ of periodically measured walks as the function of waiting time $w$. We used QW (triangles) with Hadamard coin [see Eq. (16)] and the unbiased CW (circles) on the cycle graph with 16 vertices. For the QWs we plotted the protocol giving the upper bound. The straight line corresponds to the theoretical entropy rate limit of Eq. (7): $H_{\mathrm{limit}}={log}_{2}M-1=3$ bits. In the inset plot, we show traces of the collapse and revive like effects on the same system for high $w$ waiting times: For $w=216$ the time evolution operator comes very close to a simple permutation matrix, resulting in a very predictable behavior and an entropy rate upper bound $H_{216}^{\mathrm{bound}}\approx 0.514$ bits. Meanwhile, the CW is totally mixing, resulting in an unpredictable outcome, with the maximal possible entropy rate $H_{\mathrm{limit}}=3$ bits. We calculated all plotted data numerically using the Monte Carlo method until convergence occurred.

Figure 4

Upper bound of the entropy rate $H_w^{\text{bound}}$ of an 1D QW with Hadamard coin [see Eq. (16)], denoted by circles, for infinite or finite ($w\ll M$) systems. We used high-precision numerical simulations and plotted the converged results. The dashed line corresponds to the analytically calculated entropy rate of CWs [see Eq. (6)], while the continuous line corresponds to the weak-limit-based approximation of Eq. (49).