Maximally mixed state as input of a quantum circuit

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.

• sigma cannot be entangled and maximally mixed at the same time. Also could you clarify what is actually your question. Apr 20, 2017 at 13:18
• 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. Apr 20, 2017 at 14:14

You can always choose orthonormal basis in which $\sigma$ is diagonal and takes the form, $$\sigma=\sum_{l}\sigma_l |\psi_l\rangle\langle\psi_l|$$ 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 $$P(1|\sigma)=\sum_{l} \sigma_l P(1|\psi_l)\leq \sum_{l} P(1|\psi_l)$$
Now with the same reasoning applied to maximally mixed state $\rho$ we get, $$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)$$
If we know that $P(1|\sigma)\geq\frac{2}{3}$ we get that $P(1|\rho)\geq\frac{2}{3N}$