Given a Hilbert space $\mathcal{H}_N$, a state $\rho$ is a maximally mixed state if it can be written as $\rho = \frac{1}{N} \sum_{i=1}^N |b_i\rangle \langle b_i |$ for some (any in fact) orthonormal basis $\{b_i\}$ of $\mathcal{H}_N$.

Consider now any density matrix $\sigma$, representing some quantum mixed state. Assume you have a quantum circuit that outputs 1 with probability $\geq 2/3$ on input $\sigma$. I have seen some proofs in quantum computing in which the input of the circuit is set to the maximally mixed state $\rho$ instead, and then the probability to output 1 is said to be $\geq 2/3 \cdot 1/N$. See this paper for instance (section 6, page 15, proof of theorem 20).

I agree that if $\sigma$ is a pure state $\sigma = |\psi \rangle \langle \psi |$, then we can find other vectors $|b'_2\rangle, \dots, |b'_N\rangle$ such that $\{|\psi\rangle,|b'_2\rangle, \dots, |b'_N\rangle\}$ is an orthonormal basis of $\mathcal{H}_N$. Thus, the maximally mixed state can be written as $\rho = \frac{1}{N} \left(\sigma + \sum_{i=2}^N |b'_i\rangle \langle b'_i |\right)$, and we indeed get $\sigma$ with probability $1/N$ if the input of our circuit is $\rho$ (thus the probability of having $1$ is $\geq 2/3 \cdot 1/N$). However, I don't know how to prove it when $\sigma$ is mixed.

  • 1
    $\begingroup$ sigma cannot be entangled and maximally mixed at the same time. Also could you clarify what is actually your question. $\endgroup$
    – lalala
    Apr 20, 2017 at 13:18
  • $\begingroup$ I didn't say that $\sigma$ was maximally mixed (it is $\rho$). However, I made a mistake at the end when I said "$\sigma$ is entangled" (it is "$\sigma$ is mixed"). Regarding a clarification, I don't know what to say more... I've described an argument that is used in many proofs, and that I don't understand (except when $\sigma$ is pure). So my question is why is this argument true. $\endgroup$ Apr 20, 2017 at 14:14

1 Answer 1


You can always choose orthonormal basis in which $\sigma$ is diagonal and takes the form, \begin{equation} \sigma=\sum_{l}\sigma_l |\psi_l\rangle\langle\psi_l| \end{equation} with $0\leq\sigma_l\leq 1$ that can be interpreted as classical probability that the system is in the pure state $|\psi_l\rangle$. Then if the input $|\psi_l\rangle$ gives $1$ with probability $P(1|\psi_l)$ the probability of this outcome for the input $\sigma$ is given by \begin{equation} P(1|\sigma)=\sum_{l} \sigma_l P(1|\psi_l)\leq \sum_{l} P(1|\psi_l) \end{equation}

Now with the same reasoning applied to maximally mixed state $\rho$ we get, \begin{equation} P(1|\rho)=\sum_{l} \frac{1}{N} P(1|\psi_l)\geq \frac{1}{N}\sum_{l} \sigma_l P(1|\psi_l)=\frac{1}{N}P(1|\sigma) \end{equation}

If we know that $P(1|\sigma)\geq\frac{2}{3}$ we get that $P(1|\rho)\geq\frac{2}{3N}$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.