Что такое обратный отжиг?

9

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

Процесс обратного отжига, очень кратко, заключается в использовании классических методов, таких как имитация отжига, для нахождения решения и оттачивания в долине с помощью квантового отжига. Если гамильтониан, используемый квантовым отжигом, уже находится в «долине», то, как ему передается решение, в первую очередь - Достигает ли машина D-Wave другой «долины» (лучшее решение?), Используя гамильтониан, переданный в это, во-первых?

user3483902
источник

Ответы:

4

До недавнего времени устройства квантового отжига D-Wave всегда начинали с однородной суперпозиции по всем N кубитов:

                                                Hinitial=|+0|+1...|+N

где |+i=12(|0i+|1i),

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

При исследовании сложных (бурных) энергетических ландшафтов задач оптимизации вам необходимо сбалансировать глобальное исследование пространства состояний с использованием локальных оптимумов. При традиционном (D-Wave) квантовом отжиге мы начинаем с сильного поперечного поля, которое затем постепенно уменьшается, как вы описали в своем вопросе. Таким образом, квантовый отжиг D-Wave выполнял глобальный поиск (из-за большого количества квантовых туннелей) в начале графика отжига, когда поперечное поле сильное. По мере того как поперечное поле становится слабее, поиск становится все более локальным. В отличие от обратного отжига начинается с классического решения, определенного пользователем, затем постепенно увеличивает поперечное поле (обратный отжиг), чтобы затем снова уменьшить поперечное поле (прямой отжиг).

Это вводит новый параметр реверса расстояния, который определяет, насколько далеко вы хотите отжечь назад (насколько сильным должно стать поперечное поле). D-Wave опубликовал следующие два сюжета в этом документе D-Wave :

участки разворота

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

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

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

Марк Фингхут
источник
2

Есть пара статей об алгоритмах, которые могут быть построены с использованием обратного отжига, http://iopscience.iop.org/article/10.1088/1367-2630/aa59c4/meta и https://arxiv.org/abs/1609.05875 ( Стоит отметить предыдущую работу по закрытой системе: https://link.springer.com/article/10.1007/s11128-010-0168-z ). Что касается экспериментальных результатов, я думаю, что единственные, которые были публично видны на момент написания статьи, это официальный документ, приведенный в предыдущем посте. Тем не менее, в конце июня на AQC 2018 будет представлена ​​новая работа ( https://ti.arc.nasa.gov/events/aqc-18/ ), и эти переговоры, как правило, публикуются через несколько месяцев после конференции.

Ник Канцлер
источник