InducedSchattenNorm
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.
Contents
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 (P→Q)-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:
Source code
Click on "expand" to the right to view the MATLAB source code for this function.
%% INDUCEDSCHATTENNORM Computes a lower bound of the induced Schatten p->q norm of a superoperator
% This function has two required arguments:
% Phi: a superoperator, specified as either a Choi matrix or a cell
% array of Kraus operators
% P: a real number >= 1 or Inf
%
% NRM = InducedSchattenNorm(PHI,P) is a lower bound of the induced
% Schatten P-norm of the superoperator PHI. This estimate of the norm is
% computed via a randomized algorithm, and thus running this function
% multiple times may produce different lower bounds.
%
% This function has four optional input arguments:
% Q: a real number >= 1 or Inf (by default, Q = P)
% DIM: a 1-by-2 vector containing the input and output dimensions of
% PHI, in that order (not required if the input and output
% dimensions are equal, or if PHI is specified as a cell array)
% TOL: numerical tolerance used to determine when the algorithm stops
% running (default sqrt(eps))
% X0: a vector that acts as a starting point for the randomized
% algorithm (default is randomly-generated)
%
% This function has one optional output argument:
% X: the best input matrix that was found (i.e., the matrix that
% maximizes the Q-Schatten norm of Phi(X) subject to the
% constraint SchattenNorm(X,P) = 1.
%
% [NRM,X] = InducedSchattenNorm(PHI,P,Q,DIM,TOL,V0) is a lower bound of
% the induced Schatten P->Q-norm of the superoperator PHI. This estimate
% of the norm is computed via a randomized algorithm, and thus running
% this function multiple times (with different X0) may produce different
% lower bounds. Smaller values of TOL give better numerical precision,
% but increase the running time of the algorithm.
%
% URL: http://www.qetlab.com/InducedSchattenNorm
% requires: ApplyMap.m, ChoiMatrix.m, KrausOperators.m, opt_args.m,
% Realignment.m, SchattenNorm.m, superoperator_dims.m
%
% author: Nathaniel Johnston (nathaniel@njohnston.ca)
% package: QETLAB
% last updated: January 11, 2016
function [nrm,X] = InducedSchattenNorm(Phi,p,varargin)
% Start by finding a set of Kraus operators for Phi and computing the
% dimensions that Phi acts on.
if(~iscell(Phi)) % don't alter the Kraus operators -- just wastes time
Phi = KrausOperators(Phi,varargin{2:end});
end
[da,db] = superoperator_dims(Phi,0,varargin{2:end});
% Set optional argument defaults: q=p, dim, tol=10^-8, X0=-1 (randomly-generated X0)
[q,dim,tol,X0] = opt_args({ p, [da,db], sqrt(eps), -1 },varargin{:});
% Quickly compute in some special cases.
if((p == 2 || strcmpi(p,'fro') == 1) && (q == 2 || strcmpi(q,'fro') == 1))
[~,S,V] = svd(Realignment(ChoiMatrix(Phi,2),dim).');
nrm = S(1,1); % the induced Frobenius norm is the norm of the natural representation
X = reshape(V(:,1),dim(1),dim(1)).'; % the X achieving the maximum is just the original map, viewed in a wonky basis
return
end
% In all other cases, we iterate to compute the induced Schatten norm.
% If the user specified a starting guess v0, parse it; otherwise randomly
% generate one.
randX0 = 1;
if(max(size(X0)) > 1)
if(length(X0) ~= dim(1))
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.');
else
randX0 = 0;
end
end
if randX0 % generate a random starting matrix X0, if appropriate
X = randn(dim(1),dim(1));
if(~isreal(ChoiMatrix(Phi))) % only add imaginary part to X if Phi is not real (just to make output prettier)
X = X + 1i*randn(dim(1),dim(1));
end
else
X = X0;
end
X = X/SchattenNorm(X,p); % normalize the starting matrix
% Preparation is done; now do the actual iteration.
it_err = 2*tol+1;
Y = ApplyMap(X,Phi);
nrm = SchattenNorm(Y,q);
while it_err > tol
% First, find the best left matrix Y, keeping the right matrix X fixed.
[U,S,V] = svd(Y);
S = diag(S); % only want the diagonal part of S
if(q == Inf)
[~,ind] = max(S);
S = zeros(dim(2),1);
S(ind) = 1;
else
S = S/max(S); % pre-process in this way first for numerical reasons
S = S.^(q-1); % this is the equality condition from the Schatten Holder inequality
S = S/norm(S,q/(q-1));
end
Y = U*diag(S)*V'; % reconstruct the optimal Y from the new SVD that we just computed
% Next, find the best right matrix X, keeping the left marix Y fixed.
X = ApplyMap(Y,DualMap(Phi,dim));
[U,S,V] = svd(X);
S = diag(S); % only want the diagonal part of S
if(p == 1)
[~,ind] = max(S);
S = zeros(dim(1),1);
S(ind) = 1;
else
S = S/max(S); % pre-process in this way first for numerical reasons
S = S.^(1/(p-1)); % this is the equality condition from the Schatten Holder inequality
S = S/norm(S,p);
end
X = U*diag(S)*V'; % reconstruct the optimal X from the new SVD that we just computed
% Check to see if we made any progress; if so, keep iterating.
Y = ApplyMap(X,Phi);
new_nrm = SchattenNorm(Y,q);
it_err = abs(new_nrm - nrm);
nrm = new_nrm;
end
References
- ↑ 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