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

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"?

• How does your question fit into the one clean qubit model of computation? One pure qubit acting as a control for a unitary acting on a mixed state can store, in its amplitude, properties of the unitary that are classically intractable to learn… Oct 9, 2022 at 20:08
• @MarkS I was unaware of this model of computation. Gitef's answer also provided me with examples. Thanks to both! Oct 11, 2022 at 8:24

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).