We define the quantum Kolmogorov complexity of a qubit string X as the length of the shortest quantum input to a universal quantum Turing machine that produces X with high fidelity.
We argue that this is a natural and robust measure of the quantum information contained in a quantum string. It is invariant under the choice of the underlying quantum Turing machine. As in the classical case, we can show that there exist quantum incompressible strings. It is also closely related to quantum information theory. Finally, it exhibits typical quantum behavior: as a result of the no-cloning property of quantum mechanics, the classical statement: "for all x, C(x^m)<= C(x) + O(log m)" does not hold for this definition of quantum Kolmogorov complexity.