Quantum Dynamical Entropies and G'acs Algorithmic Entropy.

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'acs 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. [ABSTRACT FROM AUTHOR]