Are there quantum algorithms which initial state is a mixed one?

Question

In this answer, it is stated that it is not yet known how to efficiently classically simulate separable mixed states, a statement supported in a comment to this answer.

However, I can't imagine an algorithm which initial state is mixed and would offer an advantage, computationally speaking, w.r.t. an algorithm starting in a pure state.

For instance, let us assume that the algorithm starts in the state: $$\rho=p_i\sum_i\left|\psi_i\middle\rangle\middle\langle\psi_i\right|$$ with each $\left|\psi_i\middle\rangle\middle\langle\psi_i\right|$ being a pure state. If one sees this state as "being in state $\left|\psi_i\middle\rangle\middle\langle\psi_i\right|$ with probability $p_i$", then it is beneficial to know on which system the algorithm will be applied. Thus, an algorithm starting in state $\left|\psi_i\middle\rangle\middle\langle\psi_i\right|$ while being sure that this state is actually this initial state would always yield better results than the one which doesn't know for sure what its initial state is. In cryptographic terms, the latter can perfectly simulate the former.

Is this reasoning wrong? If it is, what is an example of an algorithm which offers computational advantage while starting in a mixed state when compared to any other starting with a pure state? Or if there isn't, why do we care about simulating mixed states in the first place? Can't we just say "Sure, we don't know how to simulate them, but there is no need to do so in the first place"?

Answer 1

The complexity class DQC1 is defined as the class quantum circuits can compute with only 1 clean qubit (prepared in a pure state initially) and $N$ other "dirty" qubits (prepared in the completely mixed state).

It actually forms a nice class of problems that includes approximating the Jones polynomial, something that is believed to be hard for classical computers.

I guess digging into how the DQC1 algorithm makes use of the mixed states would answer your question.