Prefix-free quantum Kolmogorov complexity
share
We introduce quantum-K (QK), a measure of the descriptive complexity of density matrices using classical prefix-free Turing machines and show that the initial segments of weak Solovay random and quantum Schnorr random states are incompressible in the sense of QK. Many properties enjoyed by prefix-free Kolmogorov complexity (K) have analogous versions for QK; notably a counting condition. Several connections between Solovay randomness and K, including the Chaitin type characterization of Solovay randomness, carry over to those between weak Solovay randomness and QK. We work towards a Levin-Schnorr type characterization of weak Solovay randomness in terms of QK. Schnorr randomness has a Levin-Schnorr characterization using K_C; a version of K using a computable measure machine, C. We similarly define QK_C, a version of QK. Quantum Schnorr randomness is shown to have a Levin-Schnorr and a Chaitin type characterization using QK_C. The latter implies a Chaitin type characterization of classical Schnorr randomness using K_C.
READ FULL TEXT