# Difference between revisions of "SkOperatorNorm"

(Created page with "{{Function |name=SkOperatorNorm |desc=Computes the S(k)-norm of an operator |req=[http://cvxr.com/cvx/ cvx]<br />iden<br />IsPSD<br />kpNorm...") |
m |
||

(9 intermediate revisions by one other user not shown) | |||

Line 1: | Line 1: | ||

{{Function | {{Function | ||

|name=SkOperatorNorm | |name=SkOperatorNorm | ||

− | |desc=Computes the | + | |desc=Computes the S(k)-norm of an operator |

− | |req=[http://cvxr.com/cvx/ | + | |req=[http://cvxr.com/cvx/ CVX] |

− | | | + | |rel=[[IsBlockPositive]]<br />[[SkVectorNorm]] |

− | |upd= | + | |cat=[[List of functions#Norms|Norms]] |

− | | | + | |upd=September 22, 2014 |

− | <tt>'''SkOperatorNorm'''</tt> is a [[List of functions|function]] that computes the | + | |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, | + | * <tt>LB = SkOperatorNorm(X,K,DIM,STR)</tt> |

− | * <tt>LB = SkOperatorNorm(X,K,DIM, | + | * <tt>LB = SkOperatorNorm(X,K,DIM,STR,TARGET)</tt> |

− | * <tt>[LB,~,UB] = SkOperatorNorm(X,K,DIM, | + | * <tt>LB = SkOperatorNorm(X,K,DIM,STR,TARGET,TOL)</tt> |

− | * <tt>[LB,LWIT,UB,UWIT] = SkOperatorNorm(X,K,DIM, | + | * <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 | + | * <tt>X</tt>: A square matrix acting on bipartite space. Generally, <tt>X</tt> should be positive semidefinite – 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> | + | * <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> | + | * <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 | + | * <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 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>. |

− | |||

==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)}$: | ||

− | < | + | <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 | ||

− | </ | + | </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 | + | 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: |

− | < | + | <syntaxhighlight> |

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

Line 71: | Line 74: | ||

uwit = | uwit = | ||

− | 0. | + | 0.0518 + 0.0000i -0.0625 + 0.0000i -0.0625 - 0.0000i -0.1250 - 0.0000i |

− | -0. | + | -0.0625 - 0.0000i 0.3018 + 0.0000i 0.0000 + 0.0000i -0.0625 - 0.0000i |

− | -0. | + | -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 | + | >> lwit'*X*lwit % verify that the lower bound is correct |

ans = | ans = | ||

Line 82: | Line 85: | ||

0.7286 + 0.0000i | 0.7286 + 0.0000i | ||

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

ans = | ans = | ||

0.7286 | 0.7286 | ||

− | </ | + | </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. 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>. |

− | < | + | <syntaxhighlight> |

− | >> X = | + | >> X = RandomDensityMatrix(9); |

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

Line 131: | Line 134: | ||

0.3770 | 0.3770 | ||

− | </ | + | </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

- ↑ 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] - ↑ 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.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]