  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$.
