Completely positive trace-preserving maps
A while back we upgraded from working with state vectors |\psi\rangle to working with density operators \rho, which are positive Hermitian operators \rho with \operatorname{tr}\rho=1, where “positive” means that \langle v|\rho|v\rangle\geqslant 0 for all |v\rangle (or, equivalently, that all its eigenvalues are non-negative real numbers).
It is easy to verify that quantum channels preserve positivity and trace, but the converse is not true!
That is, there are linear maps that preserve positivity and the trace, but which are not quantum channels, and thus which are not “physical operations”.
The matrix transpose operation \rho\mapsto\rho^T is a good example of such an unphysical operation: it preserves both trace and positivity, and if \rho is a density matrix then so too is \rho^T, but we will show that the transpose cannot be written in the Stinespring (or the Kraus) form;
it is not induced by a unitary operation on some larger Hilbert space, and it cannot be physically implemented.
So, we then ask, what is the class of physically admissible maps?
That is, how can we classify which maps are quantum channels and which are not?
First, some notation.
We say that a linear operator f\colon\mathcal{H}\to\mathcal{H}' between Hilbert spaces is bounded if there exists some real number B>0 such that \|f(x)\|_{\mathcal{H}'}\leqslant B\|x\|_{\mathcal{H}} for every vector x\in\mathcal{H}.
Given a pair of Hilbert spaces \mathcal{H} and \mathcal{H}', we denote the set of bounded linear operators from \mathcal{H} to \mathcal{H}' by \mathcal{B}(\mathcal{H},\mathcal{H}').
We write \mathcal{B}(\mathcal{H}) as shorthand for \mathcal{B(H,H)}.
One reason to care so much about bounded operators is the following fact: a linear operator between normed vector spaces is bounded if and only if it is continuous.
Another important fact is that the set \mathcal{B}(\mathcal{H},\mathcal{H}') is more than just a mere set: it has both topological structure (it has a norm and forms a Banach space under this norm) and algebraic structure (it is an associative algebra over \mathbb{C}), along with the bonus feature of a particularly well-behaved involution given by the adjoint.
Formally, \mathcal{B}(\mathcal{H},\mathcal{H}') is the prototypical example of a C*-algebra.
Now here is another example of where working only with finite-dimensional spaces greatly simplifies the mathematics: if X and Y are normed vector spaces, with X finite dimensional, then every linear map f\colon X\to Y is bounded (or, equivalently, continuous).
In the infinite-dimensional setting, it is important to know whether or not a given operator is bounded, but it turns out that certain unbounded operators are still very useful.
There are some technical details, but such operators are used to model observables in the Hilbert-space formalism of quantum mechanics.
Then, mathematically speaking, a quantum channel \mathcal{E} is a specific type of map
\mathcal{E}\colon \mathcal{B}(\mathcal{H}) \to \mathcal{B}(\mathcal{H}')
that sends states (i.e. density operators) on some Hilbert space \mathcal{H} to states on some (possibly different) Hilbert space \mathcal{H}'.
But we are not interested in just any such maps, of course — the statistical interpretation of quantum theory imposes certain properties on the subset of maps in which we are interested.
Firstly, for such a map \mathcal{E} to be a channel it must respect the mixing of states.
Consider an ensemble of systems, with a fraction p_1 of them in the state \rho_1, and the remaining p_2 of them in the state \rho_2.
The overall ensemble is described by \rho=p_1\rho_1+p_2\rho_2.
If we apply \mathcal{E} to each member of the ensemble individually, then the overall ensemble will be described by the density operator \rho'=\mathcal{E}(\rho), which should be given by \rho'=p_1\mathcal{E}(\rho_1)+p_2\mathcal{E}(\rho_2).
We conclude that \mathcal{E} must be a linear map.
Next, since \mathcal{E} must map density operators to density operators, it has to be both positive (\mathcal{E}(\rho)\geqslant 0 whenever \rho\geqslant 0) and trace preserving (\operatorname{tr}\mathcal{E}(\rho)=\operatorname{tr}\rho for all \rho).
Finally comes a subtle point.
It turns out that being positive is not good enough;
we must further require that the map \mathcal{E} remains positive even when extended to act on a part of a larger system.
Suppose that Alice and Bob share a bipartite system \mathcal{AB} in an entangled state \rho_\mathcal{AB}, and, whilst Alice does nothing, Bob applies the operation \mathcal{E} to his subsystems, and his subsystems only.
Then the resulting map on the whole bipartite system is given by \mathbf{1}\otimes\mathcal{E}, and we require that this also give a density operator \rho'_\mathcal{AB} of the composed system.
It turns out that this is a strictly stronger property than mere positivity;
we are asking for something called complete positivity.
Needless to say, complete positivity of \mathcal{E} implies positivity, but the converse does not hold: there are maps which are positive but not completely positive.
The matrix transpose operation \rho\rightarrow\rho^T is a classic example of such a map.
Let’s study this matrix transpose example a bit more.
Consider the transpose operation on a single qubit: T\colon|i\rangle\langle j|\mapsto|j\rangle\langle i| (for i,j\in\{0,1\}).
It preserves both trace and positivity, and if \rho is a density matrix then so too is T(\rho)=\rho^T.
However, if the input qubit is part of a two qubit system, initially in the entangled state |\Omega\rangle=\frac{1}{\sqrt{2}}(|0\rangle|0\rangle+|1\rangle|1\rangle), and the transpose is applied to only one of the two qubits (say, the second one), then the density matrix of the two qubits evolves under the action of the partial transpose \mathbf{1}\otimes T as
\begin{aligned}
|\Omega\rangle\langle\Omega|
= \frac{1}{2}\sum_{i,j} |i\rangle\langle j| \otimes |i\rangle\langle j|
\overset{\mathbf{1}\otimes T}{\longmapsto}
&\frac{1}{2}\sum_{i,j} |i\rangle\langle j| \otimes T( |i\rangle\langle j|)
\\= &\frac{1}{2}\sum_{i,j} |i\rangle\langle j| \otimes |j\rangle\langle i|.
\end{aligned}
The output is known as the \texttt{SWAP} matrix, since it describes the \texttt{SWAP} operation: |j\rangle|i\rangle\mapsto|i\rangle|j\rangle.
Since this operation squares to the identity, we know that its eigenvalues must be either \pm1: states which are symmetric under interchange of the two qubits have eigenvalue 1, while antisymmetric states have eigenvalue -1.
In particular then, the \texttt{SWAP} matrix has negative eigenvalues, which means that \mathbf{1}\otimes T does not preserve positivity (since \mathbf{1}\otimes T applied to the positive operator |\Omega\rangle\langle\Omega| is not positive), and therefore T is not a completely positive map.
If you prefer to see this more explicitly, then you can use the matrix representation of |\Omega\rangle\langle\Omega|, apply the partial transpose \mathbf{1}\otimes T, and then inspect the resulting matrix:
\frac{1}{2}\left[
\begin{array}{cc|cc}
1 & 0 & 0 & 1
\\0 & 0 & 0 & 0
\\\hline
0 & 0 & 0 & 0
\\1 & 0 & 0 & 1
\end{array}\right]
\overset{\mathbf{1}\otimes T}{\longmapsto}
\frac{1}{2}\left[
\begin{array}{cc|cc}
1 & 0 & 0 & 0
\\0 & 0 & 1 & 0
\\\hline
0 & 1 & 0 & 0
\\0 & 0 & 0 & 1
\end{array}\right].
So the partial transpose \mathbf{1}\otimes T maps the density matrix |\Omega\rangle\langle\Omega| of a maximally mixed state |\Omega\rangle to the \texttt{SWAP} matrix, which has a negative eigenvalue (namely -1) and thus is not a density matrix (since it is not positive).
We have seen that, at the very least, we want to be considering completely positive trace-preserving maps, but how do we know whether or not there are any further restrictions left to impose?
Needless to say, here is where mathematics alone cannot guide us, since we are trying to characterise maps which are physically admissible, and mathematics knows nothing about the reality of our universe!
However, one thing that we can do is compare our abstract approach with the derivations of quantum channels defined in terms of the Stinespring (or Kraus) representation.
As it happens, we can (and will!) show that a map is completely positive and trace preserving if and only if it can be written in the Stinespring (or Kraus) form.
In other words:
Quantum channels are exactly the completely positive trace-preserving (CPTP) maps.
One direction of this claim is much simpler than the other.
Any quantum channel \mathcal{E} must be completely positive, since the Kraus decomposition guarantees positivity of both \mathcal{E} and the extended map \mathbf{1}\otimes\mathcal{E}, since if \mathcal{E} has Kraus decomposition \sum_i E_i E_i^\dagger, then the extended channel \mathbf{1}\otimes\mathcal{E} has Kraus decomposition \sum_i(\mathbf{1}\otimes E_i)(\mathbf{1}\otimes E_i^\dagger), which means that \mathbf{1}\otimes\mathcal{E} is also a positive map, whence \mathcal{E} is completely positive.
Conversely, showing that CPTP maps are quantum channels is less simple.
In order to prove this, we will now introduce a very convenient tool called the Choi matrix, which gives yet another way to characterise linear maps between operators.