Google подтвердила частичное превосходство «квантовых компьютеров» D-wave над классическими

Dec 10, 2015 18:58


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




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

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

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



НаукаТехнологии 17:05 09 Дек. 2015 Сложность 5.7 Google подтвердила частичное превосходство «квантовых компьютеров» D-wave над классическими Инженеры компании 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 переменных потребовало более миллиона компьютерных ядер и несколько дней вычислительного времени.

https://nplus1.ru/news/2015/12/09/d-wave-annealing-approved

Микроэлектроника, Вычислительные системы

Previous post Next post
Up