Power of One Bit of Quantum Information

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 σ_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 that have no known efficient classical algorithms, even though the model is less powerful than standard quantum computation in the presence of oracles.