Algoritma polinomial untuk UPB (Basis Produk Tidak Dapat Dipertahankan)

Pertimbangkan ruang Hilbert . Dasar Produk Yang Tidak Dapat Diubah (UPB) adalah sekumpulan vektor produk sedemikian rupa sehingga:$H = H_1 \otimes \dots \otimes H_n$$\vert v_i \rangle = \vert v_i^1 \rangle \otimes \dots \otimes \vert v_i^n \rangle$

a) semua saling ortogonal$\vert v_i \rangle$

b) tidak ada vektor produk ortogonal untuk semua$\vert v_i \rangle$

c) dasar adalah nontrivial, yaitu tidak span$H$

(pangkalan-pangkalan seperti itu menarik dalam informasi kuantum)

Pertanyaan:

1. Apakah ada algoritma polinomial (dalam ) untuk menemukan UPB? (perhatikan bahwa secara umum tidak ada batas atas pada ukuran UPB, jadi apriori itu mungkin eksponensial dalam )$n$$n$

2. Apakah ada algoritma polinomial untuk memeriksa apakah basis produk yang diberikan adalah UPB? (Yaitu tidak bisa diperpanjang)

Atau apakah NP-nya sudah selesai?

Saya sedikit bingung dengan pertanyaan (1). Basis produk yang tidak dapat diperpanjang ada dalam jika n ≥ 3 atau jika n = 2 dan redup H 1 , redup H 2 ≥ 3 . Dalam semua kasus ini, sangat mudah untuk menemukannya.$H_1 \otimes H_2 \otimes \ldots \otimes H_n$$n\geq 3$$n=2$$\dim H_1, \dim H_2 \geq 3$

Untuk pertanyaan (2), pertanyaannya setara dengan memeriksa apakah ada keadaan produk tensor dalam subruang yang merupakan komplemen dari ruang yang direntang oleh basis. Leonid Gurvits telah menunjukkan bahwa memeriksa apakah subruang umum berisi keadaan produk tensor adalah NP-hard, jadi saya curiga sulit juga dalam kasus ini.

Klasifikasi lengkap juga dikenal untuk kasus sederhana 3x3, ini pertama kali dibahas dalam makalah http://arxiv.org/abs/quant-ph/9808030 .

Hasilnya juga terkait dengan pembangunan PPT 3x3 acak yang terjerat pada peringkat empat. Lihat kertasnya

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