# MinUPBSize

 Other toolboxes required MinUPBSize Gives the minimum cardinality of an unextendible product basis in given dimensions none UPB Unextendible product bases

MinUPBSize is a function that returns that minimum numbers of vectors required in an unextendible product basis (UPB), given the dimensions of the local Hilbert spaces. If the minimum size of a UPB in the given space is not known, and error will be produced.

## Syntax

• S = MinUPBSize(DIM)
• S = MinUPBSize(DIM,VERBOSE)

## Argument descriptions

• DIM: A vector that specifies the local Hilbert space dimensions.
• VERBOSE (optional, default 1): A flag (either 1 or 0) indicating that a reference to a journal article that provides a proof of the minimal size claimed by this script will or will not be displayed.

## Examples

The following code tells the user that the smallest UPB in $$\mathbb{C}^5 \otimes \mathbb{C}^6$$ has $$10$$ states, and points to the reference [1] for a proof of this fact:

>> MinUPBSize([5,6])
A proof of the minimal size in this case can be found in:
N. Alon and L. Lovasz. Unextendible product bases. J. Combinatorial Theory, Ser. A, 95:169-179, 2001.

ans =

10

The following code gives the same information, but without displaying the reference:

>> MinUPBSize([5,6],0)

ans =

10

The minimum size of UPBs is also known in many multipartite cases:

>> MinUPBSize([2,2,2,2,2,2,2,2])
A proof of the minimal size in this case can be found in:
N. Johnston. The minimum size of qubit unextendible product bases. In Proceedings of the 8th Conference on the
Theory of Quantum Computation, Communication and Cryptography (TQC 2013). E-print: arXiv:1302.1604 [quant-ph], 2013.

ans =

11

Unfortunately, there are also many cases where the minimum size of a UPB is not currently known. In these cases, and error is returned:

>> MinUPBSize([2,2,2,4])
??? Error using ==> MinUPBSize at 69
The minimum size of UPBs in the specified space is not currently known.

## Notes

The minimum size of UPBs is not known in full generality yet! If you know of another case that has been solved that isn't contained in this script, please e-mail me (my e-mail address is in the header of the source code below) the article reference.

## Source code

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

1. %%  MINUPBSIZE  Gives the minimum cardinality of an unextendible product basis in given dimensions
2. %   This function has one required input argument:
3. %     DIM: a vector containing the local dimensions
4. %
5. %   S = MinUPBSize(DIM) is the minimum possible number of vectors in an
6. %   unextendible product basis in a Hilbert space whose local dimensions
7. %   are given by DIM. A reference to a journal article that provides a
8. %   proof of the minimal size claimed by this script is also be displayed.
9. %
10. %   This function has one optional input argument:
11. %     VERBOSE (default 1)
12. %
13. %   S = MinUPBSize(DIM,1) is as above. S = MinUPBSize(DIM,0) produces the
14. %   same output, but does not print the reference to a journal article.
15. %
16. %   URL: http://www.qetlab.com/MinUPBSize
17.
18. %   requires: opt_args.m, opt_disp.m
19. %   author: Nathaniel Johnston (nathaniel@njohnston.ca)
20. %   package: QETLAB
21. %   last updated: June 22, 2013
22.
23. function s = MinUPBSize(dim,varargin)
24.
25. % set optional argument defaults: verbose=1
26. [verbose] = opt_args({ 1 },varargin{:});
27.
29. refs = {'K. Feng. Unextendible product bases and 1-factorization of complete graphs. Discrete Applied Mathematics, 154:942949, 2006.', ...
30.         '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:379410, 2003.', ...
31.         'N. Alon and L. Lovasz. Unextendible product bases. J. Combinatorial Theory, Ser. A, 95:169-179, 2001.', ...
32.         'J. Chen and N. Johnston. The minimum size of unextendible product bases in the bipartite case (and some multipartite cases). Comm. Math. Phys., 333(1):351-365, 2015.', ...
33.         'N. Johnston. The minimum size of qubit unextendible product bases. In Proceedings of the 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013). E-print: arXiv:1302.1604 [quant-ph], 2013.'};
34.
35. if(verbose > 1 && all(size(dim) == [1,1]))
36.     error('MinUPBSize:IncorrectVerbose',['VERBOSE should be 0 or 1, not ',num2str(verbose),'. You perhaps meant to call this function like this: MinUPBSize([',num2str(dim),',',num2str(verbose),'])']);
37. end
38.
39. np = length(dim);
40. dim = sort(dim);
41. tlb = sum(dim) - np + 1; % trivial lower bound on s
42. x_dim = max(dim);
43.
44. if(np == 2 && min(dim) <= 2)
45.     ref_ind = 2;
46.     s = prod(dim);
47. elseif(mod(tlb,2) == 0 || all(mod(dim,2) == 1)) % if tlb is even or all dims are odd
48.     ref_ind = 3;
49.     s = tlb;
50. elseif(np == 2 && x_dim-1 >= tlb-x_dim && tlb-x_dim >= 3)
51.     ref_ind = 4;
52.     s = tlb + 1;
53. elseif((np == 4 && all(dim == [2,2,2,2])) || (mod(np,4) == 2 && all(dim == 2*ones(1,np))))
54.     ref_ind = 1;
55.     s = tlb + 1;
56. elseif(np == 8 && all(dim == [2,2,2,2,2,2,2,2]))
57.     ref_ind = 5;
58.     s = 11;
59. elseif(all(dim == 2*ones(1,np)))
60.     ref_ind = 5;
61.     s = tlb + 3;
62. elseif(np == 3 && (all(dim == [2,2,3]) || all(dim == [2,2,5])))
63.     ref_ind = 1;
64.     s = tlb + 1;
65. elseif(np == 3 && dim(1) == 2 && dim(2) == 2 && mod(dim(3),4) == 1)
66.     ref_ind = 4;
67.     s = tlb + 1;
68. else
69.     error('MinUPBSize:MinSizeUnknown','The minimum size of UPBs in the specified space is not currently known.');
70. end
71.
72. opt_disp(['A proof of the minimal size in this case can be found in:\n',refs{ref_ind},'\n'],verbose);

## References

1. N. Alon and L. Lovasz. Unextendible product bases. J. Combinatorial Theory, Ser. A, 95:169–179, 2001.