Алгоритм усложнит экзаменационные задачи для квантовых компьютеров

Граф связей, реализованный в компьютерах D-wave. Он отвечает связям между частицами в задаче Изинга.

James King et al. / arXiv.org, 2015

Физики из Мадридского университета Комплутенсе и Университета Южной Калифорнии разработали алгоритм, способный значительно усложнять задачи, необходимые для тестирования производительности квантовых вычислителей. Благодаря подобным системам ученые смогут количественно оценить преимущество квантовых компьютеров над классическими. По словам авторов, случайно сгенерированные задачи удалось усложнить более чем в сто раз. Исследование опубликовано в журнале Physical Review A (препринт), кратко о нем сообщает Physics.

Одна из причин интереса к квантовым компьютерам - возможность реализовать принципиально новые алгоритмы, недоступные для классических вычислителей. Это возможно благодаря квантовой природе битов этих компьютеров. Они могут находиться в суперпозиции состояний «ноль» и «единица», которые будут «выпадать» с некоторой вероятностью при измерениях. Теоретики предсказывают, что квантовые алгоритмы в ряде случаев оказываются эффективнее классических. Например, алгоритм Шора гораздо быстрее раскладывает число на простые множители, нежели существующие классические алгоритмы.

Еще один класс задач, легко поддающихся решению квантовыми алгоритмами, - задачи Изинга. В этих задачах рассматривается набор из нескольких частиц, каждая из которых может быть в состоянии «+1» или «-1». Энергия каждой частицы зависит от состояния других частиц, с которыми она связана. То, насколько сильны эти связи записано в «условии» задачи. В зависимости от того, положительна или отрицательна сила связи, частицам выгодно иметь одинаковые или разные знаки.

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

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

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

Рост сложности задачи с каждым шагом алгоритма. Красные квадраты - принятые изменения в условии задачи

Jeffrey Marshall et al. / ArXiv.org, 2016

За основу бралась случайным образом сгенерированная задача - около 500 связанных между собой частиц с определенными силами связей. На первом этапе алгоритм выбирал несколько связей между частицами и изменял их силу на противоположную. Затем оценивалось время на решение задачи с обновленным условием. Если время оказывалось больше (задача становилась сложнее), то изменения в условии принимались. Если время оказывалось меньше, то изменения принимались с вероятностью, которая сильно уменьшалась с облегчением задачи. Цикл повторялся необходимое число раз. 

Рост средней сложности среди нескольких сотен задач с 500 и 2,5 тысячами шагов усложнения

Jeffrey Marshall et al. / arXiv.org, 2016

В результате ученым удалось увеличить вычислительную сложность задач более чем на два порядка по сравнению со случайным образом сгенерированными. Интересно, что среди прочего авторы получили самую сложную задачу подобного рода из известных (на ее решение классический компьютер на базе Intel Xeon CPU E5-1650 v2 тратил шесть секунд). Сравнение производительности классического компьютера с квантовым вычислителем D-wave Two оказалось не в пользу последнего. По словам физиков, это может быть связано с «классическими причинами». 

Сравнение роста вычислительной сложности для квантового вычислителя (вертикальная ось) и классического (горизонтальная). t_DW - t ^2.48_HFS

Jeffrey Marshall et al. / arXiv.org, 2016

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

Возможность создания квантового компьютера вызывает и опасения - об этом рассказало Агенство национальной безопасности США. К примеру, легкость задачи факторизации (разложения чисел на простые множители) для квантовых систем ставит под угрозу существующие системы шифрования данных. Google уже начал эксперимент по защите данных, передаваемых браузером Chrome, от потенциальных квантовых хакеров. Злоумышленники могут уже сейчас собирать данные в надежде расшифровать их в ближайшем будущем.

Владимир Королёв

Источник: nplus1.ru

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