# Is there an algorithm that can decide if a state is a mixed state or a pure state?

Given we are using the computational basis,is there a quantum algorithm that can decide if an arbitrary input state $$\vert A\rangle$$ ( using $$N$$ qubits) is a pure state or a mixed state? $$\vert A\rangle$$ is defined below. If such an algorithm exists what is its space complexity and time complexity?

Where the arbitrary state $$\vert A\rangle$$ is the state

$$\vert A\rangle=a(0)|0\rangle+a(1)|1\rangle+a(2)|2\rangle+\ldots+ a(-1+(2^N))|(-1+(2^N))\rangle$$

and, of course, the sum of squares of the amplitudes $$a(0),a(1),a(2),...,a(-1+(2^N))$$ is equal to $$1$$.

For the mixed or the pure state it is unknown which of the amplitudes are non zero; it is only known that $$1$$ non zero amplitude exists if $$\vert A\rangle$$ is a pure state; it is only known that more than $$1$$ non zero amplitude exists if $$\vert A\rangle$$ is a pure state. So if it is a pure state it means for some unknown $$i$$, $$a (i) =1$$ and all the other amplitudes in the state $$\vert A\rangle$$ have amplitude zero. A mixed state is any other state which is not a pure state. Note that we only have one state $$\vert A\rangle$$ and we are not given any copies of this state $$\vert A\rangle$$.

Update:Another very closely related question is, does an algorithm exist using the standard definition of a pure state (with the computational basis) in above question? (i.e. instead of $$a (i) =1$$ we have $$a (i) =c$$ where c is a complex number with magnitude 1)

• A pure state doesn't have to have only one coefficient 1 and the others zero. Any ket state is pure by definition
– glS
Jul 21 '21 at 10:36
• @glS Your comment is moot since the the basis to decompose the arbitrary input state A i s mentioned in the question Jul 21 '21 at 11:28
• ok, but you are asking, as far as I can tell, conditions under which $|A\rangle$ is pure. A ket state $|A\rangle$ is always pure, by definition.
– glS
Jul 21 '21 at 11:31
• @glS ok, I think it is clear enough that it is implied computational basis is used in the question. But anyway, I have updated the question by adding a few words to it, regarding your comments implying I did not write out we are using computational basis in words; as far as I can tell your comment implies that. So the question now states I am using the computational basis in words. Jul 22 '21 at 17:44
• whether you are "using the computational basis" or not is irrelevant here. A ket state is pure, so it doesn't make sense to ask when it is. Your statement about "it is only known that 1 non zero amplitude exist" makes sense if you assume that the given state is a computational basis state, fine, but that doesn't change that the state $|A\rangle$ is pure regardless of the values of the coefficients
– glS
Jul 22 '21 at 17:46

No, there is no quantum algorithm $$\mathcal{D}$$ that given a single copy of a quantum state $$\rho$$ as input determines whether $$\rho$$ is pure or mixed.

## Quantum mechanics argument

By the principle of deferred measurement, we can assume that $$\mathcal{D}$$ corresponds to a unitary $$U$$ followed by a measurement of an observable $$M$$. Suppose that the eigenvalue $$\lambda$$ of $$M$$, with associated eigenspace projector $$P_\lambda$$, is meant to signify that the input is pure. Further, assume that on pure input the last step in $$\mathcal{D}$$, i.e. the measurement of $$M$$, yields $$\lambda$$ with probability no less than $$p$$ (if $$\mathcal{D}$$ is deterministic then $$p=1$$). Then

$$\mathrm{tr}(U|\psi\rangle\langle \psi|U^\dagger P_\lambda) \ge p$$

for all pure states $$|\psi\rangle$$. Now, consider a mixed state

$$\rho = \sum_kp_k|k\rangle\langle k|.$$

By linearity, we see that

$$\mathrm{tr}(U\rho U^\dagger P_\lambda) \ge p.$$

Moreover, since the set of pure states is contained in the closure of the set of mixed states, by continuity we also get the converse. This means that $$\mathcal{D}$$ fails to distinguish between pure and mixed states.

