<p>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. </p>

<p>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. </p>

CC BY-SA 2.5
2011-03-27T10:23:43.730Z
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.
Marcin Kotowski
CC BY-SA 2.5
2011-03-27T04:31:27.463Z
2011-03-27T04:31:27.463Z
Peter Shor 
<p>Full classification is also known for another simple case 3x3, this is first addressed in the paper <a href="http://arxiv.org/abs/quant-ph/9808030" rel="nofollow">http://arxiv.org/abs/quant-ph/9808030</a> .</p>

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

<p><a href="http://arxiv.org/abs/1105.3142" rel="nofollow">http://arxiv.org/abs/1105.3142</a> .</p>

CC BY-SA 3.0
2012-03-02T00:54:48.907Z
2012-03-02T00:54:48.907Z
Lin Chen
<p>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:</p>

<p>a) all $\vert v_i \rangle$ are mutually orthogonal</p>

<p>b) there is no product vector orthogonal to all $\vert v_i \rangle$</p>

<p>c) basis is nontrivial, i.e. doesn't span $H$</p>

<p>(such bases are of interest in quantum information)</p>

<p>Questions:     </p>

<ol>
<li><p>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$)</p></li>
<li><p>Is there a polynomial algorithm for checking if a given product basis is a UPB? (i.e. is unextendable)</p></li>
</ol>

<p>Or is the problem NP-complete?</p>

CC BY-SA 2.5
2011-03-27T02:11:04.230Z
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
CC BY-SA 2.5
2011-03-27T04:13:56.153Z
@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 
<quantum-computing><linear-algebra><quantum-information>
Polynomial algorithms for UPB (Unextendable Product Bases)
Marcin Kotowski
# Polynomial algorithms for UPB (Unextendable Product Bases)

(Asked by: username_0 on 2011-03-26)

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?

**Tags:** quantum-computing, linear-algebra, quantum-information
> **Comments:**
> **username_1**: 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.  
> **username_2**: @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$.  

---

## 2 answers

### Answer by username_2 on 2011-03-27. Score: 7

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.

> **Comments:**
> **username_0**: 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.  

---

### Answer by username_3 on 2012-03-02. Score: 4

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


---

