Polynomial algorithms for UPB (Unextendable Product Bases) Consider a Hilbert space $H = H_1 \otimes \dots \otimes H_n$. An Unextendable Product Basis (UPB) is a set of product vectors $\vert v_i \rangle = \vert v_i^1 \rangle \otimes \dots \otimes \vert v_i^n \rangle$ such that:

a) all $\vert v_i \rangle$ are mutually orthogonal

b) there is no product vector orthogonal to all $\vert v_i \rangle$

c) basis is nontrivial, i.e. doesn't span $H$

(such bases are of interest in quantum information)

Questions:     


Is there a polynomial algorithm (in $n$) for finding UPBs? (note that in general there is no upper bound on the size of UPB, so a priori it might be exponential in $n$)
Is there a polynomial algorithm for checking if a given product basis is a UPB? (i.e. is unextendable)


Or is the problem NP-complete?
I'm a little baffled by question (1). An unextendable product basis exists in $H_1 \otimes H_2 \otimes \ldots \otimes H_n$ if $n\geq 3$ or if $n=2$ and $\dim H_1, \dim H_2 \geq 3$. In all of these cases, it is straightforward to find one. 

For question (2), the question is equivalent to checking whether there is a tensor product state in the subspace which is the complement of the space spanned by the basis. Leonid Gurvits has shown that checking whether a general subspace contains a tensor product state is NP-hard, so I suspect that it is hard in this case as well.