# 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:

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?

• I am confused... wouldn't the standard basis for H satisfy the UPB condition in all cases? Or are there some other conditions I am missing. – Artem Kaznatcheev Mar 27 '11 at 2:11
• @Artem: the condition that's missing is that the number of vectors is strictly less than the dimension of $H_1 \otimes \ldots \otimes H_n$. – Peter Shor Mar 27 '11 at 4:13

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.