Ква́нтовый алгори́тм, алгоритм для квантового компьютера, т. е. для вычислительного устройства, использующего явления квантовой механики для представления информации и выполнения вычислений. Квантовый алгоритм задаёт последовательность вычислительных операций, которые надо совершить над носителями квантовой информации (например, кубитами) для решения той или иной задачи. За счёт «квантового параллелизма», т. е. способности квантовых носителей информации пребывать в некотором смысле одновременно во множестве разных «базисных» состояний (которые, например, могут соответствовать различным числовым значениям), квантовые алгоритмы оказываются для ряда задач эффективнее классических алгоритмов, т. е. алгоритмов, предназначенных для классического, традиционного компьютера. Более высокая эффективность понимается в том смысле, что число элементарных квантовых вычислительных операций в квантовом алгоритме растёт медленнее с ростом размерности задачи, чем число элементарных вычислительных операций в любых классических алгоритмах, решающих ту же задачу. Как следствие, если будет создан полномасштабный, универсальный и помехоустойчивый квантовый компьютер, то на нём при помощи квантовых алгоритмов можно будет решать определённые задачи, которые невозможно за разумное время решить на классическом компьютере. С этим и связан интерес к квантовым компьютерам и квантовым алгоритмам для них.

Наиболее известными квантовыми алгоритмами являются алгоритм Шора, позволяющий эффективно раскладывать большие целые числа на простые сомножители, и алгоритм Гровера, ускоряющий поиск в неупорядоченном списке.

Основные сведения

Концепция квантовых вычислений зародилась в 1980-е гг. в работах Д. Дойча, Ю. И. Манина и Р. Фейнмана. Первоначальная идея заключалась в том, что симуляцию квантовых физических и химических систем эффективнее проводить на компьютере, который тоже имеет квантовую природу. Задача симуляции остаётся актуальной и сегодня. Позже, также в 1980-е и затем в 1990-е гг., было осознано, что за счёт явления «квантового параллелизма» квантовый компьютер позволяет решать быстрее и задачи, не связанные с физикой или химией.

Широкую известность концепция квантовых вычислений приобрела в 1994 г., когда П. Шор разработал квантовый алгоритм, позволяющий эффективно раскладывать целые числа на простые сомножители. А именно, количество квантовых вычислительных операций растёт пропорционально $n^3,$ где $n$ – число разрядов, которым записывается целое число. Для сравнения, количество вычислительных операций во всех известных алгоритмах для классического (т. е. традиционного, неквантового) компьютера растёт быстрее любой степени $n.$ Есть гипотеза о том, что не существует алгоритма для классического компьютера, который бы решал эту задачу за время, пропорциональное какой бы то ни было, пусть даже и большой, степени $n.$ Это делает разложение больших целых чисел на традиционном компьютере невозможным за разумное время. Эта гипотеза лежит в основе некоторых современных методов защиты информации (т. н. криптографических систем с открытым ключом). Поэтому открытие квантового алгоритма, эффективно решающего эту задачу, привело к новым исследованиям в области разработки квантовых компьютеров и дальнейших квантовых алгоритмов. С фундаментальной стороны алгоритм Шора впервые продемонстрировал следующий феномен: класс сложности задачи изменяется в зависимости от того, на каких физических принципах строится вычислительный процесс (при условии справедливости вышеозначенной гипотезы).

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

Другой широко известный квантовый алгоритм – алгоритм поиска в неупорядоченном списке Л. Гровера (1996). Если нам дан неупорядоченный список из $n$ элементов, в котором необходимо найти требуемый нам единственный элемент, то в классической парадигме надо сделать в среднем порядка $n/2$ обращений к списку. Квантовый алгоритм Гровера позволяет достичь той же цели за порядка $\sqrt n$ обращений.

Можно перечислить некоторые другие известные квантовые алгоритмы: Дойча, Дойча – Джозы, Бернштейна – Вазирани, Саймона. К началу 2020-х гг. разработано множество других квантовых алгоритмов решения различных задач комбинаторной оптимизации, поиска в упорядоченных структурах, задач алгебры и теории чисел, линейной алгебры, дискретной математики, вычислительной математики, симуляции физических и химических систем, машинного обучения, финансовой математики и др.

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

Проблема ошибок в квантовом компьютере

Для построения квантового компьютера требуется решить ряд технологических проблем. Одной из них является поддержание длительной (на время вычисления) квантовой когерентности – специальной согласованности фаз разных базисных состояний носителей квантовой информации. Квантовая когерентность быстро разрушается под воздействием внешних шумов и помех. Разрушение квантовой когерентности делает «квантовый параллелизм» невозможным.

