  Does the notion of a quantum randomized or nondeterministic algorithm make
sense, and if so, does quantum randomness or nondeterminism add power? Although
reasonable quantum random sources do not add computational power, the
discussion of quantum randomness naturally leads to several definitions of the
complexity of quantum states. Unlike classical string complexity, both
deterministic and nondeterministic quantum state complexities are interesting.
A notion of \emph{total quantum nondeterminism} is introduced for decision
problems. This notion may be a proper extension of classical nondeterminism.
