OFFSET
1,1
COMMENTS
An unextendible product basis (UPB) is a set of mutually orthogonal product states such that there is no product state orthogonal to every member of the set. An n-qubit UPB is a UPB on the space C^2 tensored with itself n times, where C is the field of complex numbers.
LINKS
D. P. DiVincenzo, T. Mor, P. W. Shor, J. A. Smolin, and B. M. Terhal, Unextendible product bases, uncompletable product bases and bound entanglement, arXiv:quant-ph/9908070, 1999-2000; Commun. Math. Phys., 238:379-410, 2003.
K. Feng, Unextendible product bases and 1-factorization of complete graphs, Discrete Appl. Math., 154:942-949, 2006.
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. doi: 10.4230/LIPIcs.TQC.2013.93
Index entries for linear recurrences with constant coefficients, signature (1,0,0,1,-1).
FORMULA
a(n) = n + 1 if n is odd.
a(n) = n + 2 if n = 2 (mod 4) or if n = 4.
a(n) = n + 3 if n = 8.
a(n) = n + 4 otherwise (i.e., if n >= 12 and n = 0 (mod 4)).
G.f.: -x*(x^12-x^11+x^8-x^7+2*x^4-2*x^3-2*x-2) / ((x-1)^2*(x+1)*(x^2+1)). - Colin Barker, Feb 16 2013
EXAMPLE
a(2) = 4 because there is no nontrivial UPB on two qubits -- any UPB spans the entire 2^2 = 4-dimensional space.
a(3) = 4 because there is a 4-state UPB in 3-qubit space. If we use "ket" notation from quantum mechanics, then one such UPB is: |0>|0>|0>, |+>|1>|->, |1>|->|+>, |->|+>|1>. This is the "shifts" UPB from the DiVincenzo et al. paper.
MAPLE
a := proc(n) if(n mod 2 = 1)then return n + 1; elif(n = 4 or n mod 4 = 2)then return n + 2; elif(n = 8)then return 11; else return n + 4; fi: end: seq(a(n), n=1..67);
MATHEMATICA
Join[{2, 4, 4, 6, 6, 8, 8, 11}, LinearRecurrence[{1, 0, 0, 1, -1}, {10, 12, 12, 16, 14}, 60]] (* Jean-François Alcover, Nov 29 2017 *)
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Nathaniel Johnston, Feb 07 2013
STATUS
approved