  This paper explores the problem of quantum measurement complexity. In
computability theory, the complexity of a problem is determined by how long it
takes an effective algorithm to solve it. This complexity may be compared to
the difficulty for a hypothetical oracle machine, the output of which may be
verified by a computable function but cannot be simulated on a physical
machine. We define a quantum oracle machine for measurements as one that can
determine the state by examining a single copy. The complexity of measurement
for a realizable machine will then be respect to the number of copies of the
state that needs to be examined. A quantum oracle cannot perform simultaneous
exact measurement of conjugate variables, although approximate measurement may
be performed as circumscribed by the Heisenberg uncertainty relations. When
considering the measurement of a variable, there might be residual uncertainty
if the number of copies of the variable is limited. Specifically, we examine
the quantum measurement complexity of linear polarization of photons that is
used in several quantum cryptography schemes and we present a relation using
information theoretic arguments. The idea of quantum measurement complexity is
likely to find uses in measurements in biological systems.
