Почему квантовый отжиг не может быть описан моделью затвора?

Это вопрос, на который я был вдохновлен, основываясь на этом вопросе , который отмечает, что квантовый отжиг - это совершенно другая модель для вычислений, чем обычная модель схемы. Я слышал это раньше, и я понимаю, что модель гейта не применима к квантовому отжигу, но я никогда не понимал, почему это так, или как анализировать вычисления, которые может сделать отжигатель. Как я понимаю из нескольких выступлений (некоторые из них самих D-wave!) Тот факт, что отжигатели ограничены определенным гамильтонианом, играет на нем.

d-wave models annealing Эмили Тихурст
источник

Ответы:

Квантовохимический отжиг, например , как машина D-Wave является физическим представлением модели Изинга и как таковые имеет «проблему» гамильтонова форма

H_{P} = \sum_{J = 1}^{n} h_{j} σ_{j}^{z} + \sum_{i, j} J_{i j} σ_{i}^{z} σ_{j}^{z} .

$H_P = \sum_{J=1}^nh_j\sigma_j^z + \sum_{i, j}J_{ij}\sigma_i^z\sigma_j^z.$

По сути, решаемая задача сопоставлена с указанным выше гамильтонианом. Система начинается с гамильтониана и параметра отжига который используется для сопоставления исходного гамильтониана с гамильтонианом задачи с использованием . $H_I = \sum_{J=1}^nh'_j\sigma_j^x$ $s$ $H_I$ $H_P$ $H\left(s\right) = \left(1-s\right)H_I + sH_P$

Поскольку это отжиг, процесс выполняется достаточно медленно, чтобы оставаться вблизи основного состояния системы, в то время как гамильтониан варьируется в зависимости от задачи, используя туннелирование, чтобы оставаться вблизи основного состояния, как описано в ответе Ната .

Теперь, почему это не может быть использовано для описания модели контроля качества ворот? Выше приведена проблема квадратичной бинарной оптимизации без ограничений (QUBO) , которая является NP-трудной ... Действительно, вот статья, отображающая ряд проблем NP в модели Изинга . Любая проблема в NP может быть сопоставлена с любой NP-трудной задачей за полиномиальное время, и целочисленная факторизация действительно является проблемой NP.

$0.2\%$

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

Отредактируйте для пояснения: это означает, что квантовому отжигу (QA) все еще требуется экспоненциальное время (хотя, возможно, и более быстрое экспоненциальное время), чтобы решить проблемы NP, такие как целочисленная факторизация, где универсальный контроль качества дает экспоненциальное ускорение и может решить то же самое проблема в поли времени. Это то, что подразумевает, что QA не может имитировать универсальный QC в поли-времени (иначе это может решить проблемы в поли-времени, которые он не может). Как отмечено в комментариях, это не то же самое, что сказать, что QA не может дать такое же ускорение в других задачах, таких как поиск в базе данных.

Mithrandir24601
источник

Если я правильно понимаю, вы в основном говорите, что квантовый отжиг не может описать квантовую цепь, потому что проблема нахождения минимума произвольного гамильтониана NP-трудна. Я не понимаю это значение. Имитация квантовых цепей также в общем трудно симулировать классически (см., Например, 1610.01808 )

GLS

Кроме того, известно, что некоторые проблемы, решаемые с помощью алгоритмов, выраженных в виде квантовых цепей, также решаются с помощью квантового отжига. Примечательным примером является поиск в базе данных (см., Например, раздел II из 1006.1696 ). Это означает , что в каком - то смысле один может , при некоторых обстоятельствах карты водна схема в задачу д отжига. Разве это также не лишает законной силы ваш третий абзац (в частности, утверждение, что это [нельзя] использовать для описания модели контроля качества гейта )

glS

@glS нет, совсем нет - все равно требуется экспоненциальное время, чтобы найти минимальную (согласно статье во втором комментарии) NP-сложную задачу, так что пока есть проблемы в P (например, поиск в базе данных), где ускорение может быть способным соответствовать задаче универсального контроля качества, решение проблемы NP все еще требует экспоненциального времени, чтобы быть в пределах ограниченной ошибки, где универсальный контроль качества может быть в состоянии решить ту же проблему за многократное время, например, целочисленную факторизацию. Поскольку QA не может этого сделать, QA не может симулировать универсальный QC за многократное время

Mithrandir24601

Хорошо, но это не то, что вы говорите в ответе (или, по крайней мере, не явно). Из ответа видно, что вы говорите, что QA никогда не может быть использовано для решения проблемы, решаемой с помощью модели QC. Это очень отличается от того, чтобы сказать, что QA не может эффективно решить NP-сложную проблему (которая иногда может быть решена квантовой схемой ... хотя я не думаю, что это было доказано, так как мы не знаем, действительно ли Факторинг NP-hard, и большинство других проблем, в которых было показано квантовое преимущество, не являются проблемами решения, насколько мне известно).

GLS

Я сделал правку, которая, надеюсь, прояснит ситуацию. Неизвестно, является ли P = NP или нет, конечно, но это все еще является конкретным примером того, как КК экспоненциально быстрее, согласно современным знаниям

Mithrandir24601

Отжиг - это скорее аналоговая тактика.

Суть в том, что у вас есть какая-то странная функция, которую вы хотите оптимизировать. Итак, вы подпрыгиваете вокруг него. Во-первых, « температура » очень высокая, так что выбранная точка может сильно колебаться. Затем, когда алгоритм « остывает », температура понижается, и подпрыгивание становится менее агрессивным.

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

Вот анимация для имитации отжига (не квантовой):

Но это в значительной степени та же самая концепция для квантового отжига :

Напротив, логика гейта гораздо более цифровая, чем аналоговая. Это связано с кубитами и логическими операциями, а не просто с поиском результата после хаотичного скачка.

натуральный
источник

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

Эмили Тихерст

@EmilyTyhurst Технически любая проблема может быть описана в терминах восхождения на гору. Это также вопрос о том, как хорошо выглядит проблема, когда она описана в формате восхождения на гору. Проблемы, которые ему не подходят, могут быть невероятно безобразными. Для совершенно невыпуклых задач восхождение на гору, в лучшем случае, будет в основном перебором.

Nat

@EmilyTyhurst Hah opps, неправильно прочитал ваш комментарий в обратном направлении. xD Но, да, вы можете проводить отжиг на квантовом компьютере так же, как на классическом компьютере. Затем, я полагаю, будет ли мы называть это « квантовым отжигом » в большей степени вопросом семантики.

Nat

@EmilyTyhurst Да, они определенно все конвертируемы. Я имею в виду, что это похоже на концепцию полноты по Тьюрингу - если у нас есть какая-то полная логика, мы можем построить с ней что угодно.

Nat

Важным моментом квантового отжига является то, что адиабатически изменяется гамильтониан, так что это состояние всегда остается основным состоянием (изменяющегося) гамильтониана, и вы в конечном итоге получаете gs конечного гамильтониана, что является целью протокола , Как это связано с «прыжками», которые вы здесь описываете? Этот документ ( 1006.1696 ) может представлять интерес в этом отношении (в частности, последняя часть второго столбца первой страницы).

GLS