Choi’s Complete-Positivity Criterion
Formal statement
Let \(\mathcal H_A\) and \(\mathcal H_B\) be finite-dimensional complex Hilbert spaces, and let
\[ \Phi:L(\mathcal H_A)\to L(\mathcal H_B) \]
be a linear map between operator spaces. Choose an orthonormal basis \(\{|i\rangle_A\}_{i=1}^{d_A}\) for \(\mathcal H_A\), and introduce a copy \(A'\) of the input system. Define the unnormalized maximally entangled vector
\[ |\Omega\rangle_{A'A} = \sum_{i=1}^{d_A}|i\rangle_{A'}|i\rangle_A. \]
The Choi matrix of \(\Phi\) is
\[ J(\Phi) = (I_{A'}\otimes\Phi)(|\Omega\rangle\langle\Omega|_{A'A}). \]
Equivalently,
\[ J(\Phi) = \sum_{i,j=1}^{d_A}|i\rangle\langle j|_{A'}\otimes \Phi(|i\rangle\langle j|)_B. \]
Choi’s complete-positivity criterion says
\[ \Phi\text{ is completely positive} \quad\Longleftrightarrow\quad J(\Phi)\ge 0. \]
Here \(J(\Phi)\ge0\) means that the Choi matrix is positive semidefinite as an operator on \(\mathcal H_{A'}\otimes\mathcal H_B\).
If \(\Phi\) is also trace preserving, then it is a quantum channel, and the additional trace-preservation condition is
\[ \operatorname{Tr}_B J(\Phi)=I_{A'}. \]
Thus, in the unnormalized Choi convention, a linear map is a quantum channel exactly when
\[ J(\Phi)\ge0, \qquad \operatorname{Tr}_B J(\Phi)=I_{A'}. \]
Some authors use the normalized maximally entangled state
\[ |\Phi^+\rangle=\frac1{\sqrt{d_A}}\sum_i |i\rangle_{A'}|i\rangle_A. \]
Then the normalized Choi state is
\[ \omega(\Phi) = (I_{A'}\otimes\Phi)(|\Phi^+\rangle\langle\Phi^+|) = \frac1{d_A}J(\Phi). \]
With this convention, trace preservation becomes
\[ \operatorname{Tr}_B\omega(\Phi)=\frac{I_{A'}}{d_A}. \]
The theorem itself is the same. Only the normalization changes.
The problem the theorem solves
A linear map can be positive without being physically valid as a quantum operation. Positivity means that if \(X\ge0\), then \(\Phi(X)\ge0\). But a real quantum system may be entangled with an external reference \(R\). Therefore, if \(\Phi\) is physically allowed on system \(A\), then
\[ I_R\otimes\Phi \]
must also preserve positivity for every possible reference system \(R\). This stronger condition is complete positivity.
At first sight, complete positivity looks difficult to check. It appears to require infinitely many tests, one for every reference dimension and every positive operator on \(R\otimes A\). Choi’s theorem says that in finite dimensions all of those tests reduce to one matrix test:
\[ J(\Phi) = (I\otimes\Phi)(|\Omega\rangle\langle\Omega|) \ge0. \]
The operational mental image is this: the maximally entangled vector \(|\Omega\rangle\) contains all input matrix elements coherently. If applying \(\Phi\) to half of this single maximally entangled operator gives a positive operator, then \(\Phi\) is safe to apply to half of every entangled state. That is the surprise and power of Choi’s criterion.
Proof: complete positivity implies Choi positivity
Assume first that \(\Phi\) is completely positive. By definition, for every reference system \(R\), the map
\[ I_R\otimes\Phi \]
sends positive semidefinite operators to positive semidefinite operators.
Take \(R=A'\). The operator
\[ |\Omega\rangle\langle\Omega|_{A'A} \]
is positive semidefinite because it is a rank-one positive operator. Therefore complete positivity gives
\[ (I_{A'}\otimes\Phi)(|\Omega\rangle\langle\Omega|) \ge0. \]
But this operator is exactly \(J(\Phi)\). Hence
\[ J(\Phi)\ge0. \]
This proves the easy direction.
Proof: Choi positivity implies complete positivity
Now assume
\[ J(\Phi)\ge0. \]
Because \(J(\Phi)\) is positive semidefinite, the spectral theorem allows us to write it as a sum of rank-one positive operators:
\[ J(\Phi)=\sum_k |v_k\rangle\langle v_k|_{A'B}. \]
The vectors \(|v_k\rangle\) may be chosen to absorb the positive eigenvalues. More explicitly, if
\[ J(\Phi)=\sum_k\lambda_k |w_k\rangle\langle w_k| \]
with \(\lambda_k>0\), then set
\[ |v_k\rangle=\sqrt{\lambda_k}|w_k\rangle. \]
Each vector \(|v_k\rangle\in\mathcal H_{A'}\otimes\mathcal H_B\) can be reshaped into an operator
\[ E_k:\mathcal H_A\to\mathcal H_B \]
by requiring
\[ |v_k\rangle = (I_{A'}\otimes E_k)|\Omega\rangle. \]
Equivalently, if
\[ |v_k\rangle = \sum_i |i\rangle_{A'}\otimes |b_{k,i}\rangle_B, \]
then define
\[ E_k|i\rangle_A=|b_{k,i}\rangle_B. \]
Now expand one rank-one term:
\[ |v_k\rangle\langle v_k| = \sum_{i,j}|i\rangle\langle j|_{A'}\otimes E_k|i\rangle\langle j|E_k^\dagger. \]
Therefore
\[ J(\Phi) = \sum_{i,j}|i\rangle\langle j|_{A'}\otimes \left(\sum_k E_k|i\rangle\langle j|E_k^\dagger\right). \]
But by definition of the Choi matrix,
\[ J(\Phi) = \sum_{i,j}|i\rangle\langle j|_{A'}\otimes\Phi(|i\rangle\langle j|). \]
Comparing the \((i,j)\)-blocks, we obtain
\[ \Phi(|i\rangle\langle j|) = \sum_k E_k|i\rangle\langle j|E_k^\dagger. \]
Since the matrix units \(|i\rangle\langle j|\) form a basis for \(L(\mathcal H_A)\), linearity gives
\[ \Phi(X)=\sum_k E_k X E_k^\dagger \]
for every operator \(X\in L(\mathcal H_A)\).
This is a Kraus representation. A map with a Kraus representation is completely positive, because for every reference system \(R\),
\[ (I_R\otimes\Phi)(Y) = \sum_k (I_R\otimes E_k)Y(I_R\otimes E_k^\dagger), \]
and this sends positive operators \(Y\ge0\) to positive operators. Therefore \(\Phi\) is completely positive.
Thus
\[ J(\Phi)\ge0 \quad\Longrightarrow\quad \Phi\text{ is completely positive}. \]
Combining both directions proves Choi’s criterion.
Why the proof is conceptually powerful
The proof reveals that the Choi matrix is not merely a diagnostic object. It is a compressed form of the Kraus representation. If
\[ J(\Phi)=\sum_k |v_k\rangle\langle v_k|, \]
then reshaping the vectors \(|v_k\rangle\) gives Kraus operators \(E_k\). Thus positivity of \(J(\Phi)\) is exactly the statement that the map can be written as
\[ \Phi(X)=\sum_kE_kXE_k^\dagger. \]
Complete positivity becomes ordinary positivity of one bipartite operator because the maximally entangled vector stores every input basis operator \(|i\rangle\langle j|\) at once. The diagonal parts \(|i\rangle\langle i|\) test what the map does to classical populations. The off-diagonal parts \(|i\rangle\langle j|\) test what the map does to coherences. The Choi matrix packages all of this into one object.
This is why the theorem is so useful in quantum information. To check whether a proposed linear transformation is a physically allowed quantum operation, we do not need to test every entangled input. We compute one matrix and check whether its eigenvalues are nonnegative.
Example 1: identity channel
Let
\[ \operatorname{id}(X)=X. \]
Then
\[ J(\operatorname{id}) = (I\otimes\operatorname{id})(|\Omega\rangle\langle\Omega|) = |\Omega\rangle\langle\Omega|. \]
This is positive semidefinite because it is a rank-one positive operator. Therefore the identity map is completely positive.
Operationally, this is obvious: doing nothing to a system remains valid even if the system is entangled with a reference. But the Choi matrix gives a structural picture. The identity channel preserves the maximally entangled state exactly. Its Choi matrix is pure and maximally entangled.
Example 2: a Kraus map automatically has a positive Choi matrix
Suppose
\[ \Phi(X)=\sum_k E_k X E_k^\dagger. \]
Then
\[ J(\Phi) = \sum_k (I\otimes E_k)|\Omega\rangle\langle\Omega|(I\otimes E_k^\dagger). \]
If we define
\[ |E_k\rangle\!\rangle=(I\otimes E_k)|\Omega\rangle, \]
then
\[ J(\Phi)=\sum_k |E_k\rangle\!\rangle\langle\!\langle E_k|. \]
This is manifestly positive semidefinite because it is a sum of positive rank-one operators.
For example, the qubit bit-flip channel
\[ \Phi_p(\rho)=(1-p)\rho+pX\rho X \]
has Kraus operators
\[ E_0=\sqrt{1-p}\,I, \qquad E_1=\sqrt p\,X. \]
Its Choi matrix is
\[ J(\Phi_p) = (1-p)|I\rangle\!\rangle\langle\!\langle I| + p|X\rangle\!\rangle\langle\!\langle X|, \]
which is positive semidefinite for \(0\le p\le1\). The theorem says this is exactly why the bit-flip channel is completely positive.
Example 3: the transpose map is positive but not completely positive
Define the transpose map
\[ T(X)=X^T \]
on a \(d\)-dimensional Hilbert space. This map is positive: if \(X\ge0\), then \(X^T\ge0\). However, it is not completely positive when \(d\ge2\).
Its Choi matrix is
\[ J(T) = \sum_{i,j}|i\rangle\langle j|\otimes T(|i\rangle\langle j|) = \sum_{i,j}|i\rangle\langle j|\otimes |j\rangle\langle i|. \]
This is the swap operator
\[ F=\sum_{i,j}|ij\rangle\langle ji|. \]
For two qubits, consider the antisymmetric state
\[ |\psi^-\rangle = \frac{|01\rangle-|10\rangle}{\sqrt2}. \]
The swap operator acts as
\[ F|\psi^-\rangle=-|\psi^-\rangle. \]
Therefore \(J(T)\) has a negative eigenvalue. Hence
\[ J(T)\not\ge0. \]
By Choi’s criterion, the transpose map is not completely positive.
This example is one of the most important uses of the theorem. It shows that ordinary positivity is not enough for physical quantum dynamics. A map may send every single-system density matrix to another density matrix, but still fail when applied to half of an entangled state.
Example 4: the reduction map
Another useful example is the reduction map
\[ R(X)=\operatorname{Tr}(X)I-X. \]
For a density operator \(\rho\), the operator \(R(\rho)=I-\rho\) is positive semidefinite, because all eigenvalues of \(\rho\) lie between \(0\) and \(1\). Thus \(R\) is positive on states.
But its Choi matrix is
\[ J(R)=I\otimes I-|\Omega\rangle\langle\Omega|. \]
The vector \(|\Omega\rangle\) has squared norm
\[ \langle\Omega|\Omega\rangle=d. \]
Therefore
\[ J(R)|\Omega\rangle=(1-d)|\Omega\rangle. \]
For \(d>1\), this eigenvalue is negative. Hence
\[ J(R)\not\ge0, \]
so the reduction map is not completely positive.
The lesson is the same as for the transpose map. Positivity on isolated states does not guarantee physical validity on entangled systems. Complete positivity is the condition that survives arbitrary extension by a reference system.
Example 5: trace preservation is a different test
Choi positivity checks complete positivity. It does not check trace preservation. To be a deterministic quantum channel, a map must also satisfy
\[ \operatorname{Tr}_B J(\Phi)=I_{A'}. \]
For example, take the completely positive map
\[ \Phi(X)=A X A^\dagger \]
with
\[ A=|0\rangle\langle0|. \]
Its Choi matrix is positive because it has the form
\[ J(\Phi)=|A\rangle\!\rangle\langle\!\langle A|. \]
But
\[ A^\dagger A=|0\rangle\langle0|\neq I. \]
So the map is not trace preserving. It represents the branch of a measurement corresponding to projection onto \(|0\rangle\), not a full deterministic channel.
This example prevents a common misunderstanding. Choi positivity says “this map is completely positive.” It does not by itself say “this map is a channel.” A channel must be completely positive and trace preserving.
How to use the criterion in practice
Suppose someone proposes a linear map \(\Phi\). To test whether it is completely positive, choose a basis \(\{|i\rangle\}\) for the input system and compute
\[ J(\Phi)=\sum_{i,j}|i\rangle\langle j|\otimes\Phi(|i\rangle\langle j|). \]
Then diagonalize \(J(\Phi)\). If every eigenvalue is nonnegative, the map is completely positive. If even one eigenvalue is negative, the map is not completely positive and therefore cannot represent a physical quantum operation on part of an arbitrary entangled system.
If the map is intended to be a channel, also compute
\[ \operatorname{Tr}_B J(\Phi). \]
The map is trace preserving exactly when this partial trace equals \(I_{A'}\).
If \(J(\Phi)\ge0\), the same diagonalization gives Kraus operators. Write
\[ J(\Phi)=\sum_k\lambda_k|w_k\rangle\langle w_k|, \qquad \lambda_k>0. \]
Then reshape
\[ |v_k\rangle=\sqrt{\lambda_k}|w_k\rangle \]
into an operator \(E_k\). The resulting operators satisfy
\[ \Phi(X)=\sum_kE_kXE_k^\dagger. \]
Thus the Choi criterion is not only a yes-or-no test. It also gives a constructive path from a linear map to a Kraus representation.
Common mistakes
A common mistake is to say that a positive map is automatically completely positive. The transpose map and the reduction map show that this is false. Complete positivity is stronger because it requires positivity after adding an arbitrary reference system.
Another common mistake is to confuse Choi positivity with trace preservation. The condition
\[ J(\Phi)\ge0 \]
means complete positivity. The condition
\[ \operatorname{Tr}_B J(\Phi)=I \]
means trace preservation. A physical deterministic quantum channel needs both.
A third mistake is to ignore the basis convention. The Choi matrix depends on the chosen input basis because \(|\Omega\rangle\) and the transpose operation depend on that basis. However, whether \(J(\Phi)\) is positive semidefinite does not depend on arbitrary physical choices; under a change of input basis, the Choi matrix changes by a corresponding unitary transformation. Positivity is preserved.
A fourth mistake is to mix normalized and unnormalized Choi conventions. With
\[ |\Omega\rangle=\sum_i|i\rangle|i\rangle, \]
a channel satisfies
\[ \operatorname{Tr}_B J(\Phi)=I. \]
With
\[ |\Phi^+\rangle=\frac1{\sqrt d}\sum_i|i\rangle|i\rangle, \]
the normalized Choi state satisfies
\[ \operatorname{Tr}_B\omega(\Phi)=\frac Id. \]
Many wrong factors of \(d\) come from mixing these two conventions.
Final mental image
Choi’s criterion says that complete positivity, which seems to be a condition about infinitely many possible reference systems, can be checked by a single finite-dimensional matrix:
\[ \Phi\text{ is completely positive} \quad\Longleftrightarrow\quad (I\otimes\Phi)(|\Omega\rangle\langle\Omega|)\ge0. \]
The maximally entangled vector \(|\Omega\rangle\) is a universal test input. It contains all input matrix units coherently. If the map behaves positively on this universal entangled test, then it behaves positively on every entangled extension.
This is why the theorem is central in quantum information theory. It turns the physical admissibility condition of complete positivity into an ordinary eigenvalue test. It also turns the abstract map \(\Phi\) into a concrete bipartite operator \(J(\Phi)\), from which Kraus operators, channel constraints, and semidefinite programs can be built.
References
Choi, Man-Duen. “Completely Positive Linear Maps on Complex Matrices.” Linear Algebra and Its Applications 10, no. 3 (1975): 285–290.
Jamiołkowski, Andrzej. “Linear Transformations Which Preserve Trace and Positive Semidefiniteness of Operators.” Reports on Mathematical Physics 3, no. 4 (1972): 275–278.
Kraus, Karl. “General State Changes in Quantum Theory.” Annals of Physics 64, no. 2 (1971): 311–335.
Nielsen, Michael A., and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 10th anniversary edition, 2010.
Watrous, John. The Theory of Quantum Information. Cambridge University Press, 2018.
Paulsen, Vern. Completely Bounded Maps and Operator Algebras. Cambridge University Press, 2003.
Wilde, Mark M. Quantum Information Theory. Cambridge University Press, 2nd edition, 2017.