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)


  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?

  • $\begingroup$ 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. $\endgroup$ Mar 27, 2011 at 2:11
  • 1
    $\begingroup$ @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$. $\endgroup$ Mar 27, 2011 at 4:13

2 Answers 2


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.

  • $\begingroup$ yes, but I'm potentially interested in finding as many inequivalent (say, with respect to local unitaries) UPBs as possible. Full classification is known only for simple cases like 2x2x2. $\endgroup$ Mar 27, 2011 at 10:23

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 .


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.