Entanglement and correlations in mixed-state quantum computation

A very intriguing model of mixed-state quantum computation is the `power of one qubit' [E. Knill and R. Laflamme, Phys. Rev. Lett 81, 5672 (1998)], which has one pure qubit and n qubits in the completely mixed state. This model is known to evaluate the normalized trace of a unitary matrix with fixed accuracy efficiently, and offers an exponential speed-up over the best known classical algorithm. We show that this model involves entangled states. We also show that, on one hand, these states have no more than a constant amount of entanglement (as measured by the negativity), while on the other, they have an exponentially high operator Schmidt rank. Since quantum systems with limited Schmidt rank are known to be simulatable classically in an efficient manner, this suggests that the advantage of mixed-state quantum computation may stem not from the amount of entanglement but the degree of correlations (as quantified by the operator Schmidt rank) the system possesses.