Для квантовых вычислений острее, чем для классических, стоит проблема ошибок. Помимо декогеренции могут быть и ошибки других типов. Если классический бит может находиться только в двух состояниях, то квантовый бит (кубит) может находиться в непрерывном множестве состояний. По этой причине ни одну квантовую вычислительную операцию невозможно выполнить с бесконечной точностью. Чтобы обеспечить помехоустойчивое выполнение квантовых алгоритмов, необходимо использовать квантовые коды, исправляющие ошибки, т. е. проводить вычисления с избыточностью: с бо́льшим числом кубитов и вычислительных преобразований, чем предполагается при идеальной реализации. Трудность состоит в том, что в этих дополнительных кубитах и вычислительных операциях, призванных исправлять ошибки, тоже могут возникать ошибки. Доказана т. н. пороговая теорема: если точность, с которой выполняются вычислительные операции, превышает определённый порог, то реализация помехоустойчивых квантовых вычислений возможна. Неформально говоря, при достаточно точном выполнении отдельных вычислительных операций дополнительные кубиты и вычислительные операции в большей степени исправляют ошибки, чем создают новые. Если же точность выполнения отдельных вычислительных операций недостаточна, то дополнительные кубиты и вычислительные операции в большей степени создают новые ошибки, чем исправляют старые.

Поскольку создать полномасштабный универсальный помехоустойчивый квантовый компьютер пока не удаётся, многие исследователи полагают, что в ближайшем будущем наиболее перспективной будет концепция зашумлённых среднемасштабных квантовых вычислений (англ. Noisy Intermediate-Scale Quantum – NISQ). Эта концепция предполагает решение ограниченного класса задач на доступных к началу 2020-х гг. и в ближайшем будущем квантовых компьютерах. Идёт поиск полезных задач и квантовых алгоритмов для NISQ-устройств, которые обеспечат вычислительное превосходство последних перед традиционными суперкомпьютерами.

Этапы квантового алгоритма. Когерентная суперпозиция

Квантовый алгоритм состоит из трёх больших этапов:

• инициализация квантовых состояний носителей информации;

• собственно квантовое вычисление – проведение последовательности преобразований квантовых состояний;

• измерение конечных квантовых состояний.

Инициализация заключается в создании начальных квантовых состояний. На абстрактном уровне в качестве элементарного носителя квантовой информации может выступать кубит. Он может находиться в одном из двух базисных состояний $0$ и $1,$ которые обозначаются $\ket0$ и $\ket1,$ но также может находиться и в произвольной т. н. суперпозиции этих состояний: $\alpha\ket0+\beta\ket1,$ где $\alpha$ и $\beta$ – комплексные числа, называемые амплитудами вероятностей, удовлетворяющие условию $|\alpha|^2+|\beta|^2=1.$ Числа $|\alpha|^2$ и $|\beta|^2$ имеют смысл вероятностей обнаружить кубит в соответствующем базисном состоянии, если над ним в данный момент будет проведено измерение. Таким образом, (чистое) состояние кубита (как и любого другого носителя квантовой информации) представляется единичным вектором в некотором векторном пространстве над полем комплексных чисел.

О суперпозиции часто говорят как о «когерентной суперпозиции», подчёркивая согласованность амплитуд вероятностей по фазе. Это проявление корпускулярно-волновой природы квантовых объектов. Представим комплексные числа $\alpha$ и $\beta$ в полярной записи: $\alpha=|\alpha|e^{i\theta_\alpha}$ и $\beta=|\beta|e^{i\theta_\beta},$ где $i$ – мнимая единица, а $\theta_\alpha$ и $\theta_\beta$ – вещественные числа, которые и называются в данном контексте фазами. Так, например, состояния $\psi_+=(\ket0+\ket1)/\sqrt2$ и $\psi_-=(\ket0-\ket1)/\sqrt2$ имеют одинаковые значения $|\alpha|^2=1/2$ и $|\beta|^2=1/2.$ Это означает, что в обоих случаях при измерении кубит с равными вероятностями может быть обнаружен как в состоянии $0,$ так и в состоянии $1.$ Однако эти состояния различаются знаком коэффициента при базисном состоянии $\ket1.$ Поэтому, например, $(\psi_++\psi_-)/\sqrt2=\ket0.$ Члены, пропорциональные $\ket1,$ взаимоуничтожились (деструктивная интерференция), а члены, пропорциональные $\ket0,$ сложились (конструктивная интерференция). Такие эффекты невозможны, если мы имеем дело с простым вероятностным распределением, когда бит с равными вероятностями может находиться в одном из двух состояний, но фазы не имеют определённых значений.

