Equivalence of the representations

We've now discussed three different ways to represent channels in mathematical terms, namely Stinespring representations, Kraus representations, and Choi representations. We also have the definition of a channel, which states that a channel is a linear mapping that always transforms density matrices into density matrices, even when the channel is applied to just part of a compound system. The remainder of the lesson is devoted to a mathematical proof that the three representations are equivalent and precisely capture the definition.

Overview of the proof

Our goal is to establish the equivalence of a collection of four statements, and we'll begin by writing them down precisely. All four statements follow the same conventions that have been used throughout the lesson, namely that $\Phi$ is a linear mapping from square matrices to square matrices, the rows and columns of the input matrices have been placed in correspondence with the classical states of a system $\mathsf{X}$ (the input system), and the rows and columns of the output matrices have been placed in correspondence with the classical states of a system $\mathsf{Y}$ (the output system).

1. $\Phi$ is a channel from $\mathsf{X}$ to $\mathsf{Y}.$ That is, $\Phi$ always transforms density matrices to density matrices, even when it acts on one part of a larger compound system.

2. The Choi matrix $J(\Phi)$ is positive semidefinite and satisfies the condition $\operatorname{Tr}_{\mathsf{Y}}(J(\Phi)) = \mathbb{I}_{\mathsf{X}}.$

3. There is a Kraus representation for $\Phi.$ That is, there exist matrices $A_0,\ldots,A_{N-1}$ for which the equation $\Phi(\rho) = \sum_{k = 0}^{N-1} A_k \rho A_k^{\dagger}$ is true for every input $\rho,$ and that satisfy the condition $\sum_{k = 0}^{N-1} A_k^{\dagger} A_k = \mathbb{I}_{\mathsf{X}}.$

4. There is a Stinespring representation for $\Phi.$ That is, there exist systems $\mathsf{W}$ and $\mathsf{G}$ for which the pairs $(\mathsf{W},\mathsf{X})$ and $(\mathsf{G},\mathsf{Y})$ have the same number of classical states, along with a unitary matrix $U$ representing a unitary operation from $(\mathsf{W},\mathsf{X})$ to $(\mathsf{G},\mathsf{Y}),$ such that $\Phi(\rho) = \operatorname{Tr}_{\mathsf{G}}\bigl( U (\vert 0\rangle\langle 0 \vert \otimes \rho) U^{\dagger} \bigr).$

The way the proof works is that a cycle of implications is proved: the first statement in our list implies the second, the second implies the third, the third implies the fourth, and the fourth statement implies the first. This establishes that all four statements are equivalent — which is to say that they're either all true or all false for a given choice of $\Phi$ — because the implications can be followed transitively from any one statement to any other.

This is a common strategy when proving that a collection of statements are equivalent, and a useful trick to use in such a context is to set up the implications in a way that makes them as easy to prove as possible. That is the case here — and in fact we've already encountered two of the four implications.

Channels to Choi matrices

Referring to the statements listed above by their numbers, the first implication to be proved is 1 $\Rightarrow$ 2. This implication was already discussed in the context of the Choi state of a channel. Here we'll summarize the mathematical details.

Assume that the classical state set of the input system $\mathsf{X}$ is $\Sigma$ and let $n = \vert\Sigma\vert.$ Consider the situation in which $\Phi$ is applied to the second of two copies of $\mathsf{X}$ together in the state

$$\vert \psi \rangle = \frac{1}{\sqrt{n}} \sum_{a \in \Sigma} \vert a \rangle \otimes \vert a \rangle,$$

which, as a density matrix, is given by

$$\vert \psi \rangle \langle \psi \vert = \frac{1}{n} \sum_{a,b \in \Sigma} \vert a\rangle\langle b \vert \otimes \vert a\rangle\langle b \vert.$$

The result can be written as

$$(\operatorname{Id}\otimes \,\Phi) \bigl(\vert \psi \rangle \langle \psi \vert\bigr) = \frac{1}{n} \sum_{a,b = 0}^{n-1} \vert a\rangle\langle b \vert \otimes \Phi\bigl(\vert a\rangle\langle b \vert\bigr) = \frac{J(\Phi)}{n},$$

