IsUPB

From QETLAB
Revision as of 18:26, 21 October 2014 by Nathaniel (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
IsUPB
Determines whether or not a set of product vectors form a UPB

Other toolboxes required none
Related functions MinUPBSize
UPB
UPBSepDistinguishable
Function category Distinguishing objects

IsUPB is a function that determines whether or not a given set of product vectors forms an unextendible product basis (UPB).

Syntax

  • IU = IsUPB(U,V,W,...)

Argument descriptions

Input arguments

  • U,V,W,...: Matrices, each with the same number of columns as each other, whose columns are the local vectors of the supposed UPB.

Output arguments

  • IU: A flag (either 1 or 0) specifying that the set of vectors described by U,V,W,... is or is not a UPB.
  • WIT (optional): If IU = 0 then this is a cell containing local vectors for a product vector orthogonal to every member of the non-UPB described by U,V,W,... (thus, it acts as a witness to the fact that it really is not a UPB). If IU = 1 then WIT is meaningless.

Examples

The "Tiles" UPB

The following code verifies that the well-known "Tiles" UPB is indeed a UPB:

>> [u,v] = UPB('Tiles') % generate the local vectors of the "Tiles" UPB
 
u =
 
    1.0000    0.7071         0         0    0.5774
         0   -0.7071         0    0.7071    0.5774
         0         0    1.0000   -0.7071    0.5774
 
 
v =
 
    0.7071         0         0    1.0000    0.5774
   -0.7071         0    0.7071         0    0.5774
         0    1.0000   -0.7071         0    0.5774
 
>> IsUPB(u,v)
 
ans =
 
     1

However, if we remove the fifth vector from this set, then it is no longer a UPB:

>> [iu,wit] = IsUPB(u(:,1:4),v(:,1:4));
>> iu
 
iu =
 
     0
 
>> celldisp(wit) % display the witness
 
wit{1} =
 
     0
     0
     1
 
 
 
wit{2} =
 
    0.0000
    0.7071
    0.7071

Indeed, it is not difficult to verify that wit{1} is orthogonal to u(:,1) and u(:,2), and wit{2} is orthogonal to v(:,3) and v(:,4), so the first four columns of u,v do not specify a UPB.

Source code

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

  1. %%  ISUPB    Determines whether or not a set of product vectors form a UPB
  2. %
  3. %   IU = IsUPB(U,V,W,...) returns 1 or 0, indicating that the local states
  4. %   specified by U, V, W, ... is or is not an unextendible product basis.
  5. %   U, V, W, ... should be matrices, each with the same number of columns,
  6. %   whose columns are the local vectors of the supposed UPB (i.e., each
  7. %   matrix corresponds to one party).
  8. %
  9. %   This function has one optional output argument:
  10. %     WIT
  11. %
  12. %   [IU,WIT] = IsUPB(U,V,W,...) is as above. If IU = 0 then WIT is a cell
  13. %   containing local vectors for a product vector orthogonal to every
  14. %   member of the non-UPB specified by U,V,W,.... If IU = 1 then WIT is
  15. %   meaningless.
  16. %
  17. %   URL: http://www.qetlab.com/IsUPB
  18.  
  19. %   requires: opt_args.m, vec_partitions.m
  20. %   author: Nathaniel Johnston (nathaniel@njohnston.ca)
  21. %   last updated: October 21, 2014
  22.  
  23. function [iu,wit] = IsUPB(varargin)
  24.  
  25. wit = 0;
  26. p = nargin; % number of parties in the UPB
  27. s = size(varargin{1},2); % number of states in the UPB
  28. for j = p:-1:1 % get local dimension of each party
  29.     dim(j) = size(varargin{j},1);
  30. end
  31.  
  32. pt = vec_partitions(1:s,p,dim-1); % all possible partitions of the states among the different parties
  33. num_pt = length(pt); % number of partitions to loop through
  34.  
  35. if(num_pt == 0) % no partitions, which means that so few vectors were provided that it can't possibly be a UPB
  36.     iu = 0;
  37.     if(nargout > 1) % generate a witness, if requested
  38.         orth_ct = 0;
  39.         wit = cell(1,p);
  40.         for l = p:-1:1
  41.             if(orth_ct >= s) % the witness we have generated is already orthogonal to all local vectors: just pick the first basis state from here on
  42.                 wit{l} = zeros(dim(l),1);
  43.                 wit{l}(1) = 1;
  44.             else
  45.                 ct_upd = min(dim(l)-1,s-orth_ct);
  46.                 wit{l} = null(varargin{l}(:,orth_ct+1:orth_ct+ct_upd).'); % these are the states orthogonal to the local states provided
  47.                 wit{l} = wit{l}(:,1); % we only need one witness state
  48.                 orth_ct = orth_ct + ct_upd;
  49.             end
  50.         end
  51.     end
  52.     return
  53. end
  54.  
  55. % There are non-trivial partitions to loop through. Do it!
  56. for k = 1:num_pt % loop through the partitions
  57.     num_orth = 1;
  58.     for l = p:-1:1 % loop through the parties
  59.         V = varargin{l}(:,pt{k}{l}); % these are the local states that we are choosing on the l-th party
  60.         orth_state{l} = null(V.'); % these are the states orthogonal to the local states
  61.         num_orth = num_orth*size(orth_state{l},2);
  62.         if(num_orth >= 1)
  63.             orth_state{l} = orth_state{l}(:,1); % we just do this so that the wit variable is prettier
  64.         end
  65.     end
  66.  
  67.     if(num_orth >= 1) % all parties have codimension at least 1: not a UPB
  68.         iu = 0;
  69.         wit = orth_state;
  70.         return
  71.     end
  72. end
  73.  
  74. iu = 1;