Процесс, когда вследствие взаимодействия с окружением фазы теряют определённые значения, называется декогеренцией. В этом процессе когерентная суперпозиция распадается и переходит в простое вероятностное распределение и квантовые вычисления становятся невозможными. В математическом аппарате квантовой механики и квантовой информатики это выражается посредством смешанных состояний – операторов плотности. Состояние когерентной суперпозиции называется чистым состоянием. Поэтому для практической реализации квантовых вычислений принципиально важно сохранение когерентности (когерентной суперпозиции). Для этого необходимо как можно лучше изолировать квантовую систему от внешних шумов, а также использовать квантовые коды, исправляющие ошибки, или другие средства борьбы с воздействием внешнего окружения.

Альтернативно можно представить чистое состояние кубита как точку на единичной сфере в обычном трёхмерном вещественном пространстве. Такое представление называется сферой Блоха. При этом базисным состояниям $\ket0$ и $\ket1$ соответствуют полюсы на этой сфере.

Общий вид чистого состояния двух кубитов описывается комплексной суперпозицией $\alpha_{00}\ket{00}+\alpha_{01}\ket{01}+\alpha_{10}\ket{10}+\alpha_{11}\ket{11},$ где сумма квадратов модулей всех коэффициентов $\alpha_{jk}$ равна единице. Соответственно, состояние общего вида $n$ кубитов есть суперпозиция всех $2^n$ двоичных строк длины $n.$ Можно говорить о том, что квантовая система кубитов в каком-то смысле может одновременно принимать все $2^n$ возможных базисных значений. Число базисных состояний растёт с числом кубитов в геометрической прогрессии. Например, 500 кубитов (т. е. сравнительно небольшое число) могут находиться одновременно в $2^{500}$ базисных состояниях. Это число много больше числа элементарных частиц во Вселенной, много больше возраста Вселенной, выраженной в фемтосекундах и, более того, много больше даже произведения этих двух чисел.

В квантовых вычислениях могут использоваться и многоуровневые носители квантовой информации, которые могут находиться в большем числе базисных состояний: $\ket0,\ket1,\ldots,\ket{d-1}.$ Многоуровневые носители квантовой информации называются кудитами. Аналогично общий вид чистого состояния кудита имеет вид комплексной суперпозиции всех базисных состояний.

Квантовое вычисление заключается в последовательности линейных унитарных преобразований над носителями квантовой информации. Унитарное преобразование сохраняет когерентную суперпозицию, что, как указано выше, принципиально важно для квантовых вычислений. Отдельные унитарные преобразования называются вентилями или гейтами (от англ. gate). При помощи унитарных преобразований можно вычислять любые функции, но этим возможности унитарных преобразований не ограничиваются. Так, например, с их помощью можно создать суперпозицию из значений функции при всех возможных значениях аргументов. Но необходимо уметь воспользоваться этим «квантовым параллелизмом», т. к. при простом измерении природа случайным образом выберет только одно значение. Когерентная суперпозиция играет роль при интерференции. Программирование для квантового компьютера, по сравнению с программированием для классического компьютера, заключается в искусстве построения интерференций, необходимых для наиболее эффективного решения задачи.

Завершается квантовый алгоритм проведением измерения, результат которого считывает оператор квантового компьютера.

Модели квантовых алгоритмов

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

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

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

В адиабатических квантовых вычислениях решение вычислительной задачи кодируется в оператор Гамильтона (оператор энергии) специального вида. Вычисление заключается в медленном переводе исходного простого оператора Гамильтона в оператор Гамильтона требуемого вида.

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

Одностороннее квантовое вычисление, или квантовое вычисление, основанное на измерениях, начинается с создания специального сцепленного состояния – т. н. кластерного, или графового, сцепленного состояния. Например, состояния такого вида возникают в ходе динамики в спиновых цепочках и решётках. Затем квантовое вычисление осуществляется путём последовательных измерений над отдельными кубитами. Поскольку измерение необратимым образом изменяет квантовое состояние (в отличие от унитарных преобразований, которые обратимы), такой способ проведения квантовых вычислений и называется односторонним.

Математически все предложенные парадигмы эквивалентны, но с точки зрения воплощения на практике каждая имеет свои преимущества и ограничения.