Инженеры компании Google продемонстрировали существование преимуществ алгоритма квантового отжига, заложенного в «квантовых компьютерах» D-wave над классическими компьютерами и алгоритмами. Для этого исследователи создали специальную задачу на оптимизацию — поиск минимального значения функции. О результатах рассказывает издание MIT Technology Review, подробнее о тестировании можно прочитать в препринте будущей статьи на arXiv.org

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

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

Для сравнения алгоритмов была предложена задача на оптимизацию функции, зависящей от 945 бит переменных (каждая из переменных принимает значения ±1). Авторы сравнивали производительность компьютера D-wave 2X (1152 активных кубита) и обычного компьютера с одним ядром. Тесты показали, что D-wave находит абсолютный минимум с 99-процентной вероятностью до 180 миллионов раз быстрее, чем классические алгоритмы.

Сравнение производительности различных алгоритмов. Изображение: Vasil S. Denchev et al. / arXiv.org, 2015

Важно отметить, что максимальное превосходство D-wave наблюдалось на больших количествах переменных, для которых алгоритм имитации отжига дает «сбой». По словам Хартмута Невена, возглавившего исследование, при создании задачи авторы воспользовались своеобразным «багом», позволяющим уменьшить объем вычислений. Тем не менее, результат теста все равно важен, поскольку в классических компьютерах этот «баг» невозможно воспроизвести.

Задача поиска экстремумов функций многих переменных — минимумов и максимумов — на самом деле является задачей оптимизации. Как указывают авторы, для использовавшихся классических компьютеров ее решение в случае 945 переменных потребовало более миллиона компьютерных ядер и несколько дней вычислительного времени.

D-wave — канадский старт-ап, первым заявивший о создании квантового компьютера в 2007 году. Однако, вычислительные системы, создаваемые компанией не являются традиционными квантовыми компьютерами и оптимизированы лишь для алгоритма квантового отжига. К примеру, на них невозможно исполнение алгоритма Шора для факторизации (разложения на простые множители) натуральных чисел, представляющего опасность для банковских систем шифрования. Основой кубитов в D-wave являются сверхпроводящие чипы.

Разработкой квантовых компьютеров одновременно занимаются несколько крупнейших организаций, в том числе, IBM и Google. Не так давно был представлен первый четырехкубитный чип, способный к детекции внутри себя квантовых ошибок.

Автор: Владимир Королёв.