# UPB

UPB | |

Generates an unextendible product basis | |

Other toolboxes required | none |
---|---|

Related functions | IsUPB MinUPBSize UPBSepDistinguishable |

Function category | Unextendible product bases |

` UPB` is a function that generates an unextendible product basis (UPB). The user may either request a specific UPB from the literature such as

`'Tiles'`or

`'Pyramid'`

^{[1]}, or they may request a minimal UPB of specified dimensions.

## Syntax

`U = UPB(NAME)``U = UPB(NAME,OPT_PAR)``[U,V,W,...] = UPB(NAME,OPT_PAR)``U = UPB(DIM)``U = UPB(DIM,VERBOSE)``[U,V,W,...] = UPB(DIM,VERBOSE)`

## Argument descriptions

### Input arguments

**Important**: Do not specify both `NAME` and `DIM`: just one or the other!

`NAME`: The name of a UPB that is found in the literature. Accepted values include:`'GenShifts'`: A minimal UPB in \((\mathbb{C}^2)^{\otimes p}\) (only valid when p ≥ 3 is odd) constructed in^{[2]}. Note that`OPT_PAR`must be the number of parties (i.e., the integer p) in this case.`'Min4x4'`: A minimal UPB in \(\mathbb{C}^4 \otimes \mathbb{C}^4\) constructed in^{[3]}.`'Pyramid'`: A minimal UPB in \(\mathbb{C}^3 \otimes \mathbb{C}^3\) constructed in^{[1]}.`'QuadRes'`: A minimal UPB in \(\mathbb{C}^d \otimes \mathbb{C}^d\) (only valid when 2d-1 is prime and d is odd) constructed in^{[2]}. Note that you must set`OPT_PAR`equal to d (the local dimension) in this case.`'Shifts'`: A minimal UPB in \(\mathbb{C}^2 \otimes \mathbb{C}^2 \otimes \mathbb{C}^2\) introduced in^{[1]}.`'SixParam'`: The six-parameter UPB in \(\mathbb{C}^3 \otimes \mathbb{C}^3\) introduced in Section IV.A of^{[2]}. Note that`OPT_PAR`must be a vector containing the six parameters in this case.`'Tiles'`: A minimal UPB in \(\mathbb{C}^3 \otimes \mathbb{C}^3\) constructed in^{[1]}.`'GenTiles1'`: A non-minimal UPB in \(\mathbb{C}^n \otimes \mathbb{C}^n\) when n is even from^{[1]}. Note that`OPT_PAR`must be n in this case.`'GenTiles2'`: A non-minimal UPB in \(\mathbb{C}^m \otimes \mathbb{C}^n\) from^{[1]}. Note that`OPT_PAR`must be a 2-entry vector containing m and n in this case.

`DIM`: A vector containing the local dimensions of the desired UPB. In all cases, the smallest known UPB of the desired dimensionality is returned. If no unextendible product basis is known for the specified dimensions, an error is produced.`VERBOSE`(optional, default`1`): A flag (either 1 or 0) indicating whether or not a reference to a journal article that contains the UPB (or a description of how to construct the UPB) returned by this script will be displayed.

### Output arguments

If only one output argument is specified (e.g., `U = UPB(DIM)`) then `U` is a matrix whose columns are the product states in the desired UPB.

If multiple output arguments are specified (e.g., `[U,V,W,...] = UPB(DIM)`) then the unextendible product basis is obtained by tensoring the columns of `U, V, W, ...` together. That is, `U, V, W, ...` are the local vectors in the unextendible product basis.

## Examples

### Generating the "Shifts" UPB

The following code returns the "Shifts" UPB ^{[1]}, which is a UPB of 4 states on $\mathbb{C}^2 \otimes \mathbb{C}^2 \otimes \mathbb{C}^2$:

```
>> v = UPB('Shifts')
v =
1.0000 -0.0000 -0.0000 -0.0000
0 -0.0000 0.0000 -0.5000
0 0.0000 -0.5000 -0.0000
0 0.0000 0.5000 -0.5000
0 -0.5000 -0.0000 0.0000
0 -0.5000 0.0000 0.5000
0 0.5000 -0.5000 0.0000
0 0.5000 0.5000 0.5000
```

