  Kolmogorov complexity is a measure of the information contained in a binary
string. We investigate here the notion of quantum Kolmogorov complexity, a
measure of the information required to describe a quantum state. We show that
for any definition of quantum Kolmogorov complexity measuring the number of
classical bits required to describe a pure quantum state, there exists a pure
n-qubit state which requires exponentially many bits of description. This is
shown by relating the classical communication complexity to the quantum
Kolmogorov complexity. Furthermore we give some examples of how quantum
Kolmogorov complexity can be applied to prove results in different fields, such
as quantum computation and thermodynamics, and we generalize it to the case of
mixed quantum states.
