
Физики из Мадридского университета Комплутенсе и Университета Южной Калифорнии разработали алгоритм, способный значительно усложнять задачи, необходимые для тестирования производительности квантовых вычислителей. Благодаря подобным системам ученые смогут количественно оценить преимущество квантовых компьютеров над классическими. По словам авторов, случайно сгенерированные задачи удалось усложнить более чем в сто раз. Исследование опубликовано в журнале Physical Review A (препринт), кратко о нем сообщает Physics.Одна из причин интереса к квантовым компьютерам — возможность реализовать принципиально новые алгоритмы, недоступные для классических вычислителей. Это возможно благодаря квантовой природе битов этих компьютеров. Они могут находиться в суперпозиции состояний «ноль» и «единица», которые будут «выпадать» с некоторой вероятностью при измерениях. Теоретики предсказывают, что квантовые алгоритмы в ряде случаев оказываются эффективнее классических. Например, алгоритм Шора гораздо быстрее раскладывает число на простые множители, нежели существующие классические алгоритмы.Еще один класс задач, легко поддающихся решению квантовыми алгоритмами, — задачи Изинга. В этих задачах рассматривается набор из нескольких частиц, каждая из которых может быть в состоянии «+1» или «-1». Энергия каждой частицы зависит от состояния других частиц, с которыми она связана. То, насколько сильны эти связи записано в «условии» задачи. В зависимости от того, положительна или отрицательна сила связи, частицам выгодно иметь одинаковые или разные знаки.Компьютер должен найти такое состояние всех частиц системы, при котором суммарная энергия минимальна. Для классического компьютера эта задача требует масштабного перебора, сложность которого быстро растет с добавлением каждой новой частицы. Кроме того, почти всегда есть некоторое количество локальных минимумов, работающих как ловушки для классических алгоритмов — попав в один из таких минимумов программа может посчитать, что он истинный.Вместе с тем, такие задачи должны решаться достаточно быстро с помощью квантового отжига, реализованного в квантовых вычислителях компании D-wave (подробнее о нем можно прочитать в нашем материале). На практике, из-за небольшого количества кубитов, доступных в современных вычислителях, увидеть эту разницу трудно. Лишь недавно удалось надежно показать преимущество квантового компьютера с использованием специально подобранной задачи. Новая работа предлагает алгоритм, который позволит получать новые задачи, на которых можно будет увидеть разницу между производительностью классических и квантовых компьютеров. Классические алгоритмы решения задач Изинга можно отнести к алгоритмам оптимизации. Алгоритм, предложенный авторами, тоже относится к этому классу, однако вместо оптимизации состояний частиц в задаче он оптимизирует условие задачи, добиваясь максимальной сложности. В качестве параметра сложности ученые выбрали время поиска решения компьютером.
