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$ – Artem Kaznatcheev Mar 27 '11 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$ – 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.

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.

| cite | improve this answer | |
  • $\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$ – Marcin Kotowski Mar 27 '11 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 .

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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