InducedSchattenNorm

From QETLAB
Jump to: navigation, search
InducedSchattenNorm
Computes a lower bound of the induced p→q Schatten norm of a superoperator

Other toolboxes required none
Related functions DiamondNorm
InducedMatrixNorm
SchattenNorm
Function category Norms
Usable within CVX? no

InducedSchattenNorm is a function that computes a randomized lower bound of the induced p→q Schatten norm of a superoperator, defined as follows [1]: \[\|\Phi\|_{p\rightarrow q} := \max\big\{\|\Phi(X)\|_q : \|X\|_p = 1 \big\},\] where \[\|X\|_{p} := \left(\sum_i\sigma_i(X)^p\right)^{1/p}\] is the Schatten p-norm.

When p = q = 1, this is the induced trace norm that comes up frequently in quantum information theory (and whose stabilization is the diamond norm). In the p = q = Inf case, this is usually called the operator norm of $\Phi$, which comes up frequently in operator theory.

The lower bound is found via the algorithm described here, which starts with a random input matrix and performs a local optimization based on that starting matrix.

Syntax

  • NRM = InducedSchattenNorm(PHI,P)
  • NRM = InducedSchattenNorm(PHI,P,Q)
  • NRM = InducedSchattenNorm(PHI,P,Q,DIM)
  • NRM = InducedSchattenNorm(PHI,P,Q,DIM,TOL)
  • NRM = InducedSchattenNorm(PHI,P,Q,DIM,TOL,X0)
  • [NRM,X] = InducedSchattenNorm(PHI,P,Q,DIM,TOL,X0)

Argument descriptions

Input arguments

  • PHI: A superoperator to have its induced Schatten (PQ)-norm computed, specified as either a Choi matrix or a cell array of Kraus operators.
  • P: A real number ≥ 1, or Inf.
  • Q (optional, default equals P): A real number ≥ 1, or Inf.
  • DIM (optional): A 1-by-2 vector containing the input and output dimensions of PHI, in that order. Not required if PHI's input and output spaces have the same dimension or if it is provided as a cell array of Kraus operators.
  • TOL (optional, default equals sqrt(eps)): Numerical tolerance used throughout the script.
  • X0 (optional, default is randomly-generated): An input matrix to start the numerical search from.

Output arguments

  • NRM: A lower bound on the norm of X.
  • X (optional): A matrix with SchattenNorm(X,P) = 1 such that SchattenNorm(ApplyMap(X,PHI),Q) = NRM (i.e., an input matrix that attains the local maximum that was found).

Examples

A difference of unitaries channel

If $\Phi(X) = X - UXU^\dagger$, then the induced trace norm (i.e., Schatten 1-norm) of $\Phi$ is the diameter of the smallest circle that contains the eigenvalues of $U$. The following code verifies that this is indeed a lower bound in one special case:

>> U = [1 1;-1 1]/sqrt(2);
>> Phi = {eye(2),eye(2); U,-U};
>> InducedSchattenNorm(Phi,1)
 
ans =
 
    1.4142
 
>> lam = eig(U)
 
lam =
 
   0.7071 + 0.7071i
   0.7071 - 0.7071i
 
>> abs(lam(1) - lam(2))
 
ans =
 
    1.4142

Source code

