The question
Consider the following linear, trace preserving quantum map over $d \times d$ quantum states $\sigma$,
$$\Phi(\sigma) = \Pi_R \sigma \Pi_R + (1 – \text{Tr}(\Pi_R \sigma)) \frac{\Pi_R}{R}$$
for $\Pi_R$ a rank $R$ projector. This is a simplified version of the quantum channel used in Schumacher's compression protocol (see Eq. 18.9 on page 525 of Wilde's "From Classical to Quantum Shannon Theory" v8). Thus, this map must actually be a quantum channel which is completely positive and trace preserving (CPTP). For my pedagogy, I wanted to actually show complete positivity explicitly.
As Norbert Schuch points out, it is clearly also CP by simple physical interpretation. I've now verified this (below). But I would also like to prove it from the Choi matrix construction. In attempting to do so on a qudit example, I ended up showing (incorrectly) that the Choi matrix has negative eigenvalues. What did I do wrong?
Showing map is CPTP by composition of CPTP maps
Since the composition of CPTP maps is also CPTP, we can prove $\Phi$ is CPTP by constructing it from known CPTP maps. In short, we can build $\Phi$ up from (a) a quantum instrument (see Section 4.6.8 in Wilde), (b) a measurement, and (c) the replacement channel.
For (a), we consider two completely positive trace-non increasing maps $\Lambda_1(\rho) = \Pi_R \rho \Pi_R$ and $\Lambda_2(\rho) = (I – \Pi_R) \rho (I – \Pi_R)$ (just two POVM elements). Then the quantum instrument is given by $\Lambda(\rho) = \Lambda_1(\rho) \otimes |0\rangle \langle 0 | + \Lambda_2(\rho) \otimes |1 \rangle \langle 1|$. For (b), we simply measure the ancilla system which returns $0$ with probability $p_0 = \text{Tr}[\Pi_R \rho]$ and $1$ with probability $p_1 = \text{Tr}[(I – \Pi_R) \rho]$. If the ancilla reads $0$, we do nothing to the system, and if it reads $1$, we apply the replacement channel to $\Pi_R / R$. This leads to a final state $(p_0 \Pi_R \rho \Pi_R) / p_0 + p_1 (\Pi_R / R)$ which is the desired channel $\Phi$.
Incorrect Choi matrix calculation for a specific qudit example
The corresponding Choi matrix is given by
$$\chi = \sum_{i=0,j=0}^{d-1} |i\rangle \langle j| \otimes \Phi(|i\rangle \langle j|)$$
which we can calculate readily since
$$ \Phi(|i \rangle \langle j |) =
\begin{cases}
|i \rangle \langle j| + (1 – \delta_{i,j}) (\Pi_R / R) & \Pi_R |i \rangle = |i \rangle \ \& \ \Pi_R |j \rangle = |j \rangle \\
\Pi_R / R & \text{otherwise}.
\end{cases} $$
As a special case, consider $d = 3, R = 2, \Pi_2 = |0\rangle\langle0| + |1 \rangle \langle 1|$. In this case, the Choi (block) matrix is of the form
$$
\chi_{(d=3,R=2)} =
\begin{pmatrix}
|0 \rangle \langle 0 | & |0 \rangle \langle 1 | + \Pi_2 / 2 & \Pi_2 / 2 \\
%—–
|1 \rangle \langle 0 | + \Pi_2 / 2 & |1 \rangle \langle 1 | & \Pi_2 / 2 \\
\Pi_2 / 2 & \Pi_2 / 2 & \Pi_2 / 2
\end{pmatrix}
$$
with spectrum $\{2.32288, 1.20711, -0.5, 0.5, -0.322876, -0.207107, 0., 0., 0.\}$ which contains several negative values and is hence not positive semi-definite. This suggests $\Phi$ is not CP in general which contradicts the earlier calculation. What is wrong with my Choi matrix calculation?
Best Answer
Your map is not CPTP. In fact, it is not even linear, so it is unclear what the Choi state even means.
The correct map would be $$\Phi(\sigma) = \Pi_R \sigma \Pi_R + (\mathrm{tr}(\sigma) - \mathrm{tr}(\Pi_R \sigma)) \frac{\Pi_R}{R}$$ or, by thinking of a two-outcome POVM $\{\Pi_R,I-\Pi_R\}$, $$\Phi(\sigma) = \Pi_R \sigma \Pi_R + \mathrm{tr}((I-\Pi_R) \sigma) \frac{\Pi_R}{R}\ .$$ (This also matches what Wilde writes.)
Note that this map will no longer have the $\Pi_2/2$ on the off-diagonal in the Choi state (which in its current form indeed does not match the intuition for what the channel is supposed to do: Why would it output $\Pi_R/2$ on an off-diagonal input element?).