and by the assumption that $\Phi$ is a channel this must be a density matrix. Like all density matrices it must be positive semidefinite, and multiplying a positive semidefinite matrix by a positive real number yields another positive semidefinite matrix, and therefore $J(\Phi) \geq 0.$

Moreover, under the assumption that $\Phi$ is a channel, it must preserve trace, and therefore

$$\begin{aligned} \operatorname{Tr}_{\mathsf{Y}} (J(\Phi)) & = \sum_{a,b\in\Sigma} \operatorname{Tr}\bigl(\Phi( \vert a\rangle\langle b \vert)\bigr) \, \vert a\rangle\langle b \vert\\ & = \sum_{a,b\in\Sigma} \operatorname{Tr}\bigl(\vert a\rangle\langle b \vert\bigr) \, \vert a\rangle\langle b \vert\\ & = \sum_{a\in\Sigma} \vert a\rangle\langle a \vert\\ & = \mathbb{I}_{\mathsf{X}}. \end{aligned}$$

Choi to Kraus representations

The second implication, again referring to the statements in our list by their numbers, is 2 $\Rightarrow$ 3. To be clear, we're ignoring the other statements — and in particular we cannot make the assumption that $\Phi$ is a channel. All we have to work with is that $\Phi$ is a linear mapping whose Choi representation satisfies $J(\Phi) \geq 0$ and $\operatorname{Tr}_{\mathsf{Y}} (J(\Phi)) = \mathbb{I}_{\mathsf{X}}.$

This, however, is all we need to conclude that $\Phi$ has a Kraus representation

$$\Phi(\rho) = \sum_{k = 0}^{N-1} A_k \rho A_k^{\dagger}$$

for which the condition

$$\sum_{k = 0}^{N-1} A_k^{\dagger} A_k = \mathbb{I}_{\mathsf{X}}$$

is satisfied.

We begin with the critically important assumption that $J(\Phi)$ is positive semidefinite, which means that it is possible to express it in the form

$$J(\Phi) = \sum_{k = 0}^{N-1} \vert \psi_k \rangle \langle \psi_k \vert \tag{1}$$

for some way of choosing the vectors $\vert\psi_0\rangle,\ldots,\vert\psi_{N-1}\rangle.$ In general there will be multiple ways to do this — and in fact this directly mirrors the freedom one has in choosing a Kraus representation for $\Phi.$

One way to obtain such an expression is to first use the spectral theorem to write

$$J(\Phi) = \sum_{k = 0}^{N-1} \lambda_k \vert \gamma_k \rangle \langle \gamma_k \vert,$$

in which $\lambda_0,\ldots,\lambda_{N-1}$ are the eigenvalues of $J(\Phi)$ (which are necessarily nonnegative real numbers because $J(\Phi)$ is positive semidefinite) and $\vert\gamma_0\rangle,\ldots,\vert\gamma_{N-1}\rangle$ are unit eigenvectors corresponding to the eigenvalues $\lambda_0,\ldots,\lambda_{N-1}.$

Note that, while there's no freedom in choosing the eigenvalues (except for how they're ordered), there is freedom in the choice of the eigenvectors, particularly when there are eigenvalues with multiplicity larger than one. So, this is not a unique expression of $J(\Phi)$ — we're just assuming we have one such expression. Regardless, because the eigenvalues are nonnegative real numbers, they have nonnegative square roots, and so we can select

$$\vert\psi_k\rangle = \sqrt{\lambda_k} \vert \gamma_k\rangle$$

for each $k = 0,\ldots,N-1$ to obtain an expression of the form $(1).$

It is, however, not essential that the expression $(1)$ comes from a spectral decomposition in this way, and in particular the vectors $\vert\psi_0\rangle,\ldots,\vert\psi_{N-1}\rangle$ need not be orthogonal in general. It is noteworthy, though, that we can choose these vectors to be orthogonal if we wish — and moreover we never need $N$ to be larger than $nm$ (recalling that $n$ and $m$ denote the numbers of classical states of $\mathsf{X}$ and $\mathsf{Y},$ respectively).

Next, each of the vectors $\vert\psi_0\rangle,\ldots,\vert\psi_{N-1}\rangle$ can be further decomposed as

$$\vert\psi_k\rangle = \sum_{a\in\Sigma} \vert a\rangle \otimes \vert \phi_{k,a}\rangle,$$

