Quantum Dynamical Entropies and Gács Algorithmic Entropy

Abstract

Several quantum dynamical entropies have been proposed that extend the classical Kolmogorov–Sinai (dynamical) entropy. The same scenario appears in relation to the extension of algorithmic complexity theory to the quantum realm. A theorem of Brudno establishes that the complexity per unit time step along typical trajectories of a classical ergodic system equals the KS-entropy. In the following, we establish a similar relation between the Connes–Narnhofer–Thirring quantum dynamical entropy for the shift on quantum spin chains and the Gács algorithmic entropy. We further provide, for the same system, a weaker linkage between the latter algorithmic complexity and a different quantum dynamical entropy proposed by Alicki and Fannes.

1. Introduction

Several proposals have been put forward with the aim of extending the dynamical entropy of Kolmogorov and Sinai (KS-entropy) [1] to the quantum realm [2,3,4,5,6]. The KS-entropy is a dynamical invariant and a powerful indicator of the randomness of a classical dynamical system as it accounts for the predictability of the future based on the knowledge of the past. Roughly speaking, the KS-entropy measures our knowledge about the next step along a typical phase-space trajectory provided one knows the trajectory’s past. Since in quantum mechanics there are neither phase-space nor trajectories and, moreover, observations perturb the observed system, many different non-commutative extensions can be envisaged, all of them reducing to the KS-invariant in the case of classical, that is, commutative systems.

While the KS-entropy is related to the rate at which information is produced by the dynamics with respect to an equilibrium state, algorithmic complexity theory has been developed by Kolmogorov, Solomonoff and Chaitin [7] in order to qualify and quantify the randomness of individual objects, say binary strings, independently of the statistical ensemble of which they may be part, that is, independently of any a-priori probability distribution. In fact, probability theory cannot sort out regular from random binary strings; for instance, in the case of a fair coin tossing, all strings of N zeroes and ones have the same probability $2^{-N}$. Instead, algorithmic complexity measures their randomness based upon the difficulty of description by means of programs that run by Universal Turing Machines (UTM) to reproduce the target string.

The connection between the KS-entropy and classical algorithm complexity was established by a theorem of Brudno [8,9] who proved that for ergodic classical systems the algorithmic complexity per unit step of typical trajectories equals the KS-entropy.

The quantum extensions of the KS-entropy in [2,3,4,5,6] were formulated before quantum information and computation theory revolutionized our views concerning the transmission and manipulation of information [10]. The mere possibility of having quantum computers at disposal that might outperform classical computers aroused the need of confronting the notion of algorithmic complexity with the new avenues opened up by non-commutativity. The development of quantum information raised the question of which impact the existence of quantum computers may have on the issue of the algorithmic complexity of classical and quantum states [11]; in other words, can one do with classical algorithmic complexity or is it necessary to formulate a quantum algorithmic complexity that generalizes the classical notion? If one tries to pursue the second objective, the same scenario appears as for the quantum extension of the KS-entropy: several inequivalent and more or less related quantities have been put forward [12,13,14,15].

In the very special case of the space-translations over quantum spin chains, a quantum analogue of Brudno’s relation was proved to exist [16,17] between Connes–Narnhofer–Thirring [2] (CNT-) entropy and Berthiaume–van Dam–Laplante algorithmic complexity [13]; in the following we shall instead consider the Gács algorithmic entropy [14] and show how it is related to the CNT-entropy and the entropy of Alicki and Fannes (AF-entropy).

The paper is organized as follows: in Section 2, we briefly survey certain basic aspects of quantum mechanics and quantum information, in particular the notion of quantum spin chain and its von Neumann entropy rate. In Section 3, we first reformulate the notion of classical stationary source in a way where it appears as a particular realization of a quantum one; then, we summarize the fundamentals of algorithmic complexity theory and its relation to Shannon entropy and algorithmic probability. In Section 4, we introduce the AF-entropy, compute it for a binary quantum spin chain, explain the difference between the latter and the CNT-entropy and relate it to the measurement processes. In Section 5, we introduce Gács algorithmic entropy and establish a relation between it and the CNT and AF-entropies. Finally, in the conclusions we comment on the difficulties and the necessary steps to arrive at a full quantum Brudno theorem.

2. Qubits: Fundamentals

The generalization of a classical bit is a qubit, namely any quantum degree of freedom that can be described by a two-dimensional Hilbert space, like a spin $1/2$ particle, photon polarization or a two-level atom. A qubit vector state is thus an element of a two-dimensional Hilbert space:

$$\mathbb{H}={\mathbb{C}}^2\ni |\psi \rangle =\left(\begin{array}{c}x\\ y\end{array}\right)=x\left(\begin{array}{c}1\\ 0\end{array}\right)+y\left(\begin{array}{c}0\\ 1\end{array}\right),{\left|x\right|}^2+{\left|y\right|}^2=1$$

(1)

Classical bits can then be identified by the elements of the orthonormal basis ${\displaystyle \left(\begin{array}{c}1\\ 0\end{array}\right),\left(\begin{array}{c}0\\ 1\end{array}\right)}$, while generic qubit (vector) states are as in (1). Classical binary strings of length n, $i^{\left(n\right)}=i_1{i}_2\cdots i_n$, will then correspond to the tensor product states ${⨂}_{\ell =1}^n|i_{\ell }\rangle$ in the Hilbert space ${\left({\mathbb{C}}^2\right)}^{\otimes n}={\mathbb{C}}^{2^n}$. Though these states are easily associated to familiar concepts from classical information theory, generic linear combinations of these elementary states escape such an association. Even more, Hilbert space vectors are described by pure state projectors $P_{\psi }=|\psi \rangle \langle \psi |$, and generic quantum states by mixed states or density matrices, $\rho ={\sum }_j{\lambda }_j{P}_{{\psi }_j}$. These are convex combinations of projections and are (non-uniquely) associated with statistical ensembles of pure states $P_{{\psi }_j}$ mixed with weights ${\lambda }_j\ge 0$, ${\sum }_j{\lambda }_j=1$.

An important indicator of the mixedness of a state ρ is its von Neumann entropy:

$$S\left(\rho \right)=-\mathrm{Tr}\rho log\rho =-\sum _{i=1}^2{r}_{i}log{r}_i$$

(2)

