Курс «Квантовые вычисления». Глава 5. Первые алгоритмы: от Дойча к Саймону

Курс «Квантовые вычисления»

Цели главы. Разобрать алгоритмы Дойча–Йожи, Бернштейна–Вазирани и Саймона. Они решают специально построенные задачи, зато позволяют на простом материале освоить фазовый откат, интерференцию амплитуд и сочетание квантовой подпрограммы с классической постобработкой. Алгоритм Саймона даёт экспоненциальное разделение квантовой и рандомизированной классической сложности запросов и исторически привёл Шора к алгоритмам факторизации и дискретного логарифмирования.

5.1. Модель оракула

Все алгоритмы этой главы формулируются в модели оракула (чёрного ящика): дана функция f, доступная только через вентиль U_f|x⟩|y⟩ = |x⟩|y⊕f(x)⟩ (глава 4), и требуется выяснить некоторое свойство f, сделав как можно меньше обращений. Сложность измеряется числом запросов к оракулу. Модель позволяет строго доказывать разделения: нижние оценки числа запросов обычно доступны там, где нижние оценки полного времени неизвестны. Ограничение модели состоит в том, что оракульное разделение не всегда переносится на функции, заданные явной схемой.

5.2. Фазовый откат

Сначала пусть f — булева функция, а её выходной регистр состоит из одного кубита. Подадим на него не |0⟩, а состояние |−⟩ = (|0⟩ − |1⟩)/√2. Тогда:

U_f|x⟩|−⟩ = (|x⟩|f(x)⟩ − |x⟩|1⊕f(x)⟩)/√2 = (−1)^f(x)|x⟩|−⟩.

Второе равенство проверяется отдельно для f(x) = 0 и f(x) = 1. Целевой кубит не изменился, а значение функции записалось в относительную фазу входного состояния: |x⟩ → (−1)^f(x)|x⟩. Этот манёвр называется фазовым откатом (phase kickback). Фаза недоступна непосредственному измерению в вычислительном базисе, но влияет на последующую интерференцию.

Второй ингредиент — слой Адамаров H^⊗n, переводящий |0…0⟩ в равномерную суперпозицию всех 2ⁿ входов. Оракул когерентно действует согласно f(x) на каждой базисной компоненте; это иногда небрежно называют «вычислением функции на всех входах сразу». Название опасно тем, что все значения нельзя прочитать: последующая интерференция позволяет извлечь лишь специально закодированное глобальное свойство. Схема разделов 5.3–5.5: суперпозиция → фазовый откат → интерференция → измерение.

Для анализа понадобится формула действия H^⊗n на произвольное базисное состояние (проверьте её для n = 1 и n = 2 — упражнение 1):

H^⊗n|x⟩ = 2^−n/2 ∑_y (−1)^x·y|y⟩,

где x·y = x₁y₁ ⊕ … ⊕ x_ny_n — скалярное произведение битовых строк по модулю 2.

5.3. Задача Дойча

Простейший случай: f: {0,1} → {0,1}, требуется узнать, постоянна ли f (f(0) = f(1)) или сбалансирована (f(0) ≠ f(1)). Классически необходимо два запроса — оба значения. Квантово достаточно одного:

1. Приготовить |0⟩|−⟩, применить H к первому кубиту: |+⟩|−⟩.
2. Один вызов U_f (фазовый откат): первый кубит переходит в ((−1)^f(0)|0⟩ + (−1)^f(1)|1⟩)/√2.
3. Это ±|+⟩, если f постоянна, и ±|−⟩, если сбалансирована. Применить H и измерить: исход 0 — постоянна, 1 — сбалансирована. Достоверно, с одного запроса.

Алгоритм не определяет f(0) и f(1) по отдельности: функции 00 и 11 дают один ответ, а 01 и 10 — другой. Извлекается нужное глобальное свойство f(0)⊕f(1), а не таблица значений функции.

5.4. Алгоритм Дойча–Йожи

Обобщение: f: {0,1}ⁿ → {0,1}, обещано, что f либо постоянна, либо сбалансирована (равна 0 ровно на половине входов); выяснить, что именно. Детерминированному классическому алгоритму в худшем случае нужно 2ⁿ⁻¹ + 1 запросов. Квантовая схема — та же, что у Дойча, только шире:

|0⟩^⊗n → H^⊗n → U_f (с |−⟩ в целевом) → H^⊗n → измерение

