MinUPBSize

From QETLAB
Jump to: navigation, search
MinUPBSize
Gives the minimum cardinality of an unextendible product basis in given dimensions

Other toolboxes required none
Related functions UPB
Function category 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.  
  28. % pre-load various references
  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.