login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

The minimum cardinality of an n-qubit unextendible product basis.
1

%I #45 Nov 30 2017 00:06:08

%S 2,4,4,6,6,8,8,11,10,12,12,16,14,16,16,20,18,20,20,24,22,24,24,28,26,

%T 28,28,32,30,32,32,36,34,36,36,40,38,40,40,44,42,44,44,48,46,48,48,52,

%U 50,52,52,56,54,56,56,60,58,60,60,64,62,64,64,68,66,68,68

%N The minimum cardinality of an n-qubit unextendible product basis.

%C 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.

%H D. P. DiVincenzo, T. Mor, P. W. Shor, J. A. Smolin, and B. M. Terhal, <a href="https://arxiv.org/abs/quant-ph/9908070">Unextendible product bases, uncompletable product bases and bound entanglement</a>, arXiv:quant-ph/9908070, 1999-2000; Commun. Math. Phys., 238:379-410, 2003.

%H K. Feng, <a href="https://doi.org/10.1016/j.dam.2005.10.011">Unextendible product bases and 1-factorization of complete graphs</a>, Discrete Appl. Math., 154:942-949, 2006.

%H N. Johnston, <a href="http://arxiv.org/abs/1302.1604">The minimum size of qubit unextendible product bases</a>. In Proceedings of the 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC), 2013. doi: 10.4230/LIPIcs.TQC.2013.93

%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (1,0,0,1,-1).

%F a(n) = n + 1 if n is odd.

%F a(n) = n + 2 if n = 2 (mod 4) or if n = 4.

%F a(n) = n + 3 if n = 8.

%F a(n) = n + 4 otherwise (i.e., if n >= 12 and n = 0 (mod 4)).

%F 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

%e a(2) = 4 because there is no nontrivial UPB on two qubits -- any UPB spans the entire 2^2 = 4-dimensional space.

%e 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.

%p 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);

%t 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 *)

%Y Cf. A229913.

%K nonn,easy

%O 1,1

%A _Nathaniel Johnston_, Feb 07 2013