In this paper we give a definition for quantum Kolmogorov complexity. In the classical setting, the Kolmogorov complexity of a string is the length of the shortest program that can produce this string as its output. It is a measure of the amount of innate randomness (or information) contained in the string. We define the quantum Kolmogorov complexity of a qubit string as the length of the shortest quantum input to a universal quantum Turing machine that produces the initial qubit string with high fidelity. The definition of P. Vitanyi (2000) measures the amount of classical information, whereas we consider the amount of quantum information in a qubit string. We argue that our definition is natural and is an accurate representation of the amount of quantum information contained in a quantum state.

We propose a method for the stabilization of quantum computations (including quantum state storage). The method is based on the operation of projection into $\cal SYM$, the symmetric subspace of the full state space of R redundant copies of the computer. We describe an efficient algorithm and quantum network effecting $\cal SYM$--projection and discuss the stabilizing effect of the proposed method in the context of unitary errors generated by hardware imprecision, and nonunitary errors arising from external environmental interaction. Finally, limitations of the method are discussed.