Алгоритм Дойча — Джозсы¶

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

¶Постановка задачи

Задача формулируется следующим образом: дана неизвестная булева функция \( f(x) \), определённая на множестве всех двоичных строк длины \( n \) и принимающая значения 0 или 1. Известно, что функция относится к одному из двух классов: она либо константная (возвращает одно и то же значение для всех входов — либо всегда 0, либо всегда 1), либо сбалансированная (возвращает 0 ровно для половины всех возможных входов и 1 — для другой половины). Требуется определить, к какому классу относится функция, используя минимальное число обращений к ней.

Классическому алгоритму в худшем случае требуется \( 2^{n-1} + 1 \) вычислений функции, чтобы гарантированно дать ответ. Квантовый алгоритм Дойча — Джозсы решает ту же задачу за одно обращение к функции, что демонстрирует экспоненциальное ускорение.

¶Описание алгоритма

Алгоритм использует два квантовых регистра: первый содержит \( n \) кубитов (входной регистр), второй — один кубит (рабочий). Работа алгоритма состоит из следующих этапов:

1. Инициализация: все кубиты первого регистра переводятся в состояние \( |0\rangle \), рабочий кубит — в состояние \( |1\rangle \).
2. Применение преобразования Адамара: к каждому кубиту обоих регистров применяется гейт Адамара \( H \). В результате первый регистр переходит в равномерную суперпозицию всех \( 2^n \) возможных входных состояний, а рабочий кубит — в состояние \( \frac{|0\rangle - |1\rangle}{\sqrt{2}} \).
3. Оракул: применяется квантовый оракул, реализующий функцию \( f(x) \). Действие оракула на состояние \( |x\rangle|y\rangle \) задаётся как \( |x\rangle|y \oplus f(x)\rangle \). Благодаря особой подготовке рабочего кубита, фаза состояния \( |x\rangle \) изменяется на множитель \( (-1)^{f(x)} \).
4. Повторное преобразование Адамара: к кубитам первого регистра снова применяется преобразование Адамара.
5. Измерение: производится измерение всех кубитов первого регистра. Если получено состояние \( |0\ldots0\rangle \), функция является константной; если получено любое другое состояние — функция сбалансированная.

¶Математическое обоснование

Ключевой момент алгоритма — интерференция амплитуд вероятностей. После первого преобразования Адамара и действия оракула состояние первого регистра имеет вид:

\[ \frac{1}{\sqrt{2^n}} \sum_{x \in \{0,1\}^n} (-1)^{f(x)} |x\rangle \]

После второго преобразования Адамара амплитуда состояния \( |0\ldots0\rangle \) оказывается пропорциональна сумме \( \sum_{x} (-1)^{f(x)} \). Для константной функции эта сумма равна \( \pm 2^n \), что соответствует вероятности измерения \( |0\ldots0\rangle \), равной 1. Для сбалансированной функции сумма равна нулю, поэтому вероятность получить \( |0\ldots0\rangle \) равна нулю, и измерение даст ненулевое состояние.

¶Частный случай: алгоритм Дойча

Изначально в 1985 году Дэвид Дойч предложил более простую версию задачи для случая \( n = 1 \), где функция определена на одном бите. В этой версии требовалось определить, является ли функция константной или сбалансированной, и классический алгоритм требовал двух обращений к функции. Первоначальный алгоритм Дойча также требовал двух обращений. В 1992 году Дойч и Джозса усовершенствовали его, предложив версию с одним обращением и обобщив на случай произвольного \( n \). Позднее, в 1998 году, Ричард Кливе и др. модифицировали алгоритм так, чтобы он работал без рабочего кубита, используя только \( n \) кубитов.

¶Значение и ограничения

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

¶Экспериментальная реализация

Алгоритм Дойча — Джозсы был реализован экспериментально на различных физических платформах, включая ядерный магнитный резонанс, ионные ловушки и сверхпроводниковые кубиты. Первая экспериментальная демонстрация была проведена в 1998 году группой Джонатана Джонса на ядерном магнитном резонансе для случая \( n = 2 \). В последующие годы алгоритм воспроизводился на квантовых процессорах IBM, Rigetti и других, что подтверждает корректность теоретических выкладок.

¶Источники

• Дойч Д., Джозса Р. «Rapid solution of problems by quantum computation» // Proceedings of the Royal Society of London A, 1992.
• Нильсен М., Чанг И. «Квантовые вычисления и квантовая информация», 2006.
• Кливе Р., Экерт А., Маччиавелло К., Моска М. «Quantum algorithms revisited» // Proceedings of the Royal Society of London A, 1998.