where $r_i$ are the eigenvalues of ρ such that $\rho |r_i\rangle =r_i|r_i\rangle$ with orthonormal eigenvectors $\langle r_i|r_j\rangle ={\delta }_{ij}$. In the following log will denote the logarithm in base 2: $log2=1$

Any quantum mechanical process can be schematized in three steps: a preparation process, a time-evolution and a measurement process. Differently from the time-evolution, preparation and measurement are always irreversible processes. The last one is the most relevant of the two as it corresponds to reading the system, an irreversible quantum process that collapses the system states from pure ones to mixtures. These processes, also known as wave-packet reductions, correspond to the following completely positive maps [17,18]

$$P_{\psi }⟼M\left[P_{\psi }\right]=\sum _i{X}_i|\psi \rangle \langle \psi |X_i^{†},\sum _i{X}_i^{†}{X}_i=1$$

(3)

The set $\mathcal{X}={\left\{X_i\right\}}_{i\in I}$ of bounded operators on the system Hilbert space is known as POVM and the corresponding processes do in general increase entropy: $S\left(M\left[P_{\psi }\right]\right)\ge S\left(P_{\psi }\right)=0$.

Quantum Information Sources

From the algebraic point of view, a qubit is described by the algebra $M_2\left(\mathbb{C}\right)$ of $2\times 2$ complex matrices acting on ${\mathbb{C}}^2$; whence n qubits by the tensor product algebra

$$M_{[1,n]}=M_2\left(\mathbb{C}\right)\otimes M_2\left(\mathbb{C}\right)\otimes \cdots M_2\left(\mathbb{C}\right)=M_2^{\otimes n}=M_{2^n}\left(\mathbb{C}\right)$$

(4)

also called local spin algebra. It proves convenient to figure it out as describing n qubits located at the sites from $\ell =0$ to $\ell =n-1$ of a 1-dimensional lattice. Of course, one can locate n qubits along any segment $[-p,-p+n-1]$; let $n=2p$, the family of local spin algebras $M_{[-p,p-1]}$ can be completed, via an inductive limit, to an infinite dimensional $C^{*}$ algebra [18,19], or two-sided quantum spin chain,

$${\mathcal{M}}_2:=\underset{p}{lim}{M}_{[-p,p-1]}$$

(5)

