# Efficiently distinguishing mixed quantum states?

Assume we know two different mixed states, p and q, and an efficient (quantum) algorithm for creating such two. Does it follow that there exists a computationally efficient method/measurement for optimally(that is, according to the trace norm distance) distinguishing between the two?

-
For one copy of each state you can in principle distinguish between them, but I don't know if it can be done efficiently. Since you have the circuit you may want to make many copies of the states, in which case arxiv.org/abs/quant-ph/0610027 is relevant. This gives hope even when the one-copy case has low trace distance. They claim that the collective measurement is efficient (on the bottom of page 2) but I don't know whether this assumes an efficient measurement for the one-copy case. – Dan Stahlke Aug 21 '12 at 12:39
Given two states is straight forward to figure out how well to distinguish them (trace norm distance), but yeah, I'm lost on efficency. I cannot really make many copies, as it is one specific state I'm given, that I want to check. Maybe being concrete will help my question, I want to make sure that I have the following state (or something very close): \rho = \sum_{r_0,r_1 \in {0,1}^n} |\psi_{r_0,r_1}> <\psi_{r_0,r_1}| where |\psi_{r_0,r_1}> = |(|0>|r_0> + |1>|r_1>) I know how to create this mixed state, but how do I, efficiently check it? – Thomas Hansen Aug 21 '12 at 13:41