Blog > MATLAB Scripts for Computing Completely Bounded Norms via Semidefinite Programming

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.

  1. 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.
  2. 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

  1. V. I. Paulsen. Completely bounded maps and operator algebras. Cambridge University Press, 2003.
  2. 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.
  3. J. Watrous. Theory of quantum information lecture notes.
  4. J. Watrous. Semidefinite programs for completely bounded norms. Theory Comput., 5:217–238, 2009.
  1. Ian H.
    February 8th, 2012 at 15:57 | #1

    Thanks for posting this, I have found it very useful. I wrote my own diamond norm function using the cvx library for Matlab. SeDuMi is a bit problematic for me (64-bit linux, Matlab 2011b), the only version mex didn’t complain about was the newest one, which prevents me from using Kraus operators with complex entries under your code. However, I did compare the results of my code with yours in the real case, and they agree to about 9 decimal places, which is pretty good.

    CVX seems to be a fair bit quicker for this application, which surprised me considering how much mex-ing SeDuMi does. I can get the diamond norm of a 4-qubit superoperator with 8 random left and right kraus operators in 16 seconds, for example.

  2. February 8th, 2012 at 18:23 | #2

    @Ian H. – Thanks for mentioning CVX, as I was unaware of it. Getting SeDuMi to work properly is generally a pain (as you have experienced), so it’ll be nice to have an alternative to play with.

    And that’s indeed some impressive speed! It could be that SDPT3 (assuming you’re using CVX’s default solver) is just faster for these types of semidefinite programs than SeDuMi is, or it’s also entirely possible that your code is just much cleaner than mine 🙂

  1. No trackbacks yet.