Последствия

33

Как любитель TCS, я читаю некоторые очень вводные материалы по квантовым вычислениям. Вот несколько элементарных кусочков информации, которые я узнал до сих пор:

  1. Известно, что квантовые компьютеры не решают NP-полных задач за полиномиальное время.
  2. «Квантовой магии будет недостаточно» (Беннетт и др., 1997): если вы отбросите структуру проблемы и просто рассмотрите пространство из возможных решений, тогда даже квантовому компьютеру потребуется около 2n шагов, чтобы найти правильный (используя алгоритм Гровера)2n
  3. Если алгоритм квантового полиномиального времени для NP-полной задачи когда-либо найден, он должен каким-то образом использовать структуру задачи (в противном случае, пул 2 будет противоречить).

У меня есть некоторые (основные) вопросы, которые, кажется, еще никто не задавал на этом сайте (возможно, потому что они являются основными). Предположим , что кто - то находит ограниченное ошибка квантового алгоритма полиномиальное время для (или любой другой NP-полной задачи), таким образом , размещение S A T в B Q P , и подразумевая Н Р Б В Р .SATSATBQPNPBQP

Вопросов

  1. Какими будут теоретические последствия такого открытия? Как повлияет общая картина классов сложности? Какие классы станут равными другим?
  2. Подобный результат, по-видимому, предполагает, что квантовые компьютеры обладают превосходящей мощностью по сравнению с классическими компьютерами. Каковы будут последствия такого результата для физики? Будет ли это пролить свет на любую открытую проблему в физике? Изменится ли физика после подобного результата? Повлияет ли на это закон физики, каким мы его знаем?
  3. Возможность (или нет) использовать структуру проблемы достаточно общим (то есть независимым от конкретного экземпляра) способом, по-видимому, является самой сердцевиной вопроса P = NP. Теперь, если найден квантовый алгоритм с полиномиальным временем с ограниченной ошибкой для , и он должен использовать структуру задачи, разве его стратегия структуры-эксплуатации не будет применима и в классическом сценарии? Есть ли доказательства того, что такая эксплуатация структуры может быть возможна для квантовых компьютеров, но невозможна для классических?SAT
Джорджо Камерани
источник
1
@Walther: Я заметил, что вы обновили вопрос, чтобы добавить немного об экспоненциальном ускорении, но, честно говоря, различие между полиномиальным и экспоненциальным ускорениями несколько искусственно, и поэтому я не вижу никакого влияния на физику.
Джо Фитцзимонс
@Joe: я добавил этот бит только для того, чтобы прояснить, что я имел в виду, когда задавал вопрос (то есть, что квант мог бы казаться более мощным, чем классический, в том смысле, что первый мог бы решить NP-полные задачи за полиномиальное время, тогда как последний еще нет или никогда). Но теперь я вижу, что если кто-то читает текущую версию вопроса, а затем читает ваш ответ, он может ошибиться и подумать, что предложение в вашем ответе неверно: вот почему я собираюсь удалить этот бит.
Джорджио Камерани
Извините, я не хотел предлагать вам перефразировать это.
Джо Фицсимонс
@Joe: нет, не волнуйтесь! ;-) На самом деле я не хочу, чтобы вопрос и его ответы были смещены: это могло бы сбить с толку читателей и несправедливо по отношению к тем, кто ответил.
Джорджио Камерани
1
СЭП статья .
Каве

Ответы:

18

Я не собираюсь пытаться ответить на первый вопрос, так как такие люди, как Скотт Ааронсон, Питер Шор или Джон Уотроус, без сомнения, могут дать вам гораздо более исчерпывающий ответ на этот вопрос.

Что касается вопроса 2, важно отметить, что квантовые компьютеры на самом деле более мощные, чем классические компьютеры во многих случаях:

  1. Существует довольно общее ускорение полинома, полученное квантовыми компьютерами по сравнению с классическими компьютерами в целом ряде задач. С точки зрения сложности, это, возможно, несколько менее интересно, чем экспоненциальное ускорение, но это то, что мы можем доказать.
  2. Квантовая коммуникационная сложность часто может сильно отличаться от классической коммуникационной сложности для той же проблемы. Опять же, это то, что можно доказать (см., Например, игру Mermin-GHZ).
  3. Квантовые запросы к оракулам очень часто гораздо мощнее, чем классические запросы к одному и тому же оракулу (см., Например, алгоритм Дойча-Йоша).

Имея это в виду, уже известно, что квантовые компьютеры фундаментально более мощные, чем классические компьютеры. Я думаю, что я был бы прав, говоря, что большинство физиков, которые работают над такими вещами, уже предположили бы, что невозможно найти классический алгоритм для эффективного моделирования каждой квантовой системы, и, таким образом, пока результат, показывающий, что NP содержался в BQP конечно, это было бы удивительно, это не было бы особенно вероятно, чтобы обеспечить прорыв в понимании любого конкретного физического явления. Скорее, это послужило бы более убедительным доказательством того, что квантовую физику трудно симулировать.

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

