Полиномиальные алгоритмы для UPB (неопределяемые базы продуктов)

9

Рассмотрим гильбертово пространство H=H1Hn, Неописуемая основа продукта (UPB) - это набор векторов продукта|vi=|vi1|vin такой что:

а) все взаимно ортогональны|vi

б) не существует вектора произведения, ортогонального всем|vi

в) базис нетривиален, т.е. не охватываетH

(такие базы представляют интерес в квантовой информации)

Вопросов:

  1. Существует ли полиномиальный алгоритм (по ) для поиска UPB? (обратите внимание, что в целом нет верхней границы для размера UPB, поэтому априори она может быть экспоненциальной по )nn

  2. Существует ли полиномиальный алгоритм для проверки, является ли данный продукт базисом UPB? (т. е. не может быть продлен)

Или проблема NP-полная?

Марчин Котовски
источник
Я в замешательстве ... разве стандартная основа для H не удовлетворяет условию UPB во всех случаях? Или есть какие-то другие условия, которые я пропускаю.
Артем Казнатчеев
1
@Artem: условие, которое отсутствует, состоит в том, что число векторов строго меньше, чем размерность H1Hn,
Питер Шор

Ответы:

7

Я немного озадачен вопросом (1). Неоправданная основа продукта существует вH1H2Hn если n3 или если n=2 а также dimH1,dimH23, Во всех этих случаях легко найти один.

Для вопроса (2) вопрос эквивалентен проверке, существует ли в подпространстве состояние тензорного произведения, которое является дополнением к пространству, натянутому на базис. Леонид Гурвиц показал, что проверка того, содержит ли общее подпространство тензорное произведение, сложна с точки зрения NP, поэтому я подозреваю, что и в этом случае это сложно.

Питер Шор
источник
да, но я потенциально заинтересован в том, чтобы найти как можно больше неэквивалентных (скажем, в отношении местных унитарных) UPB. Полная классификация известна только для простых случаев, таких как 2x2x2.
Марчин Котовски,
4

Полная классификация также известна для другого простого случая 3x3, который впервые рассматривается в статье http://arxiv.org/abs/quant-ph/9808030 .

Результат также связан с построением произвольных запутанных состояний PPT 3x3 ранга четыре. Смотри газету

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

Лин Чен
источник