Проследим состояние входного регистра. После первого слоя Адамаров — равномерная суперпозиция; после фазового отката — 2^−n/2 ∑_x (−1)^f(x)|x⟩; после второго слоя (по формуле из 5.2):

2⁻ⁿ ∑_y [ ∑_x (−1)^{f(x) ⊕ x·y} ] |y⟩.

Амплитуда состояния |0…0⟩ (положим y = 0…0) равна 2⁻ⁿ ∑_x (−1)^f(x): для постоянной f это ±1, поэтому вся вероятность сосредоточена в нуле; для сбалансированной функции слагаемые сокращаются до нуля. Если измерено 0…0, функция постоянна, любой другой результат означает, что она сбалансирована. Ответ достоверен после одного запроса, тогда как детерминированной классической процедуре в худшем случае требуется экспоненциально много запросов.

С рандомизированным классическим алгоритмом сравнение иное. Запросим k случайных различных входов и объявим функцию постоянной, только если все ответы совпали. Для сбалансированной функции вероятность ошибки не превосходит 2^1−k, а для постоянной ошибки нет. Поэтому для заданной постоянной вероятности ошибки достаточно постоянного числа классических запросов. Алгоритм Дойча–Йожи даёт точное разделение с детерминированной классической сложностью, но не экспоненциальное преимущество над рандомизированной при ограниченной ошибке; его основная роль здесь учебная.

5.5. Алгоритм Бернштейна–Вазирани

Та же схема без единого изменения решает другую задачу. Пусть f(x) = s·x для неизвестной строки s; найти s. Классически нужно ровно n запросов (по одному на бит: f(10…0) = s₁ и т.д.). Квантово — один. Подставим f(x) = s·x в состояние перед вторым слоем Адамаров: 2^−n/2 ∑_x (−1)^s·x|x⟩. Но по формуле из 5.2 это в точности H^⊗n|s⟩! Второй слой Адамаров (H — обратный сам себе) превращает состояние ровно в |s⟩, и измерение выдаёт секретную строку целиком, достоверно, с одного запроса.

Для точного ответа разделение здесь равно 1 против n. Рандомизация не уменьшает число классических запросов, если требуется вероятность успеха больше 1/2 для каждого секрета: после q линейных уравнений остаётся не менее 2^n−q совместимых строк. Интерференция собирает нужные линейные характеристики функции в одно измеряемое базисное состояние.

5.6. Алгоритм Саймона

Кульминация главы. Дана f: {0,1}ⁿ → {0,1}ⁿ с обещанием: существует ненулевая строка s, такая что f(x) = f(z) тогда и только тогда, когда z = x или z = x⊕s. Иными словами, f «двухлистна» с периодом s относительно XOR. Найти s.

Классическая сложность: пока не найдены два входа с равными значениями, об s не известно почти ничего; парадокс дней рождения даёт нижнюю оценку Ω(2^n/2) запросов — экспоненциально много, и рандомизация не спасает.

Квантовая часть алгоритма. Два регистра по n кубитов:

1. H^⊗n на первом регистре: 2^−n/2 ∑_x |x⟩|0⟩.
2. Вызов U_f: 2^−n/2 ∑_x |x⟩|f(x)⟩ — регистры запутаны.
3. Измерить второй регистр. Пусть выпало значение f(x₀); по правилу частичного измерения (глава 3) первый регистр коллапсирует в равную суперпозицию всех прообразов этого значения — а их по обещанию ровно два: (|x₀⟩ + |x₀⊕s⟩)/√2.
4. H^⊗n на первом регистре. По формуле из 5.2 амплитуда состояния |y⟩ пропорциональна (−1)^x₀·y(1 + (−1)^s·y): она нулевая при s·y = 1 и ненулевая (одинаковая по модулю) при s·y = 0.
5. Измерение даёт равномерно случайную строку y, удовлетворяющую линейному уравнению s·y = 0.

Классическая часть. Одно уравнение не определяет s, поэтому квантовую подпрограмму повторяют и собирают систему s·y₁ = 0, s·y₂ = 0, …. Когда получены n − 1 линейно независимых уравнений — за O(n) повторов с постоянной вероятностью, — систему решают методом Гаусса над полем из двух элементов. Пространство решений одномерно и состоит из 0 и искомого s. При необходимости успех усиливают дополнительными повторами.

