NP-промежуточные задачи с эффективными квантовыми решениями

27

Питер Шор показал, что две из наиболее важных NP-промежуточных задач, факторинг и проблема дискретного логарифмирования, находятся в BQP. Напротив, самый известный квантовый алгоритм для SAT (поиск Гровера) дает только квадратичное улучшение по сравнению с классическим алгоритмом, намекая на то, что NP-полные задачи все еще неразрешимы на квантовых компьютерах. Как указывают Арора и Барак, в BQP есть также проблема, которая, как известно, отсутствует в NP, приводит к предположению, что эти два класса несопоставимы.

Есть ли какие-либо знания / предположения относительно того, почему эти NP-промежуточные проблемы находятся в BQP, но почему SAT (насколько мы знаем) нет? Следуют ли другие NP-промежуточные проблемы этой тенденции? В частности, является ли изоморфизм графов в BQP? (этот не хорошо Google).

Гек Беннетт
источник
4
Я полагаю, что мне следует рассмотреть вопрос о том, почему некоторые проблемы с промежуточным звеном находятся в BQP, а другие неизвестны. Единственное, что я могу сказать с уверенностью, - это то, что проблемы, известные в BQP, относятся к разным классам, и в каждом классе, как правило, в решении используются одни и те же методы. Смотрите две ссылки в моем предыдущем комментарии
Питер Шор
1
Любая проблема, полная BQP, служит примером проблемы в BQP, которая неизвестна в NP.
Робин Котари
2
Относительно алгоритма изоморфизма квантовых графов: tuvalu.santafe.edu/~moore/qip-slides.pdf .
Гек Беннетт
1
BQP-полной? Может кто-нибудь процитировать BQP-полную проблему, пожалуйста?
Cem Say

Ответы:

32

Изоморфизм графов неизвестен в BQP. Была проделана большая работа по его внедрению. Очень интригующее наблюдение состоит в том, что изоморфизм графов может быть решен, если квантовые компьютеры смогут решить неабелеву задачу о скрытой подгруппе для симметрической группы (факторинг и дискретный лог решаются с помощью использование проблемы абелевых скрытых подгрупп, которая в свою очередь решается путем применения квантового преобразования Фурье к абелевым группам).

Один из способов, которым люди пытались решить изоморфизм графов, заключался в применении квантового преобразования Фурье для неабелевых групп. Существуют алгоритмы квантового преобразования Фурье для многих неабелевых групп, включая симметрическую группу. К сожалению, кажется, что может быть невозможно использовать квантовое преобразование Фурье для симметрической группы для решения изоморфизма графа; было написано довольно много статей об этом, которые показывают, что он не работает, учитывая различные предположения о структуре алгоритма. Эти документы, вероятно, то, что вы найдете, когда вы Google.

Питер Шор
источник
1
Я предполагаю, что проблемы, о которых я спрашивал, попадают в категорию 2 (QFT / HSP) в вопросе MathOverflow, и это ключевая общность. Благодарность!
Гек Беннетт
10
Это хороший обзор всего, что сказал Питер. Arxiv.org/abs/0812.0380
Маркос Вильягра
С результатом проф. Бабая об изоморфизме графа, как насчет сложности алгоритма квантового компьютера на GI?
XL _At_Here_There
На данный момент у нас нет квантовых алгоритмов, которые лучше, чем классические алгоритмы.
Питер Шор
20

Фольклорный ответ заключается в том, что факторинг «структурирован» так, как это делают обычные NP-полные проблемы, и именно поэтому мы смогли найти только квантовое преимущество для промежуточных задач.

Возможно, более простая версия вашего вопроса состоит в том, чтобы взглянуть не на вычислительную сложность, а на сложность запроса булевых функций. Здесь мы можем сказать некоторые вещи доказуемо, такие как тот факт, что суперполиномиальные ускорения возможны только для частичных функций (доказано в http://arxiv.org/abs/quant-ph/9802049 ), а не для функций, которые симметричны по своим входам и результаты (доказано в http://arxiv.org/abs/0911.0996 ).

Эти результаты не проливают свет непосредственно на вопрос BQP vs NP, но я думаю, что это значимые шаги для определения, где есть квантовое преимущество.

Арам Харроу
источник