Alternatively, we can request that the local vectors on each copy of $\mathbb{C}^2$ are returned, rather than the total product vectors on $\mathbb{C}^2 \otimes \mathbb{C}^2 \otimes \mathbb{C}^2$:

```
>> [u,v,w] = UPB('Shifts')
u =
1.0000 0.0000 0.7071 -0.7071
0 1.0000 0.7071 0.7071
v =
1.0000 -0.7071 0.0000 0.7071
0 0.7071 1.0000 0.7071
w =
1.0000 0.7071 -0.7071 0.0000
0 0.7071 0.7071 1.0000
```

### Generating bound entangled states

As noted in ^{[1]}, if \(\big\{|v_i\rangle\big\}\) is an unextendible product basis, then $I - \sum_i |v_i\rangle\langle v_i|$ is (up to scaling) a bound entangled state. The following code illustrates this fact in $\mathbb{C}^3 \otimes \mathbb{C}^5$ by first constructing a UPB in this space, then constructing the corresponding state, and then verifying that this state is bound entangled.

```
>> v = UPB([3,5]);
Generated a minimal 7-state UPB from:
N. Alon and L. Lovasz. Unextendible product bases. J. Combinatorial Theory, Ser. A, 95:169-179, 2001.
See also: http://www.njohnston.ca/2013/03/how-to-construct-minimal-upbs/
>> rho = eye(3*5);
>> for j = 1:7
rho = rho - v(:,j)*v(:,j)';
end
rho = rho/7; % we are now done constructing the bound entangled state
>> IsSeparable(rho,[3,5]) % show that the state is indeed entangled
Determined to be entangled by not having a 2-copy symmetric extension. Reference:
A. C. Doherty, P. A. Parrilo, and F. M. Spedalieri. A complete family of separability criteria.
Phys. Rev. A, 69:022308, 2004.
ans =
0
>> IsPPT(rho,2,[3,5]) % verify that this state has positive partial transpose and is thus bound entangled
ans =
1
```

### Generating multipartite UPBs

Many multipartite minimal UPBs can be constructed via this script. For example, the following code generates a minimal UPB (of 6 states) in \(\mathbb{C}^2 \otimes \mathbb{C}^2 \otimes \mathbb{C}^3\):

```
>> [u,v,w] = UPB([2,2,3])
Generated a minimal 6-state UPB from:
K. Feng. Unextendible product bases and 1-factorization of complete graphs.
Discrete Applied Mathematics, 154:942–949, 2006.
u =
1.0000 0 1.0000 0.7071 0.7071 0.7071
0 1.0000 0 0.7071 -0.7071 0.7071
v =
1.0000 0.7071 0 0 0.7071 1.0000
0 0.7071 1.0000 1.0000 -0.7071 0
w =
1.0000 0.7071 0.5345 0.5774 0 0
0 0 -0.8018 0.5774 0.3162 1.0000
0 0.7071 -0.2673 -0.5774 -0.9487 0
```

However, the minimum size of UPBs is still unknown in many multipartite cases – an error is returned in these cases:

```
>> [u,v,w,x] = UPB([2,2,3,7])
??? Error using ==> UPB at 132
No minimal UPB is currently known in the specified dimensions.
```

## Source code

Click here to view this function's source code on github.

## References

- ↑
^{1.0}^{1.1}^{1.2}^{1.3}^{1.4}^{1.5}^{1.6}^{1.7}C.H. Bennett, D.P. DiVincenzo, T. Mor, P.W. Shor, J.A. Smolin, and B.M. Terhal. Unextendible product bases and bound entanglement.*Phys. Rev. Lett.*82, 5385–5388, 1999. E-print: arXiv:quant-ph/9808030 - ↑
^{2.0}^{2.1}^{2.2}D.P. DiVincenzo, T. Mor, P.W. Shor, J.A. Smolin, and B.M. Terhal. Unextendible product bases, uncompletable product bases and bound entanglement.*Commun. Math. Phys.*238, 379–410, 2003. E-print: arXiv:quant-ph/9908070 - ↑ T.B. Pedersen.
*Characteristics of unextendible product bases*. Master's Thesis, Aarhus Universitet, Datalogisk Institut, 2002.