## Computer science argument

We will show that the ability to distinguish pure and mixed states confers the ability to solve all problems in NP. This means that, from computer science perspective, it is highly unlikely that a quantum algorithm for the task exists.

To that end, we will show how to use $$\mathcal{D}$$ to solve SAT. Let $$\phi$$ be a boolean formula with $$n$$ variables $$x_1, \dots, x_n$$. There is a circuit $$U_\phi$$ with size polynomial in the size of $$\phi$$ such that

$$U_\phi|b_1\dots b_n\rangle|y\rangle = |b_1\dots b_n\rangle|y\oplus \phi(b_1,\dots,b_n)\rangle$$

for $$b_i\in\{0, 1\}$$ with $$i=1,\dots,n$$.

In order to determine whether $$\phi$$ is satisfiable, we proceed as follows. Prepare $$n+1$$ qubits in the $$|0\rangle$$ state. Apply Hadamard to qubits $$1$$ through $$n$$. Apply $$U_\phi$$ to all qubits.

At this point the $$n+1$$ qubits are in the pure state

$$|\psi\rangle = |\psi_0\rangle|0\rangle + |\psi_1\rangle|1\rangle\tag1$$

where $$|\psi_0\rangle$$ is the unnormalized superposition of bitstrings corresponding to the unsatisfying assignments of $$\phi$$ and $$|\psi_1\rangle$$ is the unnormalized superposition of bitstrings corresponding to the satisfying assignments of $$\phi$$. If $$\phi$$ has both satisfying and unsatisfying assignments then both terms in $$(1)$$ are non-zero and $$|\psi\rangle$$ is entangled. Therefore, the state $$\rho=\mathrm{tr}_{n+1}(|\psi\rangle\langle\psi|)$$ of qubits $$1$$ through $$n$$ is mixed. On the other hand, if $$\phi$$ is constant, i.e. either all its assignments are satisfying or all its assignments are unsatisfying then one of the terms in $$(1)$$ is zero and $$\psi$$ is separable. Consequently, $$\rho$$ is pure.

Therefore, as the final step of our SAT solver we discard the qubit $$n+1$$ and feed qubits $$1$$ through $$n$$ to $$\mathcal{D}$$. If $$\mathcal{D}$$ indicates that the state $$\rho$$ of qubits $$1$$ through $$n$$ is mixed then $$\phi$$ is satisfiable. Otherwise, $$\phi$$ is constant and we compute $$\phi(0, \dots, 0)$$ to check whether $$x_1=\dots=x_n=0$$ is a satisfying assignment. If it is, then $$\phi$$ is satisfiable. Otherwise, it is unsatisfiable.

Finally, SAT is NP-complete, so if $$\mathcal{D}$$ exists then all problems in NP can be solved on a quantum computer.

## Intuition

The intuition behind the arguments above is that the set of pure states is a "razor thin" subset of the set of all states. More formally, it is a zero measure subset of the set of all states. The ability to determine membership in such a set is akin to a measurement of infinite precision and therefore unphysical.

• But how do you explain for pure states $Tr(\rho^2)=1$ and for mixed states $Tr(\rho^2)<1$ and use this fact to judge? Jul 21 '21 at 0:11
• Okay, seems his definition of the pure state is some different from the standard one. Jul 21 '21 at 0:14
• We need multiple copies of $\rho$ to evaluate $\mathrm{tr}(\rho^2)$. Since the question refers to a quantum algorithm where $\rho$ is the input, I'm assuming that here we only have access to a single copy. In fact, the OP added clarification to this effect. Jul 21 '21 at 0:15
• @narip I updated the question regarding your comment Jul 21 '21 at 0:48
• @Learner Note that the quantum mechanics argument applies to both cases. If we consider all pure states, then the argument above works as stated. If we restrict our attention to the states in the computational basis (or any other basis), then the argument still works, because that's all you need to express a mixed state $\rho$ in the form $\sum_k p_k|k\rangle\langle k|$. Jul 21 '21 at 1:13