In such a context the qubit at site 0 is described by observables of the form $1_{-1]}\otimes A\otimes 1_{[1}$ where $A\in M_2\left(\mathbb{C}\right)$ and $1_{-1]}$ stands for the infinite tensor products of identity matrices up to site $-1$, while $1_{[1}$ for the infinite tensor product of infinitely many identity matrices from site 1 onwards.

The simplest dynamics on such a quantum spin chain is given by the right shift

$$\Theta \left[M_{[-p,p-1]}\right]=M_{[-p+1,p]},\Theta [1_{-p-1]}\otimes A_{[-p,p-1]}\otimes 1_{[p}]=1_{-p]}\otimes A_{[-p,p-1]}\otimes 1_{[p+1}$$

(6)

Any probability distribution over a classical source is assigned by fixing the probability measures of the local configurations; in the same vein, a global state on the quantum spin chain is determined by local density matrices on ${\mathbf{M}}_{[-p,p-1]}$. Translation-invariant states on ${\mathcal{M}}_2$ are then equivalent to a family of density matrices ${\rho }^{\left(n\right)}$ defining the quantum statistic for all local algebras $M_{[-p,-p+n-1]}$, independently of p; these density matrices determine a global, shift-invariant state ω on ${\mathcal{M}}_2$, in the sense that

$$\omega \left(A_{[0,n-1]}\right)=\mathrm{Tr}\left({\rho }^{\left(n\right)}{A}_{[0,n-1]}\right)=\omega \left({\Theta }^p\left[A_{[0,n-1]}\right]\right)$$

for all $A_{[0,n-1]}\in M_{[0,n-1]}\left(\mathbb{C}\right)$ and $p\ge 0$.

To such a global state one associates the von Neumann Entropy rate

$$s\left(\omega \right)=\underset{n\to +\infty }{lim}\frac{1}{n}S\left({\rho }^{\left(n\right)}\right)=-\underset{n\to +\infty }{lim}\frac{1}{n}\mathrm{Tr}{\rho }^{\left(n\right)}log{\rho }^{\left(n\right)}$$

(7)

that corresponds to the entropy rate of classical stationary sources [20].

The entropy per unit step $s\left(\omega \right)$ is also the quantum dynamical entropy of the shift as proposed by Connes, Narnhofer and Thirring in [2], but differs, as we shall see, from the quantum dynamical entropy of Alicki and Fannes [3].

3. Classical Algorithmic Complexity and Entropy

In the light of the previous section, classical information sources can be accounted for as commutative spin chains, consisting of spins at each site that can be either up, $|i=0\rangle$, or down, $|i=1\rangle$, along a fixed direction in space. Namely, at each site of the lattice one locates diagonal $2\times 2$ matrix algebras and diagonal p-site algebras are equipped with diagonal p dimensional density matrices. Finite binary strings $i^{\left(n\right)}\in {\Omega }_2^n$ correspond to projectors that are tensor products of single bit projectors:

$$|i^{\left(n\right)}\rangle \langle i^{\left(n\right)}|=|i_1\rangle \langle i_1|\otimes |i_2\rangle \langle i_2|\otimes \cdots |i_n\rangle \langle i_n|$$

(8)

local probability distributions ${\mu }^{\left(n\right)}=\left\{\mu \left(i^{\left(n\right)}\right)\right\}$ to diagonal density matrices

$${\rho }_{\mu }^{\left(n\right)}=\sum _{i^{\left(n\right)}}\mu \left(i^{\left(n\right)}\right)|i^{\left(n\right)}\rangle \langle i^{\left(n\right)}|$$

(9)

whose von Neumann entropy equals the Shannon entropy of ${\mu }^{\left(n\right)}$,

$$S\left({\rho }_{\mu }^{\left(n\right)}\right)=-\sum _{i^{\left(n\right)}}\mu \left(i^{\left(n\right)}\right)log\mu \left(i^{\left(n\right)}\right)=H\left({\mu }^{\left(n\right)}\right)$$

(10)

If the local probability distributions give rise to a translation-invariant global probability measure μ, then the stationary source is characterized by the (Shannon) entropy rate

$$h\left(\mu \right)=\underset{n\to +\infty }{lim}\frac{1}{n}H\left({\mu }^{\left(n\right)}\right)$$

(11)

The entropy rate of a classical stationary source is just the simplest example of KS-entropy, here the dynamics corresponding to the shift along the words emitted by the source, or along the diagonal spin chain in the quantum-like approach proposed above. In general, for a dynamical system equipped with an equilibrium state, one reduces to a suitable shift over a symbolic model by means of a finite partition of the system phase-space [1].

3.1. Algorithmic Complexity

In algorithmic complexity theory as developed by Kolmogorov, Solomonoff and Chaitin, one attributes to a binary string $i^{\left(n\right)}\in {\Omega }_2^n$ of length n a complexity $K\left(i^{\left(n\right)}\right)$ measured by the length of any shortest program $p^{*}$, that is, another binary string of length $\ell \left(p^{*}\right)$, read by a prefix Universal Turing Machine (UTM) $\mathcal{U}$, would output $i^{\left(n\right)}$, $\mathcal{U}\left[p^{*}\right]=i^{\left(n\right)}$,

$$K\left(i^{\left(n\right)}\right)=min\left\{\ell \left(p\right):\mathcal{U}\left[p\right]=i^{\left(n\right)}\right\}$$

(12)

The prefix property means that if $\mathcal{U}$ halts on a program p it does not continue to read on if another program q is appended to p; in other words, no halting program can be used as prefix to a halting program.

Suppose one has an (algorithmically) computable probability distribution ${\mu }^{\left(n\right)}=\left\{\mu \left(i^{\left(n\right)}\right)\right\}$ on the statistical ensemble of strings of length n, ${\Omega }_2^n={\{0,1\}}^n$. Then, the Shannon entropy is essentially the average Kolmogorov complexity; specifically,

$$\left|H\left({\mu }^{\left(n\right)}\right)-\sum _{i^{\left(n\right)}\in {\Omega }_2^n}\mu \left(i^{\left(n\right)}\right)K\left(i^{\left(n\right)}\right)\right|\le K\left({\mu }^{\left(n\right)}\right)$$

(13)

where $K\left({\mu }^{\left(n\right)}\right)$ is the complexity of the computable probability distribution [7]. Brudno [9] proved that, for ergodic sources, the difference disappears if one considers the rates. Actually, Brudno proved much more as his theorem establishes a relation between the entropy rate and the algorithmic information per unit step of almost all trajectories with respect to the ergodic measure of the source:

$$h\left(\mu \right)=\underset{n\to +\infty }{lim}\frac{1}{n}H\left({\mu }^{\left(n\right)}\right)=k\left(i\right):=\underset{n\to +\infty }{lim}\frac{1}{n}K\left(i^{\left(n\right)}\right)$$

(14)

for almost all sequences i with respect to the measure μ, that is, the set of sequences where the equality fails has measure 0.

As already noticed, the Shannon entropy rate $h\left(\mu \right)$ is the Kolmogorov–Sinai entropy associated to the shift dynamics; therefore, the source entropy rate can also be interpreted as the maximal information provided by the shift dynamics per unit step of time. Indeed, Brudno’s theorem shows that the equality holds between the KS-entropy, that is the dynamical entropy, and the algorithmic complexity rate along almost all trajectories of a generic ergodic classical dynamical system.

3.2. Universal Probability

With prefix UTMs one attributes a universal probability [7] $\mathbb{P}\left(i^{\left(n\right)}\right)$ to all strings $i^{\left(n\right)}\in {\Omega }_2^n$:

$$\mathbb{P}\left(i^{\left(n\right)}\right):=\sum _{p:\mathcal{U}\left[p\right]=i^{\left(n\right)}}{2}^{-\ell \left(p\right)},\mathcal{U}\text{prefix}\text{UTM}$$

(15)

Notice that ${\sum }_{i^{\left(n\right)}}\mathbb{P}\left(i^{\left(n\right)}\right)\le 1$ because the prefix property implies the Kraft’s inequality [20]. The map $\mathbb{P}$ defines a semi-computable semi-measure on ${\Omega }_2^n$: indeed, it is not normalized and can be approximated only from below because we cannot be sure that $\mathcal{U}$ will ever halt on a given program (Halting Problem) [7]. Furthermore, for all other semi-computable semi-measures μ, there exists a constant $C\left(\mu \right)\ge 0$ depending only on μ and not on the input string $i^{\left(n\right)}$ such that

$$C\left(\mu \right)\mu \left(i^{\left(n\right)}\right)\le \mathbb{P}\left(i^{\left(n\right)}\right)$$

(16)

This relation exhibits the universality of the algorithmic probability. Most important of all is the connection between universal probability and algorithmic complexity:

$$\left|K\left(i^{\left(n\right)}\right)+log\mathbb{P}\left(i^{\left(n\right)}\right)\right|\le C$$

(17)

where C is a constant independent of $i^{\left(n\right)}$.

4. Alicki–Fannes Entropy

In a snapshot, the previous sections indicate that the complexity of the strings emitted by ergodic classical information sources is essentially captured by the Shannon entropy rate of the source; indeed, the ensemble point of view (Shannon entropy rate) and the individual point of view (algorithmic complexity) give the same complexity per unit step (Brudno’s theorem).

Moving from classical to quantum sources, the obvious question is: what measures the complexity of quantum information sources? One first answer is the von Neumann entropy rate; however, this is a quantifier that is neither sensitive to the specific structure of the statistical ensemble nor to the objects (quantum states) that compose the statistical ensemble. Furthermore, from the point of view of the spirit behind the construction of the KS-entropy, predictions have to be made provided some information have been gathered. However, unlike for classical systems, gathering information on a time-evolving quantum system unavoidably perturbs the state of the system. How could then measurement processes (3) be incorporated into the definition of the complexity of the shift along quantum spin chains? The answer is given by the Alicki–Fannes entropy [3,18], whose main ideas we now briefly summarize for the specific case of quantum spin chains.

We shall identify a quantum spin chain by the triple $({\mathcal{M}}_2,\omega ,\Theta )$ and denote as partition of unit any finite collection

$$\mathcal{X}={\left\{X_i\right\}}_{i=1}^m,\sum _{i=1}^m{X}_i^{†}{X}_i=1,X_i\in {\mathcal{M}}_2$$

(18)

of local operators $X_i$ belonging to some local algebra $M_{[-p,p+1]}$. Notice that, by means of ω and $\mathcal{X}$ we can define a $m\times m$ density matrix $\rho \left[\mathcal{X}\right]$ with entries

$${\rho }_{ij}\left[\mathcal{X}\right]=\omega \left(X_j^{†}{X}_i\right)=\mathrm{Tr}\left({\rho }^{\left(2p\right)}{X}_j^{†}{X}_i\right)$$

(19)

and von Neumann entropy

$$S\left(\rho \right[\mathcal{X}\left]\right)=-\mathrm{Tr}\rho \left[\mathcal{X}\right]log\rho \left[\mathcal{X}\right]$$

(20)

In order to introduce the dynamics into the game, we let the partitions of unit transform under the action of the dynamical map Θ in (6),

$${\Theta }^{\ell }\left[\mathcal{X}\right]={\left\{{\Theta }^{\ell }\left[X_i\right]\right\}}_{i=1}^m$$

(21)

Then, we refine the partitions of unit from $\ell =0$ to $\ell =n-1$ as follows

$${\mathcal{X}}^{\left(n\right)}=\left\{X_{i^{\left(n\right)}}\right\},X_{i^{\left(n\right)}}={\Theta }^{(n-1)}\left[X_{i_{n-1}}\right]\cdots \Theta \left[X_{i_1}\right]X_{i_0},i^{\left(n\right)}=i_0{i}_1\dots i_{n-1}$$

(22)

with $i^{\left(n\right)}$ an m-nary string in ${\Omega }_m^{\left(n\right)}$. The refined sets ${\mathcal{X}}^{\left(n\right)}$ are still partitions of unit according to (18); one can thus associate to them density matrices $\rho \left[{\mathcal{X}}^{\left(n\right)}\right]$ acting on ${\mathbb{C}}^{m^n}$ with entries as in (19) and von Neumann entropies $S\left[{\mathcal{X}}^{\left(n\right)}\right]$ as in (20).

Notice the analogy with using a partition of phase-space to associate a symbolic model to a classical dynamical system; here, the choice of a partition of unit $\mathcal{X}$ allows to describe the quantum triple $({\mathcal{M}}_2,\omega ,\Theta )$ via a quantum symbolic model consisting of the family of density matrices $\rho \left[{\mathcal{X}}^{\left(n\right)}\right]$. The corresponding entropy rate is defined by

$$h_{\omega }^{AF}(\Theta ,\mathcal{X})=\underset{n\to \infty }{lim\; sup}\frac{1}{n}S\left[{\mathcal{X}}^{\left(n\right)}\right]$$

(23)

The Alicki–Fannes entropy of $({\mathcal{M}}_2,\omega ,\Theta )$ is then defined by

$$h_{\omega }^{AF}(\Theta )=\underset{\mathcal{X}}{sup}{h}_{\omega }^{AF}(\Theta ,\mathcal{X})$$

(24)

as the supremum over all possible finite partitions $\mathcal{X}$ of unit by local operators of the quantum spin chain.

Remark 1. The lim sup in (23) has to be used for the sequence of density matrices $\rho \left[{\mathcal{X}}^{\left(n\right)}\right]$ is not a stationary one [3,18]. In fact, while consistency holds as tracing $\rho \left[{\mathcal{X}}^{\left(n\right)}\right]$ over the n-th factor yields the density matrix corresponding to the first $n-1$ factors, ${\mathrm{Tr}}_n\rho \left[{\mathcal{X}}^{\left(n\right)}\right]=\rho \left[{\mathcal{X}}^{(n-1)}\right]$, stationarity does not. Indeed, in general, ${\mathrm{Tr}}_1\rho \left[{\mathcal{X}}^{\left(n\right)}\right]\ne \rho \left[{\mathcal{X}}^{(n-1)}\right]$. Thence, the density matrix for the local algebra $M_{p,q}$ corresponding to sites from p to q in line of principle depends on the starting factor $M_2\left(\mathbb{C}\right)$ at site p.

As a concrete example consider a set of 4 matrix units $U_{ij}\in M_2\left(\mathbb{C}\right)$ such that $U_{ij}^{†}=U_{ji}$, $U_{ij}{U}_{k\ell }={\delta }_{jk}{U}_{i\ell }$ and ${\sum }_{i=1}^2{U}_{ii}=1$. Dividing them by $\sqrt{2}$ one gets a partition of unit

$$\mathcal{U}={\left\{\frac{U_{ij}}{\sqrt{2}}\right\}}_{i,j=1,2}\in M_2\left(\mathbb{C}\right)$$

the simplest choice being

$$U_{11}=\left(\begin{array}{cc}1& 0\\ 0& 0\end{array}\right),U_{22}=\left(\begin{array}{cc}0& 0\\ 0& 1\end{array}\right),U_{12}=U_{21}^{†}=\left(\begin{array}{cc}0& 1\\ 0& 0\end{array}\right)$$

The refined partition that results after n applications of the right shift is

$${\mathcal{U}}^{\left(n\right)}=\left\{\frac{U_{i^{\left(n\right)}{j}^{\left(n\right)}}}{2^{n/2}}\right\},U_{i^{\left(n\right)}{j}^{\left(n\right)}}=U_{i_0{j}_0}\otimes U_{i_1{j}_1}\otimes \cdots U_{i_{n-1}{j}_{n-1}}\in M_2^{\otimes n}\left(\mathbb{C}\right)=M_{[0,n-1]}$$

(25)

The associated density matrices $\rho \left[{\mathcal{U}}^{\left(n\right)}\right]\in M_{4^n}\left(\mathbb{C}\right)$ have entries and von Neumann entropy given by

$$\begin{array}{ccc}\hfill \frac{1}{2^n}\mathrm{Tr}\left({\rho }^{\left(n\right)}{U}_{i^{\left(n\right)}{j}^{\left(n\right)}}^{†}{U}_{k^{\left(n\right)}{\ell }^{\left(n\right)}}\right)& =& \frac{1}{2^n}\mathrm{Tr}\left({\rho }^{\left(n\right)}{U}_{j_0{i}_0}{U}_{k_0{\ell }_0}\otimes U_{j_1{i}_1}{U}_{k_1{\ell }_1}\otimes \cdots \right)\hfill \\ \mathrm{(26)}& & =& \frac{1}{2^n}\mathrm{Tr}\left({\rho }^{\left(n\right)}{\delta }_{i_0{k}_0}{U}_{j_0{\ell }_0}\otimes {\delta }_{i_1{k}_1}{U}_{j_1{\ell }_1}\otimes \cdots \right)=\frac{\mathbf{1}}{2^n}\otimes {\rho }^{\left(n\right)}\hfill \end{array}$$

$$\begin{array}{ccc}\hfill S\left(\rho \left[{\mathcal{U}}^{\left(n\right)}\right]\right)& =& S\left({\rho }^{\left(n\right)}\right)+n\hfill \end{array}$$

(27)

The last equality in (26) comes from the fact that $\mathrm{Tr}\left({\rho }^{\left(n\right)}{U}_{i^{\left(n\right)}{j}^{\left(n\right)}}\right)$ are the matrix elements of ${\rho }^{\left(n\right)}$ with respect to the orthonormal basis defined by the choice of matrix units. Then, entropy rate and Alicki–Fannes entropy are readily computed to be [3,18]

$$h_{\omega }^{AF}(\Theta )=h_{\omega }^{AF}(\Theta ,\mathcal{U})=\underset{n\to \infty }{lim\; sup}\frac{1}{n}S\left(\rho \left[{\mathcal{U}}^{\left(n\right)}\right]\right)=s\left(\omega \right)+1$$

(28)

Remark 2. With respect to the AF-quantum dynamical entropy, the quantum dynamical entropy introduced by Connes, Narnhofer and Thirring [2] has a more complicated construction essentially due to the fact that it is based on a classical symbolic modeling with superimposed quantum corrections [17,21]. Consider a quantum spin chain endowed with a translation invariant state with sufficiently fast decaying correlations, the simplest case being the tensor product of a same density matrix ρ, that is

$$\omega (A_1\otimes A_2\otimes \cdots A_n)=\prod _{\ell =1}^n\mathrm{Tr}\left(\rho A_{\ell }\right)$$

In such cases, the CNT-entropy of the shift equals the von Neumann entropy rate (7), that is

$$h_{\omega }^{CNT}(\Theta )=s\left(\omega \right)(=-\mathrm{Tr}\rho log\rho \text{in}\text{the}\text{product}\text{state}\text{case})$$

(29)

One then notices that the AF-entropy exceeds the CNT-entropy by $1=log2$ in the case of the shift on quantum spin chains. The origin of the difference lies in that the AF-entropy accounts for the disturbances brought about by the description of the quantum dynamics via a quantum symbolic model. Does this addition have an interpretation in terms of quantum algorithmic complexity and of which one among the many available on the market? In the following we shall seek answers to these questions. A preliminary step is to clarify that the extra term $1=log2$ is a consequence of having introduced the measurement process through the partitions of unit.

AF-Entropy: Operational Interpretation

As we have seen in the second section, in quantum mechanics generic measurement processes on a system in a state ρ lead to a modification of the state as in (3). Suppose

$$M_{2^n}\left(\mathbb{C}\right)\ni {\rho }^{\left(n\right)}=\sum _i{r}_i^{\left(n\right)}|r_i^{\left(n\right)}\rangle \langle r_i^{\left(n\right)}|$$

(30)

is the spectral decomposition of a local state for n qubits described by the local algebra $M_{[0,n-1]}$; any such mixed state can be purified, that is transformed into a projector, by coupling $M_{[0,n-1]}$ to itself and by doubling ${\rho }^{\left(n\right)}$ into

$${\mathbb{C}}^{4^n}\ni |\sqrt{{\rho }^{\left(n\right)}}\rangle =\sum _i\sqrt{r_i^{\left(n\right)}}|r_i^{\left(n\right)}\rangle \otimes |r_i^{\left(n\right)}\rangle$$

(31)

Given the refined partition of unit ${\mathcal{U}}^{\left(n\right)}$ in (25), one further amplifies the Hilbert space from ${\mathbb{C}}^{4^n}$ to ${\mathbb{C}}^{4^n}\otimes {\mathbb{C}}^{4^n}$ and constructs the following vector state

$${\mathbb{C}}^{4^n}\otimes {\mathbb{C}}^{4^n}\ni |\Psi \left[{\mathcal{U}}^{\left(n\right)}\right]\rangle =\sum _i\sum _{\left(k^{\left(n\right)}{\ell }^{\left(n\right)}\right)}\sqrt{r_i^{\left(n\right)}}{U}_{k^{\left(n\right)}{\ell }^{\left(n\right)}}|r_i^{\left(n\right)}\rangle \otimes |r_i^{\left(n\right)}\rangle \otimes |k^{\left(n\right)}{\ell }^{\left(n\right)}\rangle$$

(32)

where the vectors $|k^{\left(n\right)}{\ell }^{\left(n\right)}\rangle$ indexed by pairs of binary strings in ${\Omega }_2^{\left(n\right)}$ form an auxiliary orthonormal basis in ${\mathbb{C}}^{4^n}$ of cardinality $2^n\times 2^n$.

One thus sees that $|\Psi [{\mathcal{U}}^{\left(n\right)}]\rangle$ is the vector state of a three-partite system consisting of the n qubits, system I, a copy of the latter, system $II$, and a copy of the first two, system $III$. From the projection $P=|\Psi \left[{\mathcal{U}}^{\left(n\right)}\right]\rangle \langle \Psi \left[{\mathcal{U}}^{\left(n\right)}\right]|$, by tracing over the first two systems, respectively over the last one, one obtains the following marginal states on $M_{[0,n-1]}\otimes M_{[0,n-1]}$,

$$\begin{array}{ccc}\hfill {\mathrm{Tr}}_{I,II}\left(P\right)& =& \rho \left[{\mathcal{U}}^{\left(n\right)}\right]\hfill \end{array}$$

(33)

$$\begin{array}{ccc}\hfill {\mathrm{Tr}}_{III}\left(P\right)& =& \sum _{\left(k^{\left(n\right)}{\ell }^{\left(n\right)}\right)}{U}_{k^{\left(n\right)}{\ell }^{\left(n\right)}}\otimes 1|\sqrt{{\rho }^{\left(n\right)}}\rangle \langle \sqrt{{\rho }^{\left(n\right)}}|U_{k^{\left(n\right)}{\ell }^{\left(n\right)}}^{†}\otimes 1=R\left[{\mathcal{U}}^{\left(n\right)}\right]\hfill \end{array}$$

(34)

Since they are marginal density matrices of a pure state, they have the same von Neumann entropy

$$S\left(\rho \left[{\mathcal{U}}^{\left(n\right)}\right]\right)=S\left(R\left[{\mathcal{U}}^{\left(n\right)}\right]\right)=S\left({\rho }^{\left(n\right)}\right)+n.$$

Thence, the entropy associated to ω and to the partition of unit ${\mathcal{U}}^{\left(n\right)}$, that is $\rho \left[{\mathcal{U}}^{\left(n\right)}\right]$, is also the entropy of the state $R\left[{\mathcal{U}}^{\left(n\right)}\right]$ which results from the action of the POVM $\{U_{k^{\left(n\right)}{\ell }^{\left(n\right)}}^{†}\otimes 1\}$ on the purified state $|\sqrt{{\rho }^{\left(n\right)}}\rangle \langle \sqrt{{\rho }^{\left(n\right)}}|$.

5. Quantum Dynamical Entropies and Gács Complexity

In order to extend classical algorithmic complexity theory to the quantum setting, P. Gács [14] started from the notion of universal probability and its relation to algorithmic complexity embodied by (17). He introduced the notion of universal semi-density matrix; it goes as follows. First, one defines the elementary vectors as those n-qubit vector states $|\Psi \rangle \in {\mathbb{C}}^{2^n}$ that have a representation along a fixed orthonormal basis $\left\{\right|{\phi }_j\rangle {\}}_j$ in terms of computable coefficients that are algebraic numbers

$$|\Psi \rangle =\sum _j{C}_j^{\Psi }|{\phi }_j\rangle ,C_j^{\Psi }\text{algebraic}\text{numbers}$$

(35)

These elementary vectors can thus be encoded by finite binary strings,

$$|\Psi \rangle ⟷i_{\Psi }\in {\Omega }_2^{p}p<+\infty$$

(36)

and characterized by algorithmic complexities $K\left(i_{\Psi }\right)$ and universal probabilities $\mathbb{P}\left(i_{\Psi }\right)$. Then, one proceeds to construct the convex combination of all elementary projectors weighted by their universal probabilities:

$$\mathbb{D}=\sum _{\Psi elementary}\mathbb{P}\left(i_{\Psi }\right)|\Psi \rangle \langle \Psi |,D=\mathrm{Tr}\mathbb{D}=\sum _{\Psi elementary}\mathbb{P}\left(i_{\Psi }\right)\le 1$$

(37)

The latter inequality states that $\mathbb{D}$ is a semi-density matrix for it is not normalized; further, exactly as for the classical universal probability, $\mathbb{D}$ is universal among lower semi-computable semi-density matrices, those whose entries with respect to the fixed orthonormal basis can be approximated as much as one likes from below by computable complex numbers. Namely, given a lower semi-computable semi-density matrix $\rho \in {\mathbf{M}}_{[0,n-1]}$ there exists a constant $C\left(\rho \right)\ge 0$ such that

$$C\left(\rho \right)\rho \le \mathbb{D},C\left(\rho \right)=2^{-K\left(\rho \right)}$$

(38)

where the constant depends only on the classical algorithmic complexity of (the entries of) ρ.

It is suggestive then to introduce the quantum algorithmic complexity as an operator

$${\kappa }_q=-log\mathbb{D}$$

(39)

and to define the complexity of $|\psi \rangle \in {\mathbb{C}}^{2^n}$, called algorithmic entropy in [14] and referred to as Gács complexity in this paper, as the mean value of the operator complexity with respect to such a state:

$$\mathbf{GC}\left(\psi \right):=\langle \psi \left|{\kappa }_q\right|\psi \rangle$$

(40)

A remarkable and simple property that follows from such a definition is that any computable density matrix ρ has von Neumann entropy that coincides with the mean value with respect to ρ of the operator complexity:

$$S\left(\rho \right)\le S\left(\rho \right)-logD\le \mathrm{Tr}\left(\rho {\kappa }_q\right)\le S\left(\rho \right)-logC\left(\rho \right)=S\left(\rho \right)+K\left(\rho \right)$$

(41)

The first inequality follows from $D\le 1$, the second one is a consequence of the positivity of the relative entropy

$$S({\rho }_1,{\rho }_2)=\mathrm{Tr}\left({\rho }_1(log{\rho }_1-log{\rho }_2)\right)\ge 0$$

of any two density matrices ${\rho }_{1,2}$ when one chooses ${\rho }_1=\rho$ and [see (37)] ${\rho }_2=\mathbb{D}/D$. Finally, the third inequality comes from the universality of $\mathbb{D}$, that is from (38).

In the following, we shall consider states of varying number n of qubits: the parameter n will always be considered as an implicit parameter in all the occurrences of Gács complexity.

5.1. Gács Complexity and CNT-Entropy for Quantum Spin Chains

Consider a family of computable local states ${\rho }^{\left(n\right)}$ on $M_{[0,n-1]}$; the universal semi-density matrix ${\mathbb{D}}_n\in M_{[0,n-1]}$ is a $2^n\times 2^n$ matrix corresponding to the local sub-algebras; it gives rise to a Gács operator complexity ${\kappa }_q^{\left(n\right)}=-log{\mathbb{D}}_n$ for which

$$S\left({\rho }^{\left(n\right)}\right)\le \mathrm{Tr}\left({\rho }^{\left(n\right)}{\kappa }_q^{\left(n\right)}\right)\le S\left({\rho }^{\left(n\right)}\right)+K\left({\rho }^{\left(n\right)}\right)$$

(42)

Therefore, if ${\displaystyle \frac{K\left({\rho }^{\left(n\right)}\right)}{n}⟼0}$, a condition holding for computable local states of sufficient regularity, as for instance for the totally uncorrelated states ${\rho }^{\left(n\right)}={\rho }^{\otimes n}$, then

$$\frac{S\left({\rho }^{\left(n\right)}\right)}{n}\le \frac{\mathrm{Tr}\left({\rho }^{\left(n\right)}{\kappa }_q^{\left(n\right)}\right)}{n}\le \frac{S\left({\rho }^{\left(n\right)}\right)}{n}+\frac{K\left({\rho }^{\left(n\right)}\right)}{n}⟹\underset{n\to \infty }{lim}\frac{\mathrm{Tr}\left({\rho }^{\left(n\right)}{\kappa }_q^{\left(n\right)}\right)}{n}=s\left(\omega \right)$$

(43)

This equality establishes a relation between the von Neumann entropy rate for a quantum spin chain and the average Gács algorithmic entropy rate relative to the local density matrices giving rise to the global translation invariant state ω. However, comparing the above relation with Brudno’s relation (14), one sees that the latter is a stronger pointwise relation. In the quantum setting, one would like to show that, for sufficiently large n, $\mathbf{GC}\left(\psi \right)$ is close to $ns\left(\omega \right)$ for all states ψ that are, in some precise sense to be defined, typical for the state ω.

Remark 3. A quantum Brudno’s relation was proved in [16] for an ergodic quantum spin chain and the quantum complexity of a quantum state ψ, ${\mathbf{QC}}^{\delta }\left(\psi \right)$, introduced by [13,16] and defined by

$${\mathbf{QC}}^{\delta }\left(\psi \right)=min\left\{{\ell \left(\sigma \right)|\parallel |\psi \rangle \langle \psi |-M\left(\sigma \right)\parallel }_{tr}\le \delta \right\}$$

(44)

In the above expression,

• σ is any density matrix acting on the Hilbert space ${\displaystyle {\mathcal{H}}_{{[0,1]}^{*}}=\underset{n\to +\infty }{lim}\underset{k=0}{\overset{n}{⨁}}{\mathcal{H}}_k}$, where ${\mathcal{H}}_k={\mathbb{C}}^{\otimes k}$ is the Hilbert space of k qubits: ${\mathcal{H}}_{{[0,1]}^{*}}$ accommodates classical binary strings of arbitrary length as quantum states and makes meaningful referring to generic density matrices acting on it as quantum programs. Furthermore, these density matrices constitute a Banach space ${\mathcal{T}}_1^{+}\left({\mathcal{H}}_{{[0,1]}^{*}}\right)$ under the so-called trace-distance ${\parallel X\parallel }_{tr}=\frac{1}{2}\mathrm{Tr}\left(\sqrt{X^{†}X}\right)$.
• $\ell \left(\sigma \right)$ is the length of quantum programs and is defined by

  $$\ell \left(\sigma \right)=min\left\{n\in \mathbb{N}|\sigma \in {\mathcal{T}}_1^{+}\left({\mathcal{H}}_{\le n}\right)\right\}$$

  (45)

  with ${\mathcal{H}}_{\le n}={⨁}_{k=0}^n{\mathcal{H}}_k$.
• M is a quantum operation, that is a completely positive map from ${\mathcal{T}}_1^{+}\left({\mathcal{H}}_{{[0,1]}^{*}}\right)$ into itself: these maps are interpreted as Quantum Turing Machines (see [22] for a detailed mathematical characterization and a discussion of the halting time in the context of the quantum superposition principle).

The quantum Brudno relation involving the quantum complexity ${\mathbf{QC}}^{\delta }$ has the following form: for any given $\delta \ge 0$, there exists a sequence of projections $P_n\left(\delta \right)$ that are typical with respect to ω, namely such that ${lim}_{n\to +\infty }\omega \left(P_n\left(\delta \right)\right)=1$. Furthermore, choosing n large enough, one has

$$\frac{1}{n}{\mathbf{QC}}^{\delta }\left(\psi \right)\in \left(s\left(\omega \right)-\delta (2+\delta )s\left(\omega \right),s\left(\omega \right)+\delta \right)$$

(46)

for all vector states $|\psi \rangle$ such that $P_n\left(\delta \right)|\psi \rangle =|\psi \rangle$.

We now prove a similar relation for the Gács complexity. The clue is given by the following result in [14]: for any n-qubit state $\psi \in {\left({\mathbb{C}}^2\right)}^{\otimes n}$ and $\delta <1/2$, if ${\mathbf{QC}}^{\delta }\left(\psi \right)\le k$ then

$$\mathbf{GC}\left(\psi \right)\le k+K\left(k\right)+2n\delta +C$$

(47)

where C is a constant independent of ψ.

Let $k=\lceil {\mathbf{QC}}^{\delta }\left(\psi \right)\rceil$ be the smallest integer larger than ${\mathbf{QC}}^{\delta }\left(\psi \right)$ and choose $N_0\in \mathbb{N}$ such that

$$\frac{1}{n}\mathbf{GC}\left(\psi \right)-s\left(\omega \right)\le \frac{1}{n}{\mathbf{QC}}^{\delta }\left(\psi \right)-s\left(\omega \right)+3\delta \forall n\ge N_0$$

In turn, for all ψ in one of the typical subspaces projected out by $P_n\left(\delta \right)$ as specified in the previous remark, the relation (46) for ${\mathbf{QC}}^{\delta }\left(\psi \right)$ gives ${\displaystyle \frac{1}{n}\mathbf{GC}\left(\psi \right)-s\left(\omega \right)\le 4\delta }$. In order to show that, for n large enough

$$\left|\frac{1}{n}\mathbf{GC}\left(\psi \right)-s\left(\omega \right)\right|\le 4\delta$$

(48)

and hence a full quantum Brudno relation for the Gács complexity, we argue by contradiction.

Suppose that for any $N_0$ one can find $n\ge N_0$ such that ${\displaystyle \frac{1}{n}\mathbf{GC}\left(\psi \right)<s\left(\omega \right)-4\delta }$. The convexity of the function $logx$ yields [14] $\mathbf{GC}\left(\psi \right)\ge -log\left(\langle \psi \left|D_n\right|\psi \rangle \right)$. It thus follows that $\langle \psi |D_n|\psi \rangle >2^{-n\left(s\right(\omega )-4\delta )}$, whence, by taking the trace of $D_n$ with respect to the typical projection $P_n\left(\delta \right)$,

$$1\ge \mathrm{Tr}{\mathbb{D}}_n\ge \mathrm{Tr}\left(P_n\left(\delta \right){\mathbb{D}}_n\right)>\mathrm{Tr}\left(P_n\left(\delta \right)\right)2^{-n\left(s\right(\omega )-4\delta )}$$

(49)

The last step in the proof is based on the following result [23]: for an ergodic quantum spin chain with von Neumann entropy rate $s\left(\omega \right)$,

$$\begin{array}{ccc}\hfill & & \underset{n\to +\infty }{lim}\frac{1}{n}{\beta }_{ϵ,n}\left(\omega \right)=s\left(\omega \right)\hfill \end{array}$$

$$\begin{array}{ccc}& & {\beta }_{ϵ,n}\left(\omega \right)=min\left\{log\mathrm{Tr}\left(P\right)|P^{†}=P=P^2\in M_{[0,n-1]},\omega \left(P\right)\ge 1-ϵ\right\},\hfill \end{array}$$

(50)

for any $1>ϵ>0$. Roughly speaking, the dimension of typical subspaces grows like $2^{ns\left(\omega \right)}$. Thus, by choosing n large enough one can make $\mathrm{Tr}\left(P_n\left(\delta \right)\right)>2^{n\left(s\right(\omega )-3\delta )}$, hence obtaining a contradiction from inequality (49):

$$1\ge \mathrm{Tr}\left(P_n\left(\delta \right){\mathbb{D}}_n\right)>2^{n\left(s\right(\omega )-3\delta )}{2}^{-n\left(s\right(\omega )-4\delta )}=2^{n\delta }$$

5.2. Gács Complexity and AF-Entropy for Quantum Spin Chains

We now consider the Gács algorithmic entropy in relation to the AF-entropy that we have seen to amount to a quantum dynamical entropy that takes into account the measurement processes, these latter providing quantum symbolic models.

The partition of unit ${\mathcal{U}}^{\left(n\right)}\in {\mathbf{M}}_{[0,n-1]}$ is computable (all matrix elements are computable algebraic numbers) with respect to the fixed standard orthonormal basis. Given the computable local states ${\rho }^{\left(n\right)}$, construct the auxiliary states $R\left[{\mathcal{U}}^{\left(n\right)}\right]\in {\mathbf{M}}_{[0,n-1]}\otimes {\mathbf{M}}_{[0,n-1]}$ and the universal density matrix ${\tilde{\mathbb{D}}}_n\in {\mathbf{M}}_{[0,n-1]}\otimes {\mathbf{M}}_{[0,n-1]}$. Notice that, unlike ${\mathbb{D}}_n$, this matrix acts on the Hilbert space ${\mathbb{C}}^{4^n}$. The corresponding operator complexity ${\tilde{\kappa }}^{\left(n\right)}=-log{\tilde{\mathbb{D}}}_n$ is such that

$$S\left(R\left[{\mathcal{U}}^{\left(n\right)}\right]\right)\le \mathrm{Tr}\left(R\left[{\mathcal{U}}^{\left(n\right)}\right]{\tilde{\kappa }}_q^{\left(n\right)}\right)\le S\left(R\left[{\mathcal{U}}^{\left(n\right)}\right]\right)+K\left(R\left[{\mathcal{U}}^{\left(n\right)}\right]\right)$$

(51)

Thus, if ${\displaystyle \frac{K\left(R\left[{\mathcal{U}}^{\left(n\right)}\right]\right)}{n}⟼0}$, a condition also holding for sufficiently regular ${\rho }^{\left(n\right)}$ in view of the structure of the partitions of unit ${\mathcal{U}}^{\left(n\right)}$, one gets

$$\underset{n\to \infty }{lim\; sup}\frac{\mathrm{Tr}\left(R\left[{\mathcal{U}}^{\left(n\right)}\right]{\tilde{\kappa }}_q^{\left(n\right)}\right)}{n}=s\left(\omega \right)+1$$

(52)

Though this is not a quantum Brudno’s relation as in (48), it establishes a connection, not available so far, between the AF-entropy and the Gács complexity. For a point-wise relation between $n\left(s\right(\omega )+1)$ and $\langle \tilde{\psi }\left|{\tilde{\kappa }}_q^{\left(n\right)}\right|\tilde{\psi }\rangle$, one would need to define the notion of typicality of projectors in ${\mathbf{M}}_{[0,n-1]}\otimes {\mathbf{M}}_{[0,n-1]}$ with respect to the sequence of auxiliary states $R\left[{\mathcal{U}}^{\left(n\right)}\right]$ and to prove an estimate of their dimension along the line of (50).

6. Conclusions

In classical information theory and, more in general, for classical dynamical systems, Brudno’s theorem establishes a relation between the dynamical information rate of ergodic time-evolutions and the algorithmic complexity per unit time step of almost all trajectories. In quantum information theory, classical sources are replaced by quantum spin chains which represent an arena for putting to test the various non-commutative extensions of both the Kolmogorov–Sinai dynamical entropy and the Kolmogorov–Solomonoff–Chaitin algorithmic complexity and their possible relations. There is a relation between the von Neumann entropy rate of quantum spin chains and the Berthiaumme–van Dam–Laplante quantum algorithmic complexity rate for every pure state in typical subspaces with respect to ergodic shift-invariant states over the chain. As the von Neumann entropy rate coincides with the quantum dynamical entropy of the shift along the quantum spin chain as defined by Connes, Narnhofer and Thirring, the above relation can rightfully be considered as a quantum Brudno’s relation. No similar relations have so far been proved to exist among any of the other existing proposals. In this paper, in the case of quantum sources, we have proved a quantum Brudno relation between the quantum dynamical entropy proposed by Connes, Narnhofer and Thirring and the rate of the algorithmic entropy of Gács. In the case of the Alicki–Fannes entropy, a first step in setting a link between the latter and the Gács complexity rate has been provided. For a full quantum Brudno relation new tools have to be developed, as the quantum symbolic models behind the AF-construction are not even stationary and the techniques of ergodic quantum spin chains cannot be used directly. Furthermore, should one succeed in proving a relation to exist between the AF-entropy and the Gács algorithmic entropy rate for pure states in typical subspaces for quantum spin chains, the next step, also in the case of the CNT-entropy, would be to move on and consider more general ergodic quantum dynamical systems and face the problem of a full quantum Brudno’s theorem for non-trivial dynamics.