Algoritmos polinomiais para UPB (bases de produtos não extensíveis)

9

Considere-se um espaço de Hilbert . Uma base de produto não extensível (UPB) é um conjunto de vetores de produtos | v i= | v 1 i| v n i tais que:H=H1Hn|vi=|vi1|vin

a) todos são mutuamente ortogonais|vi

b) não há vetor de produto ortogonal a todos |vi

c) a base não é trivial, ou seja, não abrange H

(tais bases são de interesse em informações quânticas)

Questões:

  1. Existe um algoritmo polinomial (em ) para encontrar UPBs? (observe que, em geral, não há limite superior no tamanho do UPB, portanto, a priori, pode ser exponencial em n )nn

  2. Existe um algoritmo polinomial para verificar se uma determinada base de produto é um UPB? (ou seja, não é extensível)

Ou o problema está completo?

Marcin Kotowski
fonte
Estou confuso ... a base padrão para H satisfaria a condição UPB em todos os casos? Ou há algumas outras condições que estou perdendo.
Artem Kaznatcheev
11
H1Hn

Respostas:

7

H1H2Hnn3n=2dimH1,dimH23

Para a pergunta (2), a pergunta é equivalente a verificar se existe um estado do produto tensorial no subespaço que é o complemento do espaço estendido pela base. Leonid Gurvits mostrou que verificar se um subespaço geral contém um estado de produto tensorial é difícil para NP, então eu suspeito que seja difícil também neste caso.

Peter Shor
fonte
sim, mas estou potencialmente interessado em encontrar o máximo possível de UPBs (por exemplo, com relação a unitaristas locais). A classificação completa é conhecida apenas em casos simples como 2x2x2.
Marcin Kotowski 27/03
4

A classificação completa também é conhecida por outro caso simples 3x3, abordado pela primeira vez no artigo http://arxiv.org/abs/quant-ph/9808030 .

O resultado também está relacionado à construção de estados emaranhados arbitrários de PPT 3x3 do ranking quatro. Veja o artigo

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

Lin Chen
fonte