Станет ли проблема P против NP тривиальной в результате развития универсальных квантовых компьютеров?

25

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

complexity-theory complexity-classes quantum-computing Barte
источник
3
Я почти уверен, что об этом уже спрашивали, но я не могу его найти. Может кто-нибудь еще?
Дэвид Ричерби
6
Полезное чтение в комической форме.
Дэн Брайант,

Ответы:

36

Нет, не будет никаких последствий по нескольким причинам:

  1. Проблема P vs. NP связана с классическим вычислением, а не с квантовым вычислением. Даже если квантовые компьютеры могут решать сложные задачи NP за полиномиальное время (что мы не ожидаем, что они смогут это сделать), все равно может случиться так, что классические компьютеры не смогут решить их за полиномиальное время.

  2. Универсальные квантовые компьютеры, в теоретическом смысле, (насколько мне известно) уже известны. Это всего лишь квантовые аналоги универсальных машин Тьюринга: они могут выполнять любую заданную квантовую «программу».

  3. Как квантовые вычисления, так и проблема P против NP являются теоретическими понятиями. То, что кто-то может построить в физическом мире, не имеет абсолютно никакого отношения к тому, что с ними связано.

Lieuwe Vinkhuijzen дал другую интерпретацию вашего вопроса:

Смогут ли квантовые компьютеры эффективно решать NP-полные задачи?

Ожидаемый ответ: нет. Так что даже в этом смысле физические квантовые компьютеры не позволят нам решать NP-полные задачи по своему желанию.

Юваль Фильмус
источник
17

Никаких последствий не известно в любом случае: классическое моделирование квантовых компьютеров ничего не говорит нам о том, насколько сложны проблемы поиска NP; быстрые решения проблем поиска NP ничего не говорят нам о том, как быстро классические компьютеры можно моделировать классически. Возможны следующие сценарии:

  • P=NP=BQP
  • P=NP⊊BQP
  • P⊊NP=BQP
  • P⊊NP⊊BQP
  • P ⊊ B Q P B Q P N PP⊊NP , но и несопоставимыP⊊BQPBQPNP
  • Проблемы NP требуют классической грубой силы, но решаются быстрыми (хотя и не обязательно полиномиальными) квантовыми алгоритмами.

В блоге одного влиятельного теоретика, работающего в области квантовых компьютеров, Скотта Ааронсона, есть заголовок « Если вы возьмете только одну часть информации из этого блога: квантовые компьютеры не решат сложные задачи поиска мгновенно, просто попробовав все решения одновременно ».

Лиуве Винхуйзен
источник
1
Вы пропустили и , что может быть возможно. P = B Q P ⊊ N PP⊊BQP⊊NPP=BQP⊊NP
Симмонс
2
@ASimmons True! Любая гипотеза, которая учитывает обычные и является допустимой. Если мы введем классы и , которые являются обязательными, чтобы должным образом рассказать историю о том, как квантовые компьютеры в любом случае относятся к вопросу vs , то мы получим экспоненциальное число возможных способов, которыми эти классы могут относиться друг к другу. Надеюсь, что скоро мы подрежем некоторые из этих миров. P ⊆ N P B P P Q M A P N PP⊆BQPP⊆NPBPPQMAPNP
Lieuwe Vinkhuijzen
0

В одном (считающемся маловероятным) сценарии создание универсального квантового компьютера действительно имело бы последствия для проблемы P против NP.

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

В такой ситуации построение универсального квантового компьютера по сравнению только с теоретическим рассуждением об этом имело бы последствия для проблемы P против NP. Это дало бы возможность просто использовать квантовые компьютеры для поиска / поиска доказательства, которое разрешает P против NP, которое затем может быть проверено классическим компьютером.

Однако, как уже упоминалось в других ответах, хотя нет доказательств, разделяющих BQP и NP-complete, в настоящее время имеются доказательства и ожидания того, что квантовые компьютеры не смогут эффективно решать NP-complete задачи.

PPenguin
источник
«Это дало бы возможность просто использовать квантовые компьютеры для поиска / поиска доказательства, которое разрешает P против NP, которое затем может быть проверено классическим компьютером». В общем, автоматическое доказательство считается где-то между неисчислимыми и неразрешимыми. Поскольку КК не является более «мощным» (с точки зрения вычислимости), чем машина Тьюринга, просто «быстрее» в некоторых задачах, я не понимаю, как можно ожидать практических квантовых алгоритмов, помогающих или автоматизирующих доказательство P против NP. Не могли бы вы уточнить это?
Дискретная ящерица