- Почти полное решение NP-трудной проблемы отделимости диагональных кутритов Белла(arXiv)
Автор:Кристофер Попп, Беатрикс С. Хисмайр
Аннотация:С вероятностью успеха 95 % мы решаем проблему отделимости состояний диагонального кутрита Белла с положительной частичной транспозицией (PPT). Проблема отделимости, т. е. различения разделяемых и запутанных состояний, обычно не имеет эффективного решения из-за существования связанных запутанных состояний. В отличие от свободных запутанных состояний, которые можно использовать для дистилляции запутанности с помощью локальных операций и классической коммуникации, эти состояния не могут быть обнаружены с помощью критерия Переса-Городецкого или критерия PPT. Мы анализируем большое семейство двудольных состояний кутрита, которые могут быть разделимыми, свободно запутанными или связанными запутанными. Используя геометрическое представление этих состояний в евклидовом пространстве, представлены новые методы, позволяющие эффективно классифицировать отделимые и связанные запутанные диагональные состояния Белла. Кроме того, классификация позволяет точно определить относительные объемы классов сепарабельных, свободных и связанных запутанных состояний. В частности, из всех состояний PPT на диагонали Белла 81,0% ± 0,1% определяются как разделимые, в то время как 13,9 ± 0,1% связаны запутанными и только 5,1 ± 0,1% остаются неклассифицированными. Более того, наши применяемые критерии сравниваются на предмет их эффективности и отношения в качестве детекторов связанной запутанности, что показывает, что ни один критерий не способен обнаружить все связанные запутанные состояния.
2. NP-трудность вычисления геометрической категории PL в размерности 2(arXiv)
Автор:Майкл Скотница, Мартин Тансер
Аннотация: PL-геометрическая категория многогранника P, обозначаемая plgcat(P), обеспечивает естественную верхнюю границу для категории Люстерника — Шнирельмана и определяется как минимальное количество PL-сжимаемых подполиэдров многогранника P, которые покрытие P. В размерности 2 геометрическая категория PL не превосходит ~3. Легко охарактеризовать/распознать 2-многогранники P с plgcat(P)=1. Боргини предоставил частичную характеристику 2-многогранников с plgcat(P)=2. Мы дополняем его результат, показывая, что NP-сложно решить, является ли plgcat(P)≤2. Следовательно, нам не следует ожидать чего-то большего, чем частичная характеристика, по крайней мере, в алгоритмическом смысле. Наша редукция основана на наблюдении, что 2-мерные многогранники P, допускающие оболочечное подразделение, удовлетворяют plgcat(P)≤2, и (нетривиальной) модификации редукции Гоаока, Патака, Патакова, Танцера и Вагнера, показывающей, что оболочечность 2-комплексов является NP-трудным
