  The purpose of this thesis is to give a formal definition of quantum
Kolmogorov complexity (QC), and rigorous mathematical proofs of its basic
properties. The definition used here is similar to that by Berthiaume, van Dam,
and Laplante. It defines the QC of some indeterminate-length qubit string \rho
as the minimum base length of any quantum input which makes a quantum Turing
machine (QTM) halt and output \rho, up to some error tolerance.
  First, we prove that there is a QTM which is universal in the sense of input
base length. Furthermore, we show several general properties of QTMs, including
a result on mutually orthogonal ``halting spaces'', and a way to transform
every almost-halting input into a deterministically-halting input by adding at
most a constant number of qubits.
  Afterwards, we apply these results to QC. In particular, we show that QC is
invariant, incompressible, agrees with classical Kolmogorov complexity for
classical strings, and is closely related to von Neumann entropy for ergodic
quantum information sources.
