# InducedSchattenNorm

 Other toolboxes required InducedSchattenNorm Computes a lower bound of the induced p→q Schatten norm of a superoperator none DiamondNormInducedMatrixNormSchattenNorm Norms 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