Polynomial algorithms for UPB (Unextendable Product Bases)

Question

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:

1. 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$)

2. 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?

Answer 1

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.

Answer 2

Full classification is also known for another simple case 3x3, this is first addressed in the paper http://arxiv.org/abs/quant-ph/9808030 .

The result is also related to the construction of arbitrary 3x3 PPT entangled states of rank four. See the paper

http://arxiv.org/abs/1105.3142 .