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