where the vectors $\{ \vert \phi_{k,a}\rangle \}$ have entries corresponding to the classical states of $\mathsf{Y}$ and can be explicitly determined by the equation

$$\vert \phi_{k,a}\rangle = \bigl( \langle a \vert \otimes \mathbb{I}_{\mathsf{Y}}\bigr) \vert \psi_k\rangle$$

for each $a\in\Sigma$ and $k=0,\ldots,N-1.$ Although $\vert\psi_0\rangle,\ldots,\vert\psi_{N-1}\rangle$ are not necessarily unit vectors, this is the same process we would use to analyze what would happen if a standard basis measurement was performed on the system $\mathsf{X}$ given a quantum state vector of the pair $(\mathsf{X},\mathsf{Y}).$

And now we come to the trick that makes this part of the proof work. We define our Kraus matrices $A_0,\ldots,A_{N-1}$ according to the following equation.

$$A_k = \sum_{a\in\Sigma} \vert \phi_{k,a}\rangle\langle a \vert$$

We can think about this formula purely symbolically: $\vert a\rangle$ effectively gets flipped around to form $\langle a\vert$ and moved to right-hand side, forming a matrix. For the purposes of verifying the proof, the formula is all we need.

There is, however, a simple and intuitive relationship between the vector $\vert\psi_k\rangle$ and the matrix $A_k,$ which is that by vectorizing $A_k$ we get $\vert\psi_k\rangle.$ What it means to vectorize $A_k$ is that we stack the columns on top of one another (with the leftmost column on top proceeding to the rightmost on the bottom), in order to form a vector. For instance, if $\mathsf{X}$ and $\mathsf{Y}$ are both qubits, and for some choice of $k$ we have

$$\begin{aligned} \vert\psi_k\rangle & = \alpha_{00} \vert 0\rangle \otimes \vert 0\rangle + \alpha_{01} \vert 0\rangle \otimes \vert 1\rangle + \alpha_{10} \vert 1\rangle \otimes \vert 0\rangle + \alpha_{11} \vert 1\rangle \otimes \vert 1\rangle\\[2mm] & = \begin{pmatrix} \alpha_{00} \\[1mm] \alpha_{01} \\[1mm] \alpha_{10} \\[1mm] \alpha_{11} \end{pmatrix}, \end{aligned}$$

then

$$\begin{aligned} A_k & = \alpha_{00} \vert 0\rangle\langle 0\vert + \alpha_{01} \vert 1\rangle\langle 0\vert + \alpha_{10} \vert 0\rangle\langle 1\vert + \alpha_{11} \vert 1\rangle\langle 1\vert\\[2mm] & = \begin{pmatrix} \alpha_{00} & \alpha_{10}\\[1mm] \alpha_{01} & \alpha_{11} \end{pmatrix}. \end{aligned}$$

(Beware: sometimes the vectorization of a matrix is defined in a slightly different way, which is that the rows of the matrix are transposed and stacked on top of one another to form a column vector.)

First we'll verify that this choice of Kraus matrices correctly describes the mapping $\Phi,$ after which we'll verify the other required condition. To keep things straight, let's define a new mapping $\Psi$ as follows.

$$\Psi(\rho) = \sum_{k = 0}^{N-1} A_k \rho A_k^{\dagger}$$

Thus, our goal is to verify that $\Psi = \Phi.$

The way we can do this is to compare the Choi representations of these mappings. Choi representations are faithful, so we have $\Psi = \Phi$ if and only if $J(\Phi) = J(\Psi).$ At this point we can simply compute $J(\Psi)$ using the expressions

$$\vert\psi_k\rangle = \sum_{a\in\Sigma} \vert a\rangle \otimes \vert \phi_{k,a}\rangle \quad\text{and}\quad A_k = \sum_{a\in\Sigma} \vert \phi_{k,a}\rangle\langle a \vert$$

together with the bilinearity of tensor products to simplify.

$$\begin{aligned} J(\Psi) & = \sum_{a,b\in\Sigma} \vert a\rangle \langle b \vert \otimes \sum_{k = 0}^{N-1} A_k \vert a\rangle \langle b \vert A_k^{\dagger}\\[2mm] & = \sum_{a,b\in\Sigma} \vert a\rangle \langle b \vert \otimes \sum_{k = 0}^{N-1} \vert \phi_{k,a} \rangle \langle \phi_{k,b} \vert \\[2mm] & = \sum_{k = 0}^{N-1} \biggl(\sum_{a\in\Sigma} \vert a\rangle \otimes \vert \phi_{k,a} \rangle\biggr) \biggl(\sum_{b\in\Sigma} \langle b\vert \otimes \langle \phi_{k,b} \vert\biggr)\\[2mm] & = \sum_{k = 0}^{N-1} \vert \psi_k \rangle \langle \psi_k \vert \\[2mm] & = J(\Phi) \end{aligned}$$

So, our Kraus matrices correctly describe $\Phi.$

It remains to check the required condition on $A_0,\ldots,A_{N-1},$ which turns out to be equivalent to the assumption $\operatorname{Tr}_{\mathsf{Y}}(J(\Phi)) = \mathbb{I}_{\mathsf{X}}$ (which we haven't used yet). What we'll show is this relationship:

$$\Biggl( \sum_{k = 0}^{N-1} A_k^{\dagger} A_k \Biggr)^{T} = \operatorname{Tr}_{\mathsf{Y}}(J(\Phi)) \tag{2}$$

(in which we're referring the matrix transpose on the left-hand side).

Starting on the left, we can first observe that

$$\begin{aligned} \Biggl(\sum_{k = 0}^{N-1} A_k^{\dagger} A_k\Biggr)^T & = \Biggl(\sum_{k = 0}^{N-1} \sum_{a,b\in\Sigma} \vert b \rangle \langle \phi_{k,b} \vert \phi_{k,a} \rangle \langle a \vert\Biggr)^T\\ & = \sum_{k = 0}^{N-1} \sum_{a,b\in\Sigma} \langle \phi_{k,b} \vert \phi_{k,a} \rangle \vert a \rangle \langle b \vert. \end{aligned}$$

The last equality follows from the fact that the transpose is linear and maps $\vert b\rangle\langle a \vert$ to $\vert a\rangle\langle b \vert.$

Moving to the right-hand side of our equation, we have

$$J(\Phi) = \sum_{k = 0}^{N-1} \vert \psi_k\rangle\langle\psi_k \vert = \sum_{k = 0}^{N-1} \sum_{a,b\in\Sigma} \vert a\rangle \langle b \vert \otimes \vert\phi_{k,a}\rangle\langle \phi_{k,b} \vert$$

and therefore

$$\begin{aligned} \operatorname{Tr}_{\mathsf{Y}}(J(\Phi)) & = \sum_{k = 0}^{N-1} \sum_{a,b\in\Sigma} \operatorname{Tr}\bigl(\vert\phi_{k,a}\rangle\langle \phi_{k,b} \vert \bigr)\, \vert a\rangle \langle b \vert\\ & = \sum_{k = 0}^{N-1} \sum_{a,b\in\Sigma} \langle \phi_{k,b} \vert \phi_{k,a} \rangle \vert a \rangle \langle b \vert. \end{aligned}$$

We've obtained the same result, and therefore the equation $(2)$ has been verified. It follows, by the assumption $\operatorname{Tr}_{\mathsf{Y}} (J(\Phi)) = \mathbb{I}_{\mathsf{X}},$ that

$$\Biggl(\sum_{k = 0}^{N-1} A_k^{\dagger} A_k\Biggr)^T = \mathbb{I}_{\mathsf{X}}$$

and therefore, because the identity matrix is its own transpose, the required condition is true.

$$\sum_{k = 0}^{N-1} A_k^{\dagger} A_k = \mathbb{I}_{\mathsf{X}}$$

Kraus to Stinespring representations

Now suppose that we have a Kraus representation of a mapping

$$\Phi(\rho) = \sum_{k = 0}^{N-1} A_k \rho A_k^{\dagger}$$

for which

$$\sum_{k = 0}^{N-1} A_k^{\dagger} A_k = \mathbb{I}_{\mathsf{X}}.$$

Our goal is to find a Stinespring representation for $\Phi.$

What we'd like to do first is to choose the garbage system $\mathsf{G}$ so that its classical state set is $\{0,\ldots,N-1\}.$ For $(\mathsf{W},\mathsf{X})$ and $(\mathsf{G},\mathsf{Y})$ to have the same size, however, it must be that $n$ divides $m N,$ allowing us to take $\mathsf{W}$ to have classical states $\{0,\ldots,d-1\}$ for $d = mN/n.$

For an arbitrary choice of $n,$ $m,$ and $N,$ it may not be the case that $mN/n$ is an integer, so we're not actually free to choose $\mathsf{G}$ so that it's classical state set is $\{0,\ldots,N-1\}.$ But we can always increase $N$ arbitrarily in the Kraus representation by choosing $A_k = 0$ for however many additional values of $k$ that we wish.

And so, if we tacitly assume that $mN/n$ is an integer, which is equivalent to $N$ being a multiple of $m/\operatorname{gcd}(n,m),$ then we're free to take $\mathsf{G}$ so that its classical state set is $\{0,\ldots,N-1\}.$ In particular, if it is the case that $N = nm,$ then we may take $\mathsf{W}$ to have $m^2$ classical states.

It remains to choose $U,$ and we'll do this by matching the following pattern.

$$U = \begin{pmatrix} A_{0} & \fbox{?} & \cdots & \fbox{?} \\[1mm] A_{1} & \fbox{?} & \cdots & \fbox{?} \\[1mm] \vdots & \vdots & \ddots & \vdots\\[1mm] A_{N-1} & \fbox{?} & \cdots & \fbox{?} \end{pmatrix}$$

To be clear, this pattern is meant to suggest a block matrix, where each block (including $A_{0},\ldots,A_{N-1}$ as well as the blocks marked with a question mark) has $m$ rows and $n$ columns. There are $N$ rows of blocks, which means that there are $d = mN/n$ columns of blocks.

Expressed in more formulaic terms, we will define $U$ as

$$\begin{aligned} U & = \sum_{k=0}^{N-1} \sum_{j=0}^{d-1} \vert k \rangle \langle j \vert \otimes M_{k,j} \\[4mm] & = \begin{pmatrix} M_{0,0} & M_{0,1} & \cdots & M_{0,d-1} \\[1mm] M_{1,0} & M_{1,1} & \cdots & M_{1,d-1} \\[1mm] \vdots & \vdots & \ddots & \vdots\\[1mm] M_{N-1,0} & M_{N-1,1} & \cdots & M_{N-1,d-1} \end{pmatrix} \end{aligned}$$

where each matrix $M_{k,j}$ has $m$ rows and $n$ columns, and in particular we shall take $M_{k,0} = A_k$ for $k = 0,\ldots,N-1.$

This must be a unitary matrix, and the blocks labeled with a question mark, or equivalently $M_{k,j}$ for $j>0,$ must be selected with this in mind — but aside from allowing $U$ to be unitary, the blocks labeled with a question mark won't have any relevance to the proof.

Let's momentarily disregard the concern that $U$ is unitary and focus on the expression

$$\operatorname{Tr}_{\mathsf{G}} \bigl( U (\vert 0\rangle \langle 0 \vert_{\mathsf{W}} \otimes \rho)U^{\dagger}\bigr)$$

that describes the output state of $\mathsf{Y}$ given the input state $\rho$ of $\mathsf{X}$ for our Stinespring representation. We can alternatively write

$$U(\vert 0\rangle\langle 0 \vert \otimes \rho)U^{\dagger} = U(\vert 0\rangle\otimes\mathbb{I}_{\mathsf{W}}) \rho (\langle 0\vert \otimes \mathbb{I}_{\mathsf{W}}) U^{\dagger},$$

and we see from our choice of $U$ that

$$U(\vert 0\rangle\otimes\mathbb{I}_{\mathsf{W}}) = \sum_{k = 0}^{N-1} \vert k\rangle \otimes A_k.$$

We therefore find that

$$U(\vert 0\rangle\langle 0 \vert \otimes \rho)U^{\dagger} = \sum_{j,k = 0}^{N-1} \vert k\rangle\langle j\vert \otimes A_k \rho A_j^{\dagger},$$

and so

$$\begin{aligned} \operatorname{Tr}_{\mathsf{G}} \bigl( U (\vert 0\rangle \langle 0 \vert_{\mathsf{W}} \otimes \rho) U^{\dagger}\bigr) & = \sum_{j,k = 0}^{N-1} \operatorname{Tr}\bigl(\vert k\rangle\langle j\vert\bigr) \, A_k \rho A_j^{\dagger} \\ & = \sum_{k = 0}^{N-1} A_k \rho A_k^{\dagger} \\ & = \Phi(\rho). \end{aligned}$$

We therefore have a correct representation for the mapping $\Phi,$ and it remains to verify that we can choose $U$ to be unitary.

Consider the first $n$ columns of $U$ when it's selected according to the pattern above. Taking these columns alone, we have a block matrix

$$\begin{pmatrix} A_0\\[1mm] A_1\\[1mm] \vdots\\[1mm] A_{N-1} \end{pmatrix}.$$

There are $n$ columns, one for each classical state of $\mathsf{X},$ and as vectors let us name the columns as $\vert \gamma_a \rangle$ for each $a\in\Sigma.$ Here's a formula for these vectors that can be matched to the block matrix representation above.

$$\vert \gamma_a\rangle = \sum_{k = 0}^{N-1} \vert k\rangle \otimes A_k \vert a \rangle$$

Now let's compute the inner product between any two of these vectors, meaning the ones corresponding to any choice of $a,b\in\Sigma.$

$$\langle \gamma_a \vert \gamma_b \rangle = \sum_{j,k = 0}^{N-1} \langle k \vert j \rangle \, \langle a \vert A_k^{\dagger} A_j \vert b\rangle = \langle a \vert \Biggl( \sum_{k = 0}^{N-1} A_k^{\dagger} A_k \Biggr) \vert b\rangle$$

By the assumption

$$\sum_{k = 0}^{m-1} A_k^{\dagger} A_k = \mathbb{I}_{\mathsf{X}}$$

we conclude that the $n$ column vectors $\{\vert\gamma_a\rangle\,:\,a\in\Sigma\}$ form an orthonormal set:

$$\langle \gamma_a \vert \gamma_b \rangle = \begin{cases} 1 & a = b\\ 0 & a\neq b \end{cases}$$

for all $a,b\in\Sigma.$

This implies that it is possible to fill out the remaining columns of $U$ so that it becomes a unitary matrix. In particular, the Gram-Schmidt orthogonalization process can be used to select the remaining columns. Something similar was done in the Quantum circuits lesson of "Basics of quantum information" in the context of the state discrimination problem.

Stinespring representations back to the definition

The final implication is 4 $\Rightarrow$ 1. That is, we assume that we have a unitary operation transforming a pair of systems $(\mathsf{W},\mathsf{X})$ into a pair $(\mathsf{G},\mathsf{Y}),$ and our goal is to conclude that the mapping

$$\Phi(\rho) = \operatorname{Tr}_{\mathsf{G}} \bigl( U (\vert 0\rangle \langle 0 \vert_{\mathsf{W}} \otimes \rho)U^{\dagger}\bigr)$$

is a valid channel. From its form, it is evident that $\Phi$ is linear, and it remains to verify that it always transforms density matrices into density matrices. This is pretty straightforward and we've already discussed the key points.

In particular, if we start with a density matrix $\sigma$ of a compound system $(\mathsf{Z},\mathsf{X}),$ and then add on an additional workspace system $\mathsf{W},$ we will certainly be left with a density matrix. If we reorder the systems $(\mathsf{W},\mathsf{Z},\mathsf{X})$ for convenience, we can write this state as

$$\vert 0\rangle\langle 0\vert_{\mathsf{W}} \otimes \sigma.$$

We then apply the unitary operation $U,$ and as we already discussed this is a valid channel, and hence maps density matrices to density matrices. Finally, the partial trace of a density matrix is another density matrix.

Another way to say this is to observe first that each of these things is a valid channel:

1. Introducing an initialized workspace system.
2. Performing a unitary operation.
3. Tracing out a system.

And finally, any composition of channels is another channel — which is immediate from the definition, but is also a fact worth observing in its own right.

This completes the proof of the final implication, and therefore we've established the equivalence of the four statements listed at the start of the section.