Quantum Algorithmic Complexities and Entropy
Fabio Benatti · Open Systems & Information Dynamics · 2009
We review the basics of classical algorithmic complexity theory and two of its quantum extensions that have been prompted by the foreseeable existence of quantum computing devices. In particular, we will examine the relations between these extensions and the von Neumann entropy rate of generic quantum information sources of ergodic type.