MATLAB Scripts for Computing Completely Bounded Norms via Semidefinite Programming
Update [March 3, 2015]: I have released a MATLAB package called QETLAB that can compute the completely bounded and diamond norms (and much more) much faster than the code contained in this blog post. I recommend using QETLAB instead of the code below.
In operator theory, the completely bounded norm of a linear map on complex matrices \(\Phi : M_m \rightarrow M_n\) is defined by \(\|\Phi\|_{cb} := \sup_{k \geq 1} \| id_k \otimes \Phi \|\), where \(\|\Phi\|\) is the usual norm on linear maps defined by \(\|\Phi\| := \sup_{X \in M_m} \{ \|\Phi(X)\| : \|X\| \leq 1\}\) and \(\|X\|\) is the operator norm of \(X\) [1]. The completely bounded norm is particularly useful when thinking of \(M_m\) and \(M_n\) as operator spaces.
The dual of the completely bounded norm is called the diamond norm, which plays an important role in quantum information theory, as it can be used to measure the distance between quantum channels. The diamond norm of \(\Phi\) is typically denoted \(\|\Phi\|_{\diamond}\). For properties of the completely bounded and diamond norms, see [1,2,3].
A method for efficiently computing the completely bounded and diamond norms via semidefinite programming was recently presented in [4]. The purpose of this post is to provide MATLAB scripts that implement this algorithm and demonstrate its usage.
Download and Install
In order to make use of these scripts to compute the completely bounded or diamond norm, you must download and install two things: the SeDuMi semidefinite program solver and the MATLAB scripts themselves.
- SeDuMi – Please follow the instructions on the SeDuMi website to download and install it. If possible, you should install SeDuMi 1.1R3, not SeDuMi 1.21 or SeDuMi 1.3, since there is a bug with the newer versions when dealing with complex matrices.
- CB Norm MATLAB Package – Once SeDuMi is installed, download the CB norm MATLAB scripts, unzip them, and place them in your MATLAB scripts directory. The zip file contains 10 MATLAB scripts.
Once the scripts are installed, type “help CBNorm” or “help DiamondNorm” at the MATLAB prompt to learn how to use the CBNorm and DiamondNorm functions. Several usage examples are provided below.
Usage Examples
The representation of the linear map \(\Phi\) that the CBNorm and DiamondNorm functions take as input is a pair of arrays of its left- and right- generalized Choi-Kraus operators. That is, an array of operators \(\{A_i\}\) and \(\{B_i\}\) such that \(\Phi(X) = \sum_i A_i X B_i\) for all \(X\).
Basic Examples
If we wanted to compute the completely bounded and diamond norms of the map
the MATLAB input and output would be as follows:
>> PhiA(:,:,1) = [1,1;1,0]; >> PhiA(:,:,2) = [1,0;1,2]; >> PhiB(:,:,1) = [1,0;0,1]; >> PhiB(:,:,2) = [1,2;1,1]; >> CBNorm(PhiA,PhiB) ans = 7.2684 >> DiamondNorm(PhiA,PhiB) ans = 7.4124
So we see that its completely bounded norm is 7.2684 and its diamond norm is 7.4124.
If we instead want to compute the completely bounded or diamond norm of a completely positive map, we only need to provide its Kraus operators – i.e., operators \(\{A_i\}\) such that \(\Phi(X) = \sum_i A_i X A_i^\dagger\) for all \(X\). Furthermore, in this case semidefinite programming isn’t used at all, since [1, Proposition 3.6] tells us that \(\|\Phi\|_{cb} = \|\Phi(I)\|\) and \(\|\Phi\|_{\diamond} = \|\Phi^\dagger(I)\|\), and computing \(\|\Phi(I)\|\) is trivial. The following example demonstrates the usage of these scripts in this case, via a completely positive map \(\Phi : M_3 \rightarrow M_2\) with four (essentially random) Kraus operators:
>> PhiA(:,:,1) = [1 0 0;0 1 1]; >> PhiA(:,:,2) = [-3 0 1;5 1 1]; >> PhiA(:,:,3) = [0 2 0;0 0 0]; >> PhiA(:,:,4) = [1 1 3;0 2 0]; >> CBNorm(PhiA) ans = 42.0000 >> DiamondNorm(PhiA) ans = 38.7303
Transpose Map
Suppose we want to compute the completely bounded or diamond norm of the transpose map on \(M_n\). A generalized Choi-Kraus representation is given by defining \(A_{ij} = B_{ij} = e_i e_j^\dagger\), where \(\{e_i\}\) is the standard basis of \(\mathbb{C}^n\) (i.e., \(A_{ij}\) and \(B_{ij}\) are the operators with matrix representation in the standard basis with a one in the \((i,j)\)-entry and zeroes elsewhere). It is known that the completely bounded and diamond norms of the n-dimensional transpose map are both equal to n, which can be verified in small dimensions as follows:
>> % 2-dimensional transpose >> PhiA(:,:,1) = [1 0;0 0]; >> PhiA(:,:,2) = [0 1;0 0]; >> PhiA(:,:,3) = [0 0;1 0]; >> PhiA(:,:,4) = [0 0;0 1]; >> PhiB = PhiA; >> CBNorm(PhiA,PhiB) ans = 2.0000 >> DiamondNorm(PhiA,PhiB) ans = 2.0000
>> % 3-dimensional transpose >> I = eye(3); >> for i=1:3 for j=1:3 PhiA(:,:,3*(i-1)+j) = I(:,i)*I(j,:); end end >> PhiB = PhiA; >> CBNorm(PhiA,PhiB) ans = 3.0000 >> DiamondNorm(PhiA,PhiB) ans = 3.0000
Difference of Unitary Channels
Now consider the map \(\Phi : M_2 \rightarrow M_2\) defined by \(\Phi(X) = X – UXU^\dagger\), where \(U\) is the following unitary matrix:
We know from [2, Theorem 12] that the CB norm and diamond norm of \(\Phi\) are both equal to the diameter of the smallest closed disc containing all of the eigenvalues of \(U\). Because the eigenvalues of \(U\) are \((1 \pm i)/\sqrt{2}\), the smallest closed disc containing its eigenvalues has diameter \(\sqrt{2}\), so \(\|\Phi\|_{cb} = \|\Phi\|_{\diamond} = \sqrt{2}\). This result can be verified as follows:
>> PhiA(:,:,1) = [1 0;0 1]; >> PhiA(:,:,2) = [1 1;-1 1]/sqrt(2); >> PhiB(:,:,1) = [1 0;0 1]; >> PhiB(:,:,2) = -[1 -1;1 1]/sqrt(2); >> CBNorm(PhiA,PhiB) ans = 1.4142 >> DiamondNorm(PhiA,PhiB) ans = 1.4142
References
- V. I. Paulsen. Completely bounded maps and operator algebras. Cambridge University Press, 2003.
- N. Johnston, D. W. Kribs, and V. I. Paulsen. Computing stabilized norms for quantum operations via the theory of completely bounded maps. Quantum Inf. Comput., 9:16-35, 2009.
- J. Watrous. Theory of quantum information lecture notes.
- J. Watrous. Semidefinite programs for completely bounded norms. Theory Comput., 5:217–238, 2009.
Recent Comments