Не только Шор и Гровер: какие квантовые алгоритмы существуют

Кратко о квантовых алгоритмах и их семьях

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

Точкой отсчета в развитии квантовых вычислений считают 90-е. Уже тогда существовали первые алгоритмы для квантовых компьютеров, например, алгоритм Дойча, но они имели, прежде всего, академический интерес. Несколько позже американские ученые Питер Шор и Лов Гровер разработали два разных по сути, но очень ценных с практической точки зрения квантовых алгоритма. Алгоритм Шора убедил мир, что у квантовых технологий есть вполне реальное применение и что квантовый компьютер угрожает современным методам криптографической защиты информации. А идея Гровера указала на то, что с помощью квантов можно осуществить поиск по неструктурированным данным быстрее, чем с помощью классических технологий (а как потом было доказано — с предельно доступным в данной задаче ускорением).

Оба открытия пока не принесли прямых практических экономических результатов. Тем не менее, с них началась эра изучения квантов как прикладного инструмента — и на них основаны другие, более применимые в реальности алгоритмы.

Например, алгоритм Залки — Визнера поможет создать новые лекарства и новые материалы. Алгоритм Амбайниса — проанализировать данные, например, изображения и тексты. Еще одно из наиболее заметных изобретений — алгоритм Харроу — Хассидима — Ллойда, решающий систему линейных уравнений на квантовых компьютерах. Это значительно продвинет обработку больших данных, моделирование сложных систем, а в конечном итоге может стать еще одним шагом на пути к созданию сильного искусственного интеллекта.

Новые идеи квантовых алгоритмов возникают регулярно: большинство перечислены на сайте Quantum Algorithm Zoo, а примеры реализации можно подсмотреть на Github. Помимо США и Китая, большой вклад в этот тренд делает Испания — она лидирует в разработке финансовых алгоритмов благодаря активному движению стартапа Multiverse Computing. У Англии есть успешные решения по распознаванию речи и моделированию химических процессов. Скоро о себе наверняка заявит и Индия — там запускают многочисленные университетские курсы по квантовым направлениям.

Что все-таки тормозит квантовый прогресс

Итак, квантовый алгоритм. Начнем с более понятного слова «алгоритм», под которым подразумевается некоторая последовательность действий, рецепт по получению определенного результата. Слово «квантовый» в этом случае добавляет нам возможность иметь определенные логические операции, которые недоступны в классическом мире. Благодаря явлениям квантовой физики — суперпозиции и запутанности — при помощи логических операций над состояниями квантовых объектов можно создавать сложные квантовые состояния, для описания которых классически потребовалось бы очень много чисел. Например, для описания состояния 50 кубитов требуется в общем случае до 2^50 чисел. Если правильно использовать такое свойство квантовых систем и рассчитать последовательность логических преобразований, а затем реализовать их на квантовом компьютере, можно найти ответ на нужный вопрос в том случае, когда классическому компьютеру потребовалось бы очень много времени и ресурсов памяти.

Казалось бы, создавай себе разные алгоритмы под разные задачи, — и в теории их действительно уже десятки, если не сотни. Но если речь идет о практике и о значительном (т. е. экспоненциальном) ускорении, развитие квантовых алгоритмов упирается в определенные барьеры. И потому появление новых квантовых алгоритмов, способных привести к радикальным изменениям, — скорее, редкость: на каждое десятилетие приходится всего по 5–10 новых интересных квантовых алгоритмов.

Основная сложность связана с тем фактом, что в головах математиков и теоретиков алгоритмы работают на идеальном компьютере. Однако реальные квантовые компьютеры совсем не защищены от ошибок.

Препятствия сводятся к тому, что создать мощную безошибочную квантовую систему очень трудно:

Квантовые объекты очень чувствительны к малейшим изменениям окружающей среды: даже минимальное просачивание квантовой информации в процессе выполнения алгоритма в окружающую среду может привести к искажению итогового ответа. И это при том, что условия для устойчивой работы кубитов в определенных случаях необходимо поддерживать очень специфические: к примеру, температура должна быть близка к абсолютному нулю, то есть соответствовать –273,15 °C.
Шумы влияют на процесс вычислений — из-за постоянного воздействия ошибок количество операций, которое можно реализовать в квантовом алгоритме, сейчас ограничено несколькими десятками, тогда как для выигрыша при решении индустриальных задач требуются тысячи операций.
Пока что не удалось создать нужное количество безошибочных, то есть логических кубитов. К примеру, для расчета рисков компании, работающей на рынке ценных бумаг, требуется минимум 200 логических кубитов, для взлома криптографии — около 6 тыс., а для предсказания стоимости финансовых деривативов в реальном времени — 7,5 тыс. Для еще более сложных задач вроде быстрого взлома сети, биткоина или моделирования новых материалов нужно от нескольких десятков до сотен миллионов. Тогда как на сегодня квантовые устройства не располагают больше, чем единицами защищенных от ошибок кубитов.

Чтобы справиться с квантовыми шумами, ученые предлагают разные методы коррекции, — и они действительно позволяют снизить уровень ошибок в системе. Но значительно уменьшить их эффект на вычисления смогут лишь через определенное время. Прогнозы варьируются: IonQ ставит на 2025 год, а Google рассчитывает на 2029-й.

Как скоро квантовые алгоритмы изменят нашу жизнь

Квантовые вычисления еще не стали массовыми, но уже влияют на уровень жизни — или повлияют в скором времени. К примеру, квантовый вычислитель D-Wave показал возможность в разы ускорить работу морского порта Лос-Анджелеса (пока проводятся исследования на тестовых данных), Daimler с IBM Quantum вот-вот создадут квантовые батареи для электромобилей, а РКЦ и проект QBoard разработали квантовый алгоритм для безопасного захоронения ядерных отходов в интересах Росатома.

Быстрее всего — в течение 2-3 лет — себя проявят вариационные алгоритмы для решения оптимизационных задач, широко применимых практически в любой отрасли. Это гибридный класс вычислений: квантовая часть отвечает за изменения состояния, а классическая часть помогает стабилизировать этот процесс. И, поскольку гибридные модели намного проще в реализации, чем полностью квантовые, для них достаточно мощностей уже существующих квантовых компьютеров. РКЦ и проект QBoard используют квантовые алгоритмы при решении задач химического моделирования в интересах автомобильной индустрии. Однако разработка вариационных алгоритмов сталкивается с целым набором вызовов. На пути к их внедрению всю область квантовых вычислений ждут интересные открытия.

Читать далее:

Найден самый старый кириллический текст из когда-либо найденных

«Уэбб» нашел следы невероятно огромных звезд: они погибли на заре Вселенной

Странные звуки зафиксировали в стратосфере Земли: как ученые пытаются понять их природу

Фото на обложке: Изображение от starline на Freepik