Если бы P = NP были правдой, были бы полезны квантовые компьютеры?

29

Предположим, что P = NP верно. Будет ли тогда какое-либо практическое применение для построения квантового компьютера, такое как быстрое решение определенных задач, или же любое такое улучшение будет неуместным, основываясь на том факте, что P = NP верно? Как бы вы охарактеризовали повышение эффективности, которое могло бы произойти, если бы квантовый компьютер мог быть построен в мире, где P = NP, в отличие от мира, в котором P! = NP?

Вот вымышленный пример того, что я ищу:

Если P! = NP, мы видим, что класс сложности ABC равен классу квантовой сложности XYZ ... но если P = NP, класс ABC все равно сворачивается в связанный класс UVW.

(Мотивация: мне любопытно, и я относительно новичок в квантовых вычислениях; перенесите этот вопрос, если он недостаточно продвинут.)

Филип Уайт
источник
9
Мы не знаем, подразумевает ли B Q P = P , так что может быть некоторая проблема в B Q P , которой нет в P, даже если P = N P .... Это также также открытый вопрос, или нет B Q P в P H ....P=NPBQP=PBQPPP=NPBQPPH
Тайфун Пей
4
В основном, класс захватывает «эффективные» квантовые алгоритмы (квантовое полиномиальное время с ограниченной ошибкой). Вот почему формализация вашего вопроса Тайфуном является естественной, например, если P = N P , есть ли проблемы еще не в P , но в B Q P ? И, очевидно, это согласуется с нашими современными знаниями, что это происходит. BQPP=NPPBQP
Усул

Ответы:

30

Статья Скотта Ааронсона « BQP и полиномиальная иерархия » напрямую отвечает на ваш вопрос. Если P = NP, то PH рухнет. Кроме того, если бы BQP были в PH, то в этом случае квантовое ускорение было бы невозможным. С другой стороны, Ааронсон свидетельствует о проблеме с квантовым ускорением вне PH, таким образом, такое ускорение переживет коллапс PH.

Мартин Шварц
источник
10
Фактически сам Ааронсон доказал, что предположение, что он был основан на этой работе, является ложным. См. Scottaaronson.com/papers/glnfalse.pdf
Алекс Грило
5
@AlexGrilo Некоторые из результатов в статье были безоговорочными и до сих пор остаются в силе: существует разрыв оракула между реляционными версиями BQP и PH.
Сашо Николов
8
Пояснение: хотя «Обобщенная гипотеза Линиала-Нисана» оказалась ложной, гипотеза о том, что проблема Фурье-проверки / «связи» отсутствует в PH, все еще остается. Просто нужен другой подход, чтобы доказать это. Кроме того, я могу усилить мой результат, что существует оракул, относительно которого есть проблемы отношения BQP не в BPP ^ PH, чтобы показать, что существует оракул, относительно которого P = NP, но все еще есть проблемы отношения BQP не в BPP , Это простое расширение, но, к сожалению, я его еще не написал.
Скотт Ааронсон
9

Ответ однозначный да. Квантовые компьютеры определенно все еще будут полезны.

Квантовые компьютеры - это не оракулы для BQP, а устройства, которые обрабатывают квантовые состояния и могут общаться с помощью квантовых состояний. Точно так же, как способность делать недетерминированные запросы принципиально более мощна, чем способность делать чисто детерминированные запросы, независимо от статуса P против NP (и в действительности это корень разделения оракула), способность делать квантовые запросы и общаться с использованием квантовых состояний принципиально более мощным, чем чисто классический аналог.

Это приводит к преимуществам в широком спектре приложений

  1. Возможность запрашивать оракулы или внешние базы данных в суперпозиции обеспечивает доказуемое разделение между квантовыми компьютерами и классическими компьютерами с точки зрения сложности запросов.
  2. Существует множество коммуникационных задач, которые видят радикальное снижение стоимости связи, которую использует квантовая связь.
  3. Квантовая обработка информации позволяет теоретически защищать информацию протоколами для решения более широкого круга задач, чем это классически возможно. Конечно, QKD не требует реализации универсального квантового компьютера, но многие протоколы для других задач этого требуют.
  4. Предварительная и последующая обработка больших запутанных квантовых состояний позволяет нарушать предел дробового шума в метрологии, что приводит к более точным измерениям.

Помимо аргументов сложности, есть еще одна практическая причина, чтобы хотеть квантовые компьютеры. В наши дни большая часть данных, обрабатываемых на классических компьютерах, получена при зондировании мира природы (например, с помощью ПЗС в цифровой камере). Однако такие измерения обязательно отбрасывают некоторую информацию о системе, чтобы отобразить результат измерения в виде классической битовой цепочки (например, коллапсирующая пространственная суперпозиция фотонов), и не всегда ясно, какая информация позднее будет считаться наиболее важной, когда Первоначально запись данных. Поэтому разумно полагать, что способность сохранять и обрабатывать квантовые состояния напрямую, а не сворачивать их в некоторой основе перед обработкой, будет становиться все более желательной.

Джо Фитцсимонс
источник
4

Решение практической части.

P=NPO(n2103) это не будет представлять практического интереса для современного оборудования.

O(n1010000) (при этом подразумеваемая константа больше, чем число Skewes)».

Насколько я могу судить, достаточно мощный квантовый компьютер будет представлять практический интерес в этом случае.

Joro
источник
n2103
@SashoNikolov я обратился к практическим . Квантовый компьютер, который эффективно вычисляет 2048-битные целые числа, будет представлять для меня практический интерес на данный момент из-за ключей RSA;).
Joro
Я считаю, что можно получить линейные алгоритмы сортировки по времени с квантовыми компьютерами.
Малыш Дракон
2

Есть исследования в отношении между BQP и полиномиальной иерархией PH. Например, существует проблема, относительно которой BQP не содержится в PH ( http://arxiv.org/abs/0910.4698 ), и гипотеза, которая доказывает тот же результат в нерелятивизированном мире ( http://arxiv.org /abs/1007.0305 ). См. Также проблему BosonSampling, которая заключается в выборке из вероятностного исхода фотонов, выходящих из сети светоделителя, считается классически сложной, хотя ее можно реализовать с помощью довольно простых квантовых систем, которые даже не являются универсальным квантовым компьютером (см. для статьи Ааронсон, Архипов - Вычислительная сложность линейной оптики. Это еще один намек на то, что квантовые вычисления сильнее, чем PH: действительно, если классический компьютер может эффективно решить BosonSampling с оракулом для проблемы PH, тоP#PBPPPH , которые подразумевают многочлен иерархия разрушится.

В заключение, мы не знаем, какова точная мощность квантовых компьютеров, но есть результаты, предполагающие, что BQP может быть вне PH.

неофит
источник