Quantum Kolmogorov complexity

In this paper we give a definition for quantum Kolmogorov complexity. In th e 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 m easure of the amount of innate randomness (or information) contained in the string. We define the quantum Kolmogorov complexity of a qubit string as t he length of the shortest quantum input to a universal quantum Turing machi ne that produces the initial qubit string with high fidelity. The definitio n of P. Vitanyi (2001, IEEE Trans. Inform. Theory 47, 2464-2479) measures t he amount of classical information, whereas we consider the amount of quant um information in a qubit string. We argue that our definition is a natural and accurate representation of the amount of quantum information contained in a quantum state. Recently, P. Gacs (2001, J. Phys. A: Mathematical and General 34, 6859-6880) also proposed two measures of quantum algorithmic en tropy which are based on the existence of a universal semidensity matrix. T he latter definitions are related to Vitdanyi's and the one presented in th is article, respectively. (C) 2001 Academic Press.