Algorytmy wielomianowe dla UPB (nieusuwalne bazy produktów)

Rozważ przestrzeń Hilberta $H = H_1 \otimes \dots \otimes H_n$. Podstawa produktu nie do rozszerzenia (UPB) to zestaw wektorów produktu$\vert v_i \rangle = \vert v_i^1 \rangle \otimes \dots \otimes \vert v_i^n \rangle$ takie, że:

a) wszyscy $\vert v_i \rangle$ są wzajemnie ortogonalne

b) nie ma wektora produktu prostopadłego do wszystkich $\vert v_i \rangle$

c) podstawa jest nietrywialna, tzn. nie obejmuje $H$

(takie zasady są interesujące w informacji kwantowej)

Pytania:

1. Czy istnieje algorytm wielomianowy (w $n$) za znalezienie UPB? (zauważ, że ogólnie nie ma górnej granicy wielkości UPB, więc z góry może być wykładniczy w$n$)

2. Czy istnieje algorytm wielomianowy do sprawdzania, czy dana podstawa produktu jest UPB? (tzn. jest nie do przedłużenia)

Czy problem NP jest kompletny?

Jestem trochę zaskoczony pytaniem (1). Istnieje nierozszerzalna podstawa produktu w$H_1 \otimes H_2 \otimes \ldots \otimes H_n$ gdyby $n\geq 3$ albo jeśli $n=2$ i $\dim H_1, \dim H_2 \geq 3$. We wszystkich tych przypadkach znalezienie jednego jest proste.

W przypadku pytania (2) pytanie jest równoznaczne ze sprawdzeniem, czy w podprzestrzeni znajduje się stan iloczynu tensora, który jest dopełnieniem przestrzeni rozciągniętej przez podstawę. Leonid Gurvits wykazał, że sprawdzenie, czy ogólna podprzestrzeń zawiera stan produktu tensorowego, jest NP-trudne, więc podejrzewam, że również w tym przypadku jest trudne.

Pełna klasyfikacja znana jest również z innego prostego przypadku 3x3, który został po raz pierwszy omówiony w artykule http://arxiv.org/abs/quant-ph/9808030 .

Wynik jest również związany z konstrukcją dowolnych stanów splątanych 3x3 PPT rangi czwartej. Zobacz artykuł

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