Исключительно заманчиво сказать, что это будет иметь последствия для адиабатической эволюции квантовых систем (и я думаю, вы могли бы получить ответ или два, предполагая это) и т. Д., Но это было бы неправильно, поскольку они регулируются определенным физическим процессом. и, таким образом, показ того, что в принципе можно решать SAT за полиномиальное время на квантовом компьютере, ничего не скажет об их конкретной эволюции.

Что касается вашего последнего вопроса, у нас уже есть примеры, где структура проблемы используется для получения полиномиального квантового алгоритма, но которые не приводят к такому классическому алгоритму (например, с учетом фактора). Таким образом, что касается нашего текущего понимания, проблема со структурой, пригодной для получения квантового алгоритма за полиномиальное время, не подразумевает, что структура может использоваться для получения классического алгоритма с полиномиальным временем.

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

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

Таким образом, хотя доказательство NP  ⊆  BQP было бы триумфом первого порядка - для всех теоретиков сложности, а не только для теоретиков квантовых вычислений - это предполагает, что существует целая новая теория «физических» моделей вычислений, ожидающих своего открытия. Зачем? Что ж, модели вычислений могут быть истолкованы как модели физики (хотя и узкоспециализированные), а именно: какие вычислительные ресурсы являются физически обоснованными. Один из «лозунгов» квантовых вычислений является то , что Nature isn't classical, [darn] it - так что если вы не можете моделировать квантовую механику на классическом компьютере, что вы можете физически вычислить эффективно почти наверняка более мощным , чем P . И все же, у нас есть доказательства того, что он менее мощный, чем NP; поэтому он должен быть менее мощным, чем BQP , если бы так получилось, что NP  ⊆  BQP .

Итак, доказательство NP  ⊆  BQP дало бы нам трилемму: либо

  1. квантовые схемы могут быть эффективно смоделированы на классическом компьютере, доказывая NP  ⊆  BQP  ⊆  P , тем самым превосходя самые смелые сны или кошмары каждого теоретика;
  2. квантовые схемы не могут быть смоделированы на классическом компьютере, но могут быть построены масштабируемые квантовые компьютеры для решения проблем в NP , что вызывает действительно взрывной интерес к квантовым вычислениям и гарантирует, что физики-экспериментаторы имеют карьерную безопасность в обозримом будущем;
  3. есть еще одна модель вычислений, ожидающая своего открытия, промежуточная между P и BQP по мощности, которая описывает (или, скорее, лучше приближает ) то, что эффективно физически вычислимо.

Я подозреваю, что умные деньги будут на # 3, так же весело, как на # 1 или # 2 с академической точки зрения.

 С извинениями перед Фейнманом, который, я подозреваю, не часто смягчал свои проклятия.

Ниль де Бодрап
источник
1
Несомненно, возможность №2 не является смехотворной возможностью (даже, я должен подчеркнуть, в гипотетической ситуации, когда NPBQP ). Но ваш аргумент также может быть использован для аргументации № 1. Учитывая выбор между тремя вариантами, я выбираю № 3, потому что это наиболее консервативная возможность; но также и потому, что я считаю важным подчеркнуть, что в принципе существуют веские физические и эмпирические причины для предположения о сложности теории.
Ниль де Бёдрап,
3
@Neil: я действительно не согласен. Я не вижу в этом никакой консервативности (скорее, наоборот) утверждать, что квантовая механика ошибочна, потому что квантовые компьютеры были бы мощными. Просто нет доказательств для 1, поэтому аргумент не будет применяться. Существует огромное количество доказательств того, что квантовые вычисления возможны, по крайней мере, в принципе.
Джо Фицсимонс
1
@Joe: Конечно, наши модели QC, насколько мы можем судить, являются отличными абстракциями QM (что само по себе является довольно хорошей теорией). Он также допускает разумные границы ошибок в принципе и надеется на корректируемое исправление ошибок. Но достаточно сложно собрать все части на место, чтобы выполнить бесшумные операции, не так ли? В любом случае, мы говорим здесь о нереальных фактах, а здесь это дурацкое состояние. Можете ли вы сказать мне, что такой результат, как NPBQP , не даст вам ни минуты на паузу, чтобы подумать, что, может быть, есть большой улов, ожидающий для КК где-нибудь?
Ниль де Бёдрап,
2
3
@Neil: На самом деле, 2, похоже, сейчас. Я действительно сомневаюсь, что BQP = P , поэтому квантовые схемы, вероятно, не могут быть эффективно симулированы классически. Тем не менее, есть все признаки того, что мы можем построить квантовые компьютеры (хотя это сложно!).
Джо Фицсимонс