Maximally mixed state as input of a quantum circuit

Question

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.

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}$