Click on "expand" to the right to view the MATLAB source code for this function.

  1. %%  INDUCEDSCHATTENNORM    Computes a lower bound of the induced Schatten p->q norm of a superoperator
  2. %   This function has two required arguments:
  3. %     Phi: a superoperator, specified as either a Choi matrix or a cell
  4. %          array of Kraus operators
  5. %     P: a real number >= 1 or Inf
  6. %
  7. %   NRM = InducedSchattenNorm(PHI,P) is a lower bound of the induced
  8. %   Schatten P-norm of the superoperator PHI. This estimate of the norm is
  9. %   computed via a randomized algorithm, and thus running this function
  10. %   multiple times may produce different lower bounds.
  11. %
  12. %   This function has four optional input arguments:
  13. %     Q: a real number >= 1 or Inf (by default, Q = P)
  14. %     DIM: a 1-by-2 vector containing the input and output dimensions of
  15. %          PHI, in that order (not required if the input and output
  16. %          dimensions are equal, or if PHI is specified as a cell array)
  17. %     TOL: numerical tolerance used to determine when the algorithm stops
  18. %          running (default sqrt(eps))
  19. %     X0: a vector that acts as a starting point for the randomized
  20. %         algorithm (default is randomly-generated)
  21. %
  22. %   This function has one optional output argument:
  23. %     X: the best input matrix that was found (i.e., the matrix that
  24. %        maximizes the Q-Schatten norm of Phi(X) subject to the
  25. %        constraint SchattenNorm(X,P) = 1.
  26. %   
  27. %   [NRM,X] = InducedSchattenNorm(PHI,P,Q,DIM,TOL,V0) is a lower bound of
  28. %   the induced Schatten P->Q-norm of the superoperator PHI. This estimate
  29. %   of the norm is computed via a randomized algorithm, and thus running
  30. %   this function multiple times (with different X0) may produce different
  31. %   lower bounds. Smaller values of TOL give better numerical precision,
  32. %   but increase the running time of the algorithm.
  33. %
  34. %   URL: http://www.qetlab.com/InducedSchattenNorm
  35.  
  36. %   requires: ApplyMap.m, ChoiMatrix.m, KrausOperators.m, opt_args.m,
  37. %             Realignment.m, SchattenNorm.m, superoperator_dims.m
  38. %             
  39. %   author: Nathaniel Johnston (nathaniel@njohnston.ca)
  40. %   package: QETLAB
  41. %   last updated: January 11, 2016
  42.  
  43. function [nrm,X] = InducedSchattenNorm(Phi,p,varargin)
  44.  
  45. % Start by finding a set of Kraus operators for Phi and computing the
  46. % dimensions that Phi acts on.
  47. if(~iscell(Phi)) % don't alter the Kraus operators -- just wastes time
  48.     Phi = KrausOperators(Phi,varargin{2:end});
  49. end
  50. [da,db] = superoperator_dims(Phi,0,varargin{2:end});
  51.  
  52. % Set optional argument defaults: q=p, dim, tol=10^-8, X0=-1 (randomly-generated X0)
  53. [q,dim,tol,X0] = opt_args({ p, [da,db], sqrt(eps), -1 },varargin{:});
  54.  
  55. % Quickly compute in some special cases.
  56. if((p == 2 || strcmpi(p,'fro') == 1) && (q == 2 || strcmpi(q,'fro') == 1))
  57.     [~,S,V] = svd(Realignment(ChoiMatrix(Phi,2),dim).');
  58.     nrm = S(1,1); % the induced Frobenius norm is the norm of the natural representation
  59.     X = reshape(V(:,1),dim(1),dim(1)).'; % the X achieving the maximum is just the original map, viewed in a wonky basis
  60.     return
  61. end
  62.  
  63. % In all other cases, we iterate to compute the induced Schatten norm.
  64.  
  65. % If the user specified a starting guess v0, parse it; otherwise randomly
  66. % generate one.
  67. randX0 = 1;
  68. if(max(size(X0)) > 1)
  69.     if(length(X0) ~= dim(1))
  70.         warning('InducedSchattenNorm:DimensionMismatch','The initial matrix X0 must be of size DA-by-DA, where PHI is a map acting on DA-by-DA matrices. Using a randomly-generated intial matrix instead.');
  71.     else
  72.         randX0 = 0;
  73.     end
  74. end
  75. if randX0 % generate a random starting matrix X0, if appropriate
  76.     X = randn(dim(1),dim(1));
  77.     if(~isreal(ChoiMatrix(Phi))) % only add imaginary part to X if Phi is not real (just to make output prettier)
  78.         X = X + 1i*randn(dim(1),dim(1));
  79.     end
  80. else
  81.     X = X0;
  82. end
  83. X = X/SchattenNorm(X,p); % normalize the starting matrix
  84.  
  85. % Preparation is done; now do the actual iteration.
  86. it_err = 2*tol+1;
  87. Y = ApplyMap(X,Phi);
  88. nrm = SchattenNorm(Y,q);
  89.  
  90. while it_err > tol
  91.     % First, find the best left matrix Y, keeping the right matrix X fixed.
  92.     [U,S,V] = svd(Y);
  93.     S = diag(S); % only want the diagonal part of S
  94.  
  95.     if(q == Inf)
  96.         [~,ind] = max(S);
  97.         S = zeros(dim(2),1);
  98.         S(ind) = 1;
  99.     else
  100.         S = S/max(S); % pre-process in this way first for numerical reasons
  101.         S = S.^(q-1); % this is the equality condition from the Schatten Holder inequality
  102.         S = S/norm(S,q/(q-1));
  103.     end
  104.     Y = U*diag(S)*V'; % reconstruct the optimal Y from the new SVD that we just computed
  105.  
  106.     % Next, find the best right matrix X, keeping the left marix Y fixed.
  107.     X = ApplyMap(Y,DualMap(Phi,dim));
  108.     [U,S,V] = svd(X);
  109.     S = diag(S); % only want the diagonal part of S
  110.  
  111.     if(p == 1)
  112.         [~,ind] = max(S);
  113.         S = zeros(dim(1),1);
  114.         S(ind) = 1;
  115.     else
  116.         S = S/max(S); % pre-process in this way first for numerical reasons
  117.         S = S.^(1/(p-1)); % this is the equality condition from the Schatten Holder inequality
  118.         S = S/norm(S,p);
  119.     end
  120.     X = U*diag(S)*V'; % reconstruct the optimal X from the new SVD that we just computed
  121.  
  122.     % Check to see if we made any progress; if so, keep iterating.
  123.     Y = ApplyMap(X,Phi);
  124.     new_nrm = SchattenNorm(Y,q);
  125.     it_err = abs(new_nrm - nrm);
  126.     nrm = new_nrm;
  127. end

References

  1. J. Watrous. Notes on super-operator norms induced by Schatten norms. Quantum Information & Computation, 5(1):58–68, 2005. E-print: arXiv:quant-ph/0411077