Author: Peter Gacs

Abstract:

We extend algorithmic information theory to quantum mechanics.  Due to difficulties and ambiguities in finding an appropriate notion of description complexity for quantum states, we take the construction of a universal semicomputable density matrix (``apriori probability'') as a starting point, and define complexity as its negative logarithm.

A number of properties of Kolmogorov complexity extend to the new domain. Approximately, a quantum state is simple if it is within a small distance from a low-dimensional subspace of low Kolmogorov complexity.  The von Neumann entropy of a computable density matrix is within an additive constant from the average complexity.  Some of the theory of randomness translates to the new domain, but new questions arise due to non-commutativity.  The problem of cloning in terms of the new complexity leads to an algebraic problem that we formulate.

Our complexity is smaller than the one defined by Vitanyi.  The latter is sometimes almost 2n for an n-qubit object; ours is at most n.