
Инженеры компании Google продемонстрировали существование преимуществ алгоритма квантового отжига, заложенного в «квантовых компьютерах» D-wave, над классическими компьютерами и алгоритмами. Для этого исследователи создали специальную задачу на оптимизацию — поиск минимального значения функции. О результатах рассказывает издание MIT Technology Review, подробнее о тестировании можно прочитать в препринте будущей статьи на arXiv.orgАвторы сравнивали между собой производительность двух алгоритмов — квантового отжига и имитации отжига. Суть этих алгоритмов заключается в воспроизведении физических процессов, происходящих при отжиге и кристаллизации твердых тел. Часть атомов уже заняли свои позиции в кристаллической решетке, а часть, благодаря тепловой энергии еще могут перемещаться в объеме в поиске наиболее энергетически выгодных для себя позиций. С уменьшением температуры тепловое движение замедляется и атомы постепенно занимают локальные минимумы. В алгоритме имитации отжига последовательный поиск максимума или минимума функции определяется случайным процессом перескоков, причем каждый следующий скачок оказывается ближе к искомому значению. Существенным отличием квантового отжига является возможность туннелирования в процессе спуска. Физической аналогией был бы перескок атома, которому не нашлось своего места в кристаллической ячейке, в соседнюю ячейку при температурах, не допускающих такого простым тепловым движением. Это не позволяет алгоритму «застревать» в локальном минимуме.Для сравнения алгоритмов была предложена задача на оптимизацию функции, зависящей от 945 бит переменных (каждая из переменных принимает значения ±1). Авторы сравнивали производительность компьютера D-wave 2X (1152 активных кубита) и обычного компьютера с одним ядром. Тесты показали, что D-wave находит абсолютный минимум с 99-процентной вероятностью до 180 миллионов раз быстрее, чем классические алгоритмы.
