Разгадка квантовых отжигов с использованием классической твердости

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

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

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

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

На правых графиках показан главный результат работы: зависимость типичного времени поиска основного состояния t_s от трудности задачи ?. Для классического алгоритма симулированного отжига (оранжевая линия) время нахождения решения масштабируется с трудностью задачи как t_s ~ ?^1.6, а для квантового отжига на 512-кубитной машине D-Wave (красная линия) t_s ~ ?^1.73. То есть на квантовой машине время решения растет быстрее с трудностью задачи, чем на классической! Хотя, казалось бы, квантовое превосходство должно подразумевать ровно обратное.

Авторы не спешат сильно ругать компьютер D-Wave и обвинять его в отсутствии квантовой когерентности и предполагают, что причина его тормознутости, во первых, в наличии реальной физической температуры кубитов, мешающей достичь квантового основного состояния, а во-вторых, в неидеальности контроля над чипом, приводящей к случайным отклонениям параметров реальных межкубитных взаимодействий от тех, которые мы пытаемся установить внешним контролем.

Источник: www.nature.com

Комментарии: