  In standard quantum computation, the initial state is pure and the answer is
determined by making a measurement of some of the bits in the computational
basis. What can be accomplished if the initial state is a highly mixed state
and the answer is determined by measuring the expectation of $\sigma_z$ on the
first bit with bounded sensitivity? This is the situation in high temperature
ensemble quantum computation. We show that in this model it is possible to
perform interesting physics simulations which have no known efficient classical
algorithms, even though the model is less powerful then standard quantum
computing in the presence of oracles.
