Algoritmos polinomiales para UPB (Bases de producto no extensibles)

9

Considere un espacio de Hilbert . Una base de producto no extensible (UPB) es un conjunto de vectores de producto | v i= | v 1 i| v n i tal que:H=H1HnorteEl |vyo=El |vyo1El |vyonorte

a) todos son mutuamente ortogonalesEl |vyo

b) no existe un vector de producto ortogonal para todos El |vyo

c) la base no es trivial, es decir, no abarca H

(tales bases son de interés en la información cuántica)

Preguntas:

  1. ¿Existe un algoritmo polinomial (en ) para encontrar UPB? (tenga en cuenta que en general no hay límite superior en el tamaño de UPB, por lo que a priori podría ser exponencial en n )nortenorte

  2. ¿Existe un algoritmo polinómico para verificar si una base de producto dada es un UPB? (es decir, no se puede ampliar)

¿O es el problema NP-completo?

Marcin Kotowski
fuente
Estoy confundido ... ¿la base estándar para H no satisfaría la condición UPB en todos los casos? ¿O hay otras condiciones que me estoy perdiendo?
Artem Kaznatcheev
1
@Artem: la condición que falta es que el número de vectores es estrictamente menor que la dimensión de . H1...Hnorte
Peter Shor

Respuestas:

7

Estoy un poco desconcertado por la pregunta (1). Existe una base de producto no extensible en si n 3 o si n = 2 y dim H 1 , dim H 23 . En todos estos casos, es sencillo encontrar uno.H1H2...Hnortenorte3norte=2oscuroH1,oscuroH23

Para la pregunta (2), la pregunta es equivalente a verificar si hay un estado del producto tensor en el subespacio que es el complemento del espacio abarcado por la base. Leonid Gurvits ha demostrado que verificar si un subespacio general contiene un estado del producto tensor es NP-duro, por lo que sospecho que también es difícil en este caso.

Peter Shor
fuente
Sí, pero estoy potencialmente interesado en encontrar la mayor cantidad posible de UPB no equivalentes (por ejemplo, con respecto a las unidades unitarias locales). La clasificación completa se conoce solo para casos simples como 2x2x2.
Marcin Kotowski