Итого требуется O(n) квантовых запросов и полиномиальная классическая постобработка, тогда как любой рандомизированный классический алгоритм с ограниченной ошибкой требует Ω(2^n/2) запросов. Это экспоненциальное разделение в модели оракула, а не доказательство аналогичного разрыва для произвольных явно заданных функций. Архитектура алгоритма предвосхищает Шора: квантовая подпрограмма извлекает соотношения о скрытой периодичности, а классическая постобработка восстанавливает период. В своей статье Шор отмечал, что пришёл к алгоритму после знакомства с работой Саймона.

Итоги главы

• Модель оракула считает запросы к U_f; разделения в ней доказываются строго, но с оговоркой.
• Фазовый откат: U_f с целевым |−⟩ реализует |x⟩ → (−1)^f(x)|x⟩ — значение функции уходит в фазу и становится доступным интерференции.
• Общая схема: суперпозиция входов → когерентное действие оракула → интерференция → измерение глобального свойства функции. Таблицу всех значений при этом прочитать нельзя.
• Дойч–Йожа: 1 запрос против экспоненты, но лишь у детерминированной классики. Бернштейн–Вазирани: 1 против n у любой классики. Саймон: экспоненциальное разделение и прообраз алгоритма Шора — квантовое извлечение соотношений плюс классическая постобработка.

Упражнения

1. Проверьте формулу H^⊗n|x⟩ = 2^−n/2∑_y(−1)^x·y|y⟩ прямым вычислением для n = 2 и x = 10.
2. Проследите алгоритм Дойча по шагам для всех четырёх возможных функций f и убедитесь в правильности ответа в каждом случае.
3. Выполните алгоритм Бернштейна–Вазирани вручную для n = 3, s = 101: выпишите состояние после каждого шага.
4. В алгоритме Саймона шаг 3 (измерение второго регистра) на самом деле необязателен — алгоритм работает и без него. Объясните, почему: что произойдёт с интерференцией в первом регистре, если второй просто игнорировать? Указание: слагаемые с разными значениями f(x) во втором регистре ортогональны и не интерферируют между собой — суперпозиция «расслаивается» на пары и без измерения.
5. Оцените вероятность того, что n − 1 случайных строк y с условием s·y = 0 линейно независимы. Указание: вероятность того, что очередная строка не попадает в линейную оболочку уже набранных k, равна 1 − 2^k−(n−1); произведение по всем шагам ограничено снизу константой ≈ 0,29.
6. Пусть в задаче Саймона обещание нарушено и f взаимно однозначна (s «равно нулю»). Что будет выдавать квантовая подпрограмма и как алгоритм это обнаружит?

Ответы и указания. 1: H^⊗2|10⟩ = (|00⟩ + |01⟩ − |10⟩ − |11⟩)/2, поскольку 10·y = y₁. 2: функции 00 и 11 дают после оракула соответственно |+⟩ и −|+⟩, а функции 01 и 10 — |−⟩ и −|−⟩; глобальные знаки не влияют на ответ. 3: после отката состояние 2^−3/2∑_x(−1)^x₁⊕x₃|x⟩; финальное измерение даёт 101 с вероятностью 1. 4: после игнорирования второго регистра первый описывается смесью состояний пар (|x⟩+|x⊕s⟩)/√2; QFT над (ℤ₂)ⁿ переводит каждую пару в распределение только на строках y с s·y = 0. 5: вероятность равна ∏_k=0ⁿ⁻²(1−2^k−(n−1)) и стремится примерно к 0,289, поэтому постоянное число серий достаточно для усиления успеха. 6: подпрограмма выдаёт равномерно случайные строки y без ограничений. Если собрано n линейно независимых строк, система имеет только нулевое решение, что достоверно исключает ненулевой период; такое свидетельство появляется за O(n) повторов с постоянной вероятностью, которую можно усилить.

Литература к главе

1. D. Deutsch, R. Jozsa, "Rapid solution of problems by quantum computation," Proc. R. Soc. Lond. A 439, 1992.
2. E. Bernstein, U. Vazirani, "Quantum Complexity Theory," SIAM J. Comput. 26, 1997.
3. D. Simon, "On the Power of Quantum Computation," SIAM J. Comput. 26, 1997.
4. P. Shor, "Algorithms for Quantum Computation: Discrete Logarithms and Factoring," Proc. 35th FOCS, 1994. doi.org/10.1109/SFCS.1994.365700
5. M. Nielsen, I. Chuang, "Quantum Computation and Quantum Information," гл. 1.4.3–1.4.4. Cambridge University Press, 2010.

Предыдущая глава || Содержание курса || Следующая глава