# Kraus operator rank

All quantum operations $\mathcal{E}$ on a system of Hilbert space dimension $\mathcal{d}$ can be generated by an operator-sum representation containing at most $\mathcal{d^2}$ elements. Extending further, an operation from space with dimension $\mathcal{m}$ to space with dimension $\mathcal{n}$ has an operator sum representation in terms of Kraus operators. Refer: http://en.wikipedia.org/wiki/Quantum_operation#Kraus_operators

The follow up proof is in terms of an exercise in Nielsen and Chuang's book, exercise 8.10 Proving the first part is easy enough... $W_{jk} = W_{kj}^{*}$ if you expand the definition of $W_{jk}$ and using properties of transpose conjugate. So W is in fact Hermitian. That it is of rank at most $d^2$ is what I'm not able to prove.

I read on wikipedia about the properties of rank of a matrix, and it says that a matrix of rank M can be expressed as the sum of M rank-1 matrices. In that case I would need to prove that the individual terms in the sum:

$\sum_{j,k} tr(E_j^{+}E_k)\left|j\right \rangle \left\langle k \right|$

are of rank 1. Since $tr(E_j^{+}E_k)$ is in fact a scalar, and $\left|j\right \rangle$ & $\left\langle k \right|$ are the eigenbasis for the input and output spaces, there can be d such terms of $\left|j\right \rangle$ and $\left|k\right \rangle$ respectively, the product of which forms a rank-1 matrix.

Hence there would be at max d*d such terms, if all the terms $tr(E_j^{+}E_k)$ are non-zero.

Is that the correct proof? Am I making a mistake somewhere?

The number of such terms is also called the Kraus rank as given in: https://en.wikipedia.org/wiki/Quantum_channel#Pure_channel

• yes, you are making a mistake: A matrix of rank k kann be expressed as a sum of k rank-1 matrices (that's via singular value decomposition, just as Nielsen&Chuang say), but that doesn't mean that ANY decomposition into rank-1 matrices has at most k matrices. Rather the opposite: it has at least k matrices. Thus proving (which is trivial) that the summands in your some are of rank-1 doesn't get you anywhere. Oct 8, 2014 at 17:04

Since there still isn't an answer but the question has attracted a few upvotes, let me elaborate on my comment. This is more maths, than physics, but anyway.

Writing $\sum_{jk} \mathrm{tr}(E_j^{\dagger}E_i)|j\rangle\langle k|$ doesn't give you anything. This is indeed a rank-one decomposition, but the theorem does not tell you that ANY rank-1 decomposition has at most d^2 terms. This would be true, if $|j\rangle$ was the eigenbasis of $\mathbb{C}^d$ - but it is not. $W$ is an $M\times M$ matrix, hence $|j\rangle$ is the eigenbasis of $\mathbb{C}^M$ and $M$ could be much larger than this.

However, what is true is that $E_j\in\mathbb{C}^{d\times d}$. The key observation is that at most $d^2$ of these $E_j$ can therefore be linearly independent and this entails that $W$ can only be of rank at most $d^2$. Here is a proof (albeit not that pretty):

There is a basis of $\mathbb{C}^{d\times d}$ with $d^2$ elements, call it $F_j$, which is orthonormal with respect to the trace inner-product. Now, since the $F_j$ form a basis, for every $E_j$ we have:

$$E_j=\sum_i a_i^{(j)} F_i \qquad a_i^{(j)}\in\mathbb{C}\quad \forall\,j\in \{1,\ldots,N\}$$

the $E_j$ are linear combinations of the $F_j$. But then, we can reexpress the columns of W by $F_i$ and obtain:

$$\operatorname{tr}(E_i^{\dagger}E_j)=\sum_{k=1}^{d^2} {a_k^{(i)}}^* a_k^{(j)}$$

By definition of a basis, only $d^2$ of the $E_i$ can be linearly independent. Without loss of generality, we suppose the first $d^2$ $E_i$ were linearly independent. Let's then have a look at the $(d^2+1)$th column. Since $E_{d^2+1}$ is linearly dependent, its coefficients $a_k^{(d^2+1)}$ are linear combinations of the other $a^{(j)}$, say

$$a^{(d^2+1)}_k=\sum_{j=1}^{d^2} b_ja_k^{(j)}$$

But then, we can see that

$$\operatorname{tr}(E_i^{\dagger}E_{d^2+1})=\sum_j b_j \operatorname{tr}(E_i^{\dagger}E_j)$$

hence the whole column is a linear combination of the former columns. Putting everything together, $W$ can have at most $d^2$ linearly independent columns. We can then diagonalize $W$, since it is Hermitian and proceed as indicated.

• I can see the reasoning for determining the maximal possible rank of W. Still, I fail to see the usefulness in using W for proving the particular statement. That is, why is W constructed the way it is? What makes the unitary matrix U significant by its ability to make W diagonal? I'm a bit confused by the premises suggested for this problem. Aug 20, 2016 at 12:41

There's no need to introduce an orthonormal basis for the space of operators. Let $$|w_k\rangle \equiv \sum_{j}W_{jk}|j\rangle = \sum_{j}\mathrm{tr}(E_j^\dagger E_k)|j\rangle$$ denote the $$k$$th column of $$W$$. As noted, at most $$d^2$$ of the $$E_j$$ can be linearly independent. Suppose without loss of generality that $$E_1, \dots, E_{d^2}$$ are linearly independent. Then, there exist $$c_{kl} \in \mathbb{C}$$ for which $$E_k = \sum_{l=1}^{d^2} c_{kl}E_l$$ for any $$k > d^2$$. Hence, $$|w_k\rangle = \sum_j \mathrm{tr}\left(E_j^\dagger \sum_{l=1}^{d^2}c_{kl}E_l\right)|j\rangle = \sum_{l=1}^{d^2} c_{kl} \left[\sum_j \mathrm{tr}(E_j^\dagger E_l)|j\rangle\right] = \sum_{l=1}^{d^2}c_{kl}|w_l\rangle,$$ i.e., for every $$k > d^2$$, the $$k$$th column of $$W$$ is a linear combination of the first $$d^2$$ columns of $$W$$. The number of linearly independent columns is therefore at most $$d^2$$, so the rank is at most $$d^2$$.