Difference between revisions of "SkOperatorNorm"

From QETLAB
Jump to navigation Jump to search
m
 
(7 intermediate revisions by one other user not shown)
Line 1: Line 1:
 
{{Function
 
{{Function
 
|name=SkOperatorNorm
 
|name=SkOperatorNorm
|desc=Computes the [[S(k)-operator norm|S(k)-norm of an operator]]
+
|desc=Computes the S(k)-norm of an operator
|req=[http://cvxr.com/cvx/ cvx]<br />[[iden]]<br />[[IsPSD]]<br />[[kpNorm]]<br />[[MaxEntangled]]<br />[[normalize_cols]]<br />[[opt_args]]<br />[[PartialMap]]<br />[[PartialTrace]]<br />[[PartialTranspose]]<br />[[PermuteSystems]]<br />[[Realignment]]<br />[[SchmidtDecomposition]]<br />[[SchmidtRank]]<br />[[SkVectorNorm]]<br />[[sporth]]<br />[[Swap]]
+
|req=[http://cvxr.com/cvx/ CVX]
|rel=[[IsBlockPositive]]
+
|rel=[[IsBlockPositive]]<br />[[SkVectorNorm]]
|upd=January 2, 2013
+
|cat=[[List of functions#Norms|Norms]]
|v=2.00}}
+
|upd=September 22, 2014
<tt>'''SkOperatorNorm'''</tt> is a [[List of functions|function]] that computes the [[S(k)-operator norm|S(k)-norm of an operator]]<ref>N. Johnston and D. W. Kribs. A Family of Norms With Applications in Quantum Information Theory. ''J. Math. Phys.'', 51:082202, 2010. E-print: [http://arxiv.org/abs/0909.3907 arXiv:0909.3907] [quant-ph]</ref><ref>N. Johnston and D. W. Kribs. A Family of Norms With Applications in Quantum Information Theory II. Quantum Information & Computation, 11(1 & 2):104–123, 2011. E-print: [http://arxiv.org/abs/1006.0898 arXiv:1006.0898] [quant-ph]</ref>:
+
|cvx=no}}
 +
<tt>'''SkOperatorNorm'''</tt> is a [[List of functions|function]] that computes the S(k)-norm of an operator<ref>N. Johnston and D. W. Kribs. A Family of Norms With Applications in Quantum Information Theory. ''J. Math. Phys.'', 51:082202, 2010. E-print: [http://arxiv.org/abs/0909.3907 arXiv:0909.3907] [quant-ph]</ref><ref>N. Johnston and D. W. Kribs. A Family of Norms With Applications in Quantum Information Theory II. Quantum Information & Computation, 11(1 & 2):104–123, 2011. E-print: [http://arxiv.org/abs/1006.0898 arXiv:1006.0898] [quant-ph]</ref>:
 
$$
 
$$
   \|X\|_{S(k)} := \sup_{|v\rangle , |w\rangle } \Big\{ \big| \langle w| X |v \rangle \big| : \big\||v \rangle\big\| = \big\||w \rangle\big\| = 1 \Big\}
+
   \|X\|_{S(k)} := \sup_{|v\rangle , |w\rangle } \Big\{ \big| \langle w| X |v \rangle \big| : SR(|v \rangle), SR(|v \rangle) \leq k, \big\||v \rangle\big\| = \big\||w \rangle\big\| = 1 \Big\},
 
$$
 
$$
 +
where $SR(\cdot)$ refers to the [[SchmidtRank|Schmidt rank]] of a pure state.
  
 
==Syntax==
 
==Syntax==
Line 15: Line 17:
 
* <tt>LB = SkOperatorNorm(X,K)</tt>
 
* <tt>LB = SkOperatorNorm(X,K)</tt>
 
* <tt>LB = SkOperatorNorm(X,K,DIM)</tt>
 
* <tt>LB = SkOperatorNorm(X,K,DIM)</tt>
* <tt>LB = SkOperatorNorm(X,K,DIM,ITS)</tt>
+
* <tt>LB = SkOperatorNorm(X,K,DIM,STR)</tt>
* <tt>LB = SkOperatorNorm(X,K,DIM,ITS,POS_MAP)</tt>
+
* <tt>LB = SkOperatorNorm(X,K,DIM,STR,TARGET)</tt>
* <tt>[LB,~,UB] = SkOperatorNorm(X,K,DIM,ITS,POS_MAP)</tt>
+
* <tt>LB = SkOperatorNorm(X,K,DIM,STR,TARGET,TOL)</tt>
* <tt>[LB,LWIT,UB,UWIT] = SkOperatorNorm(X,K,DIM,ITS,POS_MAP)</tt>
+
* <tt>[LB,~,UB] = SkOperatorNorm(X,K,DIM,STR,TARGET,TOL)</tt>
 +
* <tt>[LB,LWIT,UB,UWIT] = SkOperatorNorm(X,K,DIM,STR,TARGET,TOL)</tt>
  
 
==Argument descriptions==
 
==Argument descriptions==
 
===Input arguments===
 
===Input arguments===
* <tt>X</tt>: A square matrix acting on [[bipartite]] space. Generally, <tt>X</tt> should be positive semidefinite &ndash; the bounds produced otherwise are quite poor.
+
* <tt>X</tt>: A square matrix acting on bipartite space. Generally, <tt>X</tt> should be positive semidefinite &ndash; the bounds produced otherwise are quite poor.
 
* <tt>K</tt> (optional, default 1): A positive integer.
 
* <tt>K</tt> (optional, default 1): A positive integer.
 
* <tt>DIM</tt> (optional, by default has both subsystems of equal dimension): A 1-by-2 vector containing the dimensions of the subsystems that <tt>X</tt> acts on.
 
* <tt>DIM</tt> (optional, by default has both subsystems of equal dimension): A 1-by-2 vector containing the dimensions of the subsystems that <tt>X</tt> acts on.
* <tt>ITS</tt> (optional, default 10): The number of iterations used in an algorithm that computes the lower bound <tt>LB</tt>. Higher values of <tt>ITS</tt> result in better lower bounds but slower computations. <tt>ITS</tt> should be set to 0 if the user is only interested in <tt>UB</tt>.
+
* <tt>STR</tt> (optional, default 2): An integer that determines how hard the script should work to compute the lower and upper bounds (<tt>STR = -1</tt> means that the script won't stop working until the bounds match each other). Other valid values are <tt>0, 1, 2, 3, ...</tt>. In practice, if <tt>STR >= 4</tt> then most computers will run out of memory and/or the sun will explode before computation completes.
* <tt>ITS</tt> (optional, default is the transpose map if <tt>K = 1</tt> and the <tt>K</tt>-positive map $\Phi(X) = K{\rm Tr}(X)I - X$ if <tt>K > 1</tt>): A [[positive map|<tt>K</tt>-positive]] (but not [[completely positive]]) map used in the computation of the upper bound <tt>UB</tt>. Different <tt>K</tt>-positive maps lead to different upper bounds. Maps that are not <tt>K</tt>-positive will not result in error messages, but may result in nonsensical or incorrect calculations, so it is the user's responsibility to ensure that <tt>POS_MAP</tt> really is <tt>K</tt>-positive. <tt>PHI</tt> should be provided either as a Choi matrix, or as a cell with 2 columns whose entries are its Kraus operators (see the [[tutorial]] to learn how to deal with superoperators in QETLAB).
+
* <tt>TARGET</tt> (optional, default -1): A value that you wish to prove that the norm is above or below. If, at any point while this script is running, it proves that <tt>LB >= TARGET</tt> or that <tt>UB <= TARGET</tt>, then the script will immediately abort and return the best lower bound and upper bound computed up to that point. This is a time-saving feature that can be avoided by setting <tt>TARGET = -1</tt>.
 +
* <tt>TOL</tt> (optional, default <tt>eps^(3/8)</tt>): The numerical tolerance used throughout the script.
  
 
===Output arguments===
 
===Output arguments===
Line 32: Line 36:
 
* <tt>LWIT</tt>: A witness that verifies that <tt>LB</tt> is indeed a lower bound of the S(k)-operator norm of <tt>X</tt>. More specifically, <tt>LWIT</tt> is a unit vector such that <tt>SchmidtRank(LWIT,DIM) <= K</tt> and <tt>LWIT'*X*LWIT = LB</tt>.
 
* <tt>LWIT</tt>: A witness that verifies that <tt>LB</tt> is indeed a lower bound of the S(k)-operator norm of <tt>X</tt>. More specifically, <tt>LWIT</tt> is a unit vector such that <tt>SchmidtRank(LWIT,DIM) <= K</tt> and <tt>LWIT'*X*LWIT = LB</tt>.
 
* <tt>UB</tt>: An upper bound of the S(k)-operator norm of <tt>X</tt>.
 
* <tt>UB</tt>: An upper bound of the S(k)-operator norm of <tt>X</tt>.
* <tt>UWIT</tt>: A witness that verifies that <tt>UB</tt> is indeed an upper bound of the S(k)-operator norm of <tt>X</tt>. More specifically, <tt>UWIT</tt> is a positive semidefinite operator satisfying $\big\| X + (id \otimes \Phi^\dagger)(Y) \big\| = UB$, where $\Phi^\dagger$ is the [[dual map]] (in the sense of the Hilbert&ndash;Schmidt inner product) of <tt>POS_MAP</tt>.
+
* <tt>UWIT</tt>: A witness that verifies that <tt>UB</tt> is indeed an upper bound of the S(k)-operator norm of <tt>X</tt>. More specifically, <tt>UWIT</tt> is a feasible point of the dual semidefinite program presented in Section&nbsp;5.2.3 of <ref name="nj_thesis">N. Johnston. Norms and Cones in the Theory of Quantum Entanglement. PhD thesis, University of Guelph, 2012. E-print: [http://arxiv.org/abs/1207.1479 arXiv:1207.1479] [quant-ph]</ref>.
To see why this implies that $\|X\|_{S(k)} \leq UB$, see Section 5.2.1 of <ref name="nj_thesis">N. Johnston. Norms and Cones in the Theory of Quantum Entanglement. PhD thesis, University of Guelph, 2012. E-print: [http://arxiv.org/abs/1207.1479 arXiv:1207.1479] [quant-ph]</ref>.
 
  
 
==Examples==
 
==Examples==
 
===Exact computation in small dimensions===
 
===Exact computation in small dimensions===
 
When <tt>X</tt> lives in $M_2 \otimes M_2$, $M_2 \otimes M_3$, or $M_3 \otimes M_2$ (i.e., when <tt>prod(DIM) <= 6</tt>), the script is guaranteed to compute the exact value of $\|X\|_{S(1)}$:
 
When <tt>X</tt> lives in $M_2 \otimes M_2$, $M_2 \otimes M_3$, or $M_3 \otimes M_2$ (i.e., when <tt>prod(DIM) <= 6</tt>), the script is guaranteed to compute the exact value of $\|X\|_{S(1)}$:
<pre<noinclude></noinclude>>
+
<syntaxhighlight>
 
>> X = [5 1 1 1;1 1 1 1;1 1 1 1;1 1 1 1]/8;
 
>> X = [5 1 1 1;1 1 1 1;1 1 1 1;1 1 1 1]/8;
 
>> SkOperatorNorm(X)
 
>> SkOperatorNorm(X)
Line 45: Line 48:
  
 
     0.7286
 
     0.7286
</pre<noinclude></noinclude>>
+
</syntaxhighlight>
  
The fact that this computation is correct is illustrated in Example 5.2.11 of <ref name="nj_thesis"></ref>, where it was shown that the S(1)-norm is exactly $(3 + 2\sqrt(2))/8 \approx 0.7286$. However, if we were still unconvinced, we could request witnesses that verify that 0.7286 is both a lower bound and an upper bound of the S(1)-norm:
+
The fact that this computation is correct is illustrated in Example 5.2.11 of <ref name="nj_thesis"></ref>, where it was shown that the S(1)-norm is exactly $(3 + 2\sqrt{2})/8 \approx 0.7286$. However, if we were still unconvinced, we could request witnesses that verify that 0.7286 is both a lower bound and an upper bound of the S(1)-norm:
<pre<noinclude></noinclude>>
+
<syntaxhighlight>
 
>> [lb,lwit,ub,uwit] = SkOperatorNorm(X)
 
>> [lb,lwit,ub,uwit] = SkOperatorNorm(X)
  
Line 71: Line 74:
 
uwit =
 
uwit =
  
   0.0516            -0.0624 - 0.0000i  -0.0624 - 0.0000i   0.0004 + 0.0000i
+
   0.0518 + 0.0000i  -0.0625 + 0.0000i  -0.0625 - 0.0000i -0.1250 - 0.0000i
   -0.0624 + 0.0000i  0.3013            -0.1246 + 0.0000i  -0.0631 - 0.0000i
+
   -0.0625 - 0.0000i  0.3018 + 0.0000i  0.0000 + 0.0000i  -0.0625 - 0.0000i
   -0.0624 + 0.0000i -0.1246 - 0.0000i  0.3013            -0.0631 - 0.0000i
+
   -0.0625 + 0.0000i   0.0000 - 0.0000i  0.3018 + 0.0000i  -0.0625 + 0.0000i
  0.0004 - 0.0000i  -0.0631 + 0.0000i  -0.0631 + 0.0000i  0.3026         
+
  -0.1250 + 0.0000i  -0.0625 + 0.0000i  -0.0625 - 0.0000i  0.3018 + 0.0000i
  
 
>> lwit'*X*lwit % verify that the lower bound is correct
 
>> lwit'*X*lwit % verify that the lower bound is correct
Line 82: Line 85:
 
   0.7286 + 0.0000i
 
   0.7286 + 0.0000i
  
>> norm(X + [[PartialTranspose|PartialTranspose(uwit,2)]]) % verify that the upper bound is correct
+
>> norm(X + uwit) % verify that the upper bound is correct
  
 
ans =
 
ans =
  
 
     0.7286
 
     0.7286
</pre<noinclude></noinclude>>
+
</syntaxhighlight>
  
 
===Only interested in the lower and upper bounds; not the witnesses===
 
===Only interested in the lower and upper bounds; not the witnesses===
 
If all you want are the lower and upper bounds, but don't require the witnesses <tt>LWIT</tt> and <tt>UWIT</tt>, you can use code like the following. Note that in this case, $\|X\|_{S(1)}$ is computed exactly, as the lower and upper bound are equal (though this will not happen for all <tt>X</tt>!). However, all we know about $\|X\|_{S(2)}$ is that it lies in the interval [0.3522, 0.3546]. It is unsurprising that $\|X\|_{S(3)}$ is the usual operator norm of <tt>X</tt>, since this is always the case when <tt>K >= min(DIM)</tt>.
 
If all you want are the lower and upper bounds, but don't require the witnesses <tt>LWIT</tt> and <tt>UWIT</tt>, you can use code like the following. Note that in this case, $\|X\|_{S(1)}$ is computed exactly, as the lower and upper bound are equal (though this will not happen for all <tt>X</tt>!). However, all we know about $\|X\|_{S(2)}$ is that it lies in the interval [0.3522, 0.3546]. It is unsurprising that $\|X\|_{S(3)}$ is the usual operator norm of <tt>X</tt>, since this is always the case when <tt>K >= min(DIM)</tt>.
<pre<noinclude></noinclude>>
+
<syntaxhighlight>
>> X = [[RandomDensityMatrix|RandomDensityMatrix(9)]];
+
>> X = RandomDensityMatrix(9);
 
>> [lb,~,ub] = SkOperatorNorm(X,1)
 
>> [lb,~,ub] = SkOperatorNorm(X,1)
  
Line 131: Line 134:
  
 
     0.3770
 
     0.3770
</pre<noinclude></noinclude>>
+
</syntaxhighlight>
 +
 
 +
{{SourceCode|name=SkOperatorNorm}}
  
 
==References==
 
==References==
 
<references />
 
<references />

Latest revision as of 16:39, 13 June 2018

SkOperatorNorm
Computes the S(k)-norm of an operator

Other toolboxes required CVX
Related functions IsBlockPositive
SkVectorNorm
Function category Norms
Usable within CVX? no

SkOperatorNorm is a function that computes the S(k)-norm of an operator[1][2]: $$ \|X\|_{S(k)} := \sup_{|v\rangle , |w\rangle } \Big\{ \big| \langle w| X |v \rangle \big| : SR(|v \rangle), SR(|v \rangle) \leq k, \big\||v \rangle\big\| = \big\||w \rangle\big\| = 1 \Big\}, $$ where $SR(\cdot)$ refers to the Schmidt rank of a pure state.

Syntax

  • LB = SkOperatorNorm(X)
  • LB = SkOperatorNorm(X,K)
  • LB = SkOperatorNorm(X,K,DIM)
  • LB = SkOperatorNorm(X,K,DIM,STR)
  • LB = SkOperatorNorm(X,K,DIM,STR,TARGET)
  • LB = SkOperatorNorm(X,K,DIM,STR,TARGET,TOL)
  • [LB,~,UB] = SkOperatorNorm(X,K,DIM,STR,TARGET,TOL)
  • [LB,LWIT,UB,UWIT] = SkOperatorNorm(X,K,DIM,STR,TARGET,TOL)

Argument descriptions

Input arguments

  • X: A square matrix acting on bipartite space. Generally, X should be positive semidefinite – the bounds produced otherwise are quite poor.
  • K (optional, default 1): A positive integer.
  • DIM (optional, by default has both subsystems of equal dimension): A 1-by-2 vector containing the dimensions of the subsystems that X acts on.
  • STR (optional, default 2): An integer that determines how hard the script should work to compute the lower and upper bounds (STR = -1 means that the script won't stop working until the bounds match each other). Other valid values are 0, 1, 2, 3, .... In practice, if STR >= 4 then most computers will run out of memory and/or the sun will explode before computation completes.
  • TARGET (optional, default -1): A value that you wish to prove that the norm is above or below. If, at any point while this script is running, it proves that LB >= TARGET or that UB <= TARGET, then the script will immediately abort and return the best lower bound and upper bound computed up to that point. This is a time-saving feature that can be avoided by setting TARGET = -1.
  • TOL (optional, default eps^(3/8)): The numerical tolerance used throughout the script.

Output arguments

  • LB: A lower bound of the S(k)-operator norm of X.
  • LWIT: A witness that verifies that LB is indeed a lower bound of the S(k)-operator norm of X. More specifically, LWIT is a unit vector such that SchmidtRank(LWIT,DIM) <= K and LWIT'*X*LWIT = LB.
  • UB: An upper bound of the S(k)-operator norm of X.
  • UWIT: A witness that verifies that UB is indeed an upper bound of the S(k)-operator norm of X. More specifically, UWIT is a feasible point of the dual semidefinite program presented in Section 5.2.3 of [3].

Examples

Exact computation in small dimensions

When X lives in $M_2 \otimes M_2$, $M_2 \otimes M_3$, or $M_3 \otimes M_2$ (i.e., when prod(DIM) <= 6), the script is guaranteed to compute the exact value of $\|X\|_{S(1)}$:

>> X = [5 1 1 1;1 1 1 1;1 1 1 1;1 1 1 1]/8;
>> SkOperatorNorm(X)

ans =

    0.7286

The fact that this computation is correct is illustrated in Example 5.2.11 of [3], where it was shown that the S(1)-norm is exactly $(3 + 2\sqrt{2})/8 \approx 0.7286$. However, if we were still unconvinced, we could request witnesses that verify that 0.7286 is both a lower bound and an upper bound of the S(1)-norm:

>> [lb,lwit,ub,uwit] = SkOperatorNorm(X)

lb =

    0.7286


lwit =

   0.8536 + 0.0000i
   0.3536 - 0.0000i
   0.3536 + 0.0000i
   0.1464          


ub =

    0.7286


uwit =

   0.0518 + 0.0000i  -0.0625 + 0.0000i  -0.0625 - 0.0000i  -0.1250 - 0.0000i
  -0.0625 - 0.0000i   0.3018 + 0.0000i   0.0000 + 0.0000i  -0.0625 - 0.0000i
  -0.0625 + 0.0000i   0.0000 - 0.0000i   0.3018 + 0.0000i  -0.0625 + 0.0000i
  -0.1250 + 0.0000i  -0.0625 + 0.0000i  -0.0625 - 0.0000i   0.3018 + 0.0000i

>> lwit'*X*lwit % verify that the lower bound is correct

ans =

   0.7286 + 0.0000i

>> norm(X + uwit) % verify that the upper bound is correct

ans =

    0.7286

Only interested in the lower and upper bounds; not the witnesses

If all you want are the lower and upper bounds, but don't require the witnesses LWIT and UWIT, you can use code like the following. Note that in this case, $\|X\|_{S(1)}$ is computed exactly, as the lower and upper bound are equal (though this will not happen for all X!). However, all we know about $\|X\|_{S(2)}$ is that it lies in the interval [0.3522, 0.3546]. It is unsurprising that $\|X\|_{S(3)}$ is the usual operator norm of X, since this is always the case when K >= min(DIM).

>> X = RandomDensityMatrix(9);
>> [lb,~,ub] = SkOperatorNorm(X,1)

lb =

    0.2955


ub =

    0.2955

>> [lb,~,ub] = SkOperatorNorm(X,2)

lb =

    0.3522


ub =

    0.3546

>> [lb,~,ub] = SkOperatorNorm(X,3)

lb =

    0.3770


ub =

    0.3770

>> norm(X)

ans =

    0.3770

Source code

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

References

  1. N. Johnston and D. W. Kribs. A Family of Norms With Applications in Quantum Information Theory. J. Math. Phys., 51:082202, 2010. E-print: arXiv:0909.3907 [quant-ph]
  2. N. Johnston and D. W. Kribs. A Family of Norms With Applications in Quantum Information Theory II. Quantum Information & Computation, 11(1 & 2):104–123, 2011. E-print: arXiv:1006.0898 [quant-ph]
  3. 3.0 3.1 N. Johnston. Norms and Cones in the Theory of Quantum Entanglement. PhD thesis, University of Guelph, 2012. E-print: arXiv:1207.1479 [quant-ph]