Polynomalgorithmen für UPB (Unextendable Product Bases)

9

Betrachten Sie einen Hilbert-Raum . Eine nicht erweiterbare Produktbasis (UPB) ist eine Menge von Produktvektoren so dass:H.=H.1H.n|vich=|vich1|vichn

a) Alle sind zueinander orthogonal|vich

b) Es gibt keinen Produktvektor orthogonal zu allen|vich

c) Basis ist nicht trivial, dh erstreckt sich nicht überH.

(Solche Basen sind für Quanteninformationen von Interesse.)

Fragen:

  1. Gibt es einen Polynomalgorithmus (in ) zum Auffinden von UPBs? (Beachten Sie, dass es im Allgemeinen keine Obergrenze für die Größe von UPB gibt, so dass sie a priori in exponentiell sein kann. )nn

  2. Gibt es einen Polynomalgorithmus, mit dem überprüft werden kann, ob eine bestimmte Produktbasis ein UPB ist? (dh ist nicht erweiterbar)

Oder ist das Problem NP-vollständig?

Marcin Kotowski
quelle
Ich bin verwirrt ... würde die Standardbasis für H nicht in allen Fällen die UPB-Bedingung erfüllen? Oder gibt es andere Bedingungen, die mir fehlen?
Artem Kaznatcheev
1
@Artem: Die Bedingung, die fehlt, ist, dass die Anzahl der Vektoren streng kleiner ist als die Dimension von . H.1H.n
Peter Shor

Antworten:

7

Ich bin ein wenig verblüfft von Frage (1). Eine nicht erweiterbare Produktbasis existiert in wenn oder wenn und . In all diesen Fällen ist es einfach, einen zu finden.H.1H.2H.nn3n=2dimH.1,dimH.23

Bei Frage (2) entspricht die Frage der Überprüfung, ob sich im Unterraum ein Tensorproduktzustand befindet, der das Komplement des von der Basis überspannten Raums darstellt. Leonid Gurvits hat gezeigt, dass die Überprüfung, ob ein allgemeiner Unterraum einen Tensorproduktzustand enthält, NP-hart ist, daher vermute ich, dass dies auch in diesem Fall schwierig ist.

Peter Shor
quelle
Ja, aber ich bin möglicherweise daran interessiert, so viele inäquivalente UPBs (z. B. in Bezug auf lokale Unitarier) wie möglich zu finden. Die vollständige Klassifizierung ist nur für einfache Fälle wie 2x2x2 bekannt.
Marcin Kotowski
4

Die vollständige Klassifizierung ist auch für einen anderen einfachen Fall 3x3 bekannt. Dies wird zuerst in der Veröffentlichung http://arxiv.org/abs/quant-ph/9808030 behandelt .

Das Ergebnis hängt auch mit der Konstruktion beliebiger 3x3-PPT-Verschränkungszustände von Rang vier zusammen. Siehe das Papier

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

Lin Chen
quelle