Рассмотрим гильбертово пространство , Неописуемая основа продукта (UPB) - это набор векторов продукта такой что:
а) все взаимно ортогональны
б) не существует вектора произведения, ортогонального всем
в) базис нетривиален, т.е. не охватывает
(такие базы представляют интерес в квантовой информации)
Вопросов:
Существует ли полиномиальный алгоритм (по ) для поиска UPB? (обратите внимание, что в целом нет верхней границы для размера UPB, поэтому априори она может быть экспоненциальной по )
Существует ли полиномиальный алгоритм для проверки, является ли данный продукт базисом UPB? (т. е. не может быть продлен)
Или проблема NP-полная?
quantum-computing
linear-algebra
quantum-information
Марчин Котовски
источник
источник
Ответы:
Я немного озадачен вопросом (1). Неоправданная основа продукта существует вH1⊗H2⊗…⊗Hn если n≥3 или если n=2 а также dimH1,dimH2≥3 , Во всех этих случаях легко найти один.
Для вопроса (2) вопрос эквивалентен проверке, существует ли в подпространстве состояние тензорного произведения, которое является дополнением к пространству, натянутому на базис. Леонид Гурвиц показал, что проверка того, содержит ли общее подпространство тензорное произведение, сложна с точки зрения NP, поэтому я подозреваю, что и в этом случае это сложно.
источник
Полная классификация также известна для другого простого случая 3x3, который впервые рассматривается в статье http://arxiv.org/abs/quant-ph/9808030 .
Результат также связан с построением произвольных запутанных состояний PPT 3x3 ранга четыре. Смотри газету
http://arxiv.org/abs/1105.3142 .
источник