Квантовые вычисления

Алгоритм Дойча-Йожа

1985 год. Дэвид Дойч публикует 'Quantum theory, the Church-Turing principle and the universal quantum computer'. Первый алгоритм, показывающий: квантовый компьютер может решить задачу быстрее любого классического. Один запрос к оракулу вместо $2^{n-1}+1$. При $n=100$: разница в $6 \times 10^{29}$ раз - больше числа атомов в наблюдаемой вселенной.

IBM Quantum Network: алгоритм D-J используется как benchmark для NISQ-устройств - проверка качества реализации гейтов H и оракулов на реальном железе
Google Sycamore: демонстрация квантового превосходства (2019) использует схожие принципы суперпозиции и интерференции в случайных схемах
Алгоритм Шора (факторизация): использует те же building blocks - суперпозиция входов через H + оракул + обратное QFT; D-J - упрощённая модель этой идеи
QML (Quantum Machine Learning): variational quantum circuits используют H-гейты для feature encoding - та же идея суперпозиции входного пространства, что и в D-J

Алгоритм Дойча: один кубит, два запроса vs один

**1985 год. Дэвид Дойч публикует статью 'Quantum theory, the Church-Turing principle and the universal quantum computer'. Первый алгоритм, доказывающий: квантовый компьютер может решить задачу быстрее любого классического.** Задача: дана функция $f: \{0,1\} \to \{0,1\}$. Существует четыре возможных функции - две константных ($f(0)=f(1)=0$ и $f(0)=f(1)=1$) и две сбалансированных ($f(0)=0, f(1)=1$ и $f(0)=1, f(1)=0$). Нужно определить: константная функция или сбалансированная? Классически - минимум два запроса. Алгоритм Дойча - один.

**Трюк алгоритма Дойча** - подать на оракул состояние $|+\rangle|-\rangle = \frac{|0\rangle + |1\rangle}{\sqrt{2}} \otimes \frac{|0\rangle - |1\rangle}{\sqrt{2}}$. Оракул $U_f$ применяется к обоим сразу. Если функция константная - первый кубит после $H$ вернётся в $|0\rangle$. Если сбалансированная - в $|1\rangle$. Одно измерение, один запрос.

В алгоритме Дойча ancilla-кубит инициализируется в $|1\rangle$ и проходит через $H$. Какую роль играет это состояние $|-\rangle$ для ancilla?

Обобщение на n кубитов: экспоненциальное превосходство

**Классическому алгоритму нужно $2^{n-1}+1$ запросов в худшем случае. Квантовому - один. При $n=100$: разница в $6 \times 10^{29}$ раз.** Алгоритм Дойча-Йожа обобщает задачу: дана функция $f: \{0,1\}^n \to \{0,1\}$ с обещанием - функция либо константная (всегда 0 или всегда 1), либо сбалансированная (ровно половина входов даёт 0, половина - 1). Нужно определить: которая из двух? Никаких промежуточных вариантов - обещание гарантировано.

**Шаги алгоритма Дойча-Йожа:** 1. Подготовить $|0\rangle^{\otimes n}|1\rangle$ 2. Применить $H^{\otimes n}$ к первым $n$ кубитам и $H$ к ancilla: получаем суперпозицию всех $2^n$ входов одновременно 3. Применить оракул $U_f$: phase kickback записывает $(-1)^{f(x)}$ в амплитуды 4. Применить $H^{\otimes n}$ снова к первым $n$ кубитам 5. Измерить первые $n$ кубитов: все нули - константная, любой ненулевой бит - сбалансированная

В алгоритме Дойча-Йожа для $n=3$ при измерении получили $|010\rangle$. Что это означает?

Квантовый оракул и phase kickback

**Оракул - это черный ящик, реализующий функцию $f$.** В квантовом случае оракул - унитарная матрица $U_f$, определяемая как $U_f|x\rangle|y\rangle = |x\rangle|y \oplus f(x)\rangle$, где $\oplus$ - XOR. Такая реализация обратима: применив $U_f$ дважды, получаем исходное состояние ($U_f^2 = I$). Это единственный способ реализовать произвольную функцию унитарно - классический output записывается XOR-ом в ancilla, не затирая входные данные.

**Phase kickback** - ключевой трюк: если ancilla $= |-\rangle = \frac{|0\rangle - |1\rangle}{\sqrt{2}}$, то $U_f|x\rangle|-\rangle = (-1)^{f(x)}|x\rangle|-\rangle$. Фаза $(-1)^{f(x)}$ переходит с ancilla на input-регистр. Ancilla не меняется. Именно это позволяет за один вызов $U_f$ обработать все $2^n$ входов суперпозиции.

**Как компилировать классическую функцию в квантовый оракул:** каждое классическое вычисление можно перевести в обратимую схему (reversible circuit) из Toffoli-гейтов, а затем в квантовую. Стоимость - количество гейтов пропорционально сложности классической функции. Оракул не бесплатен: его построение уже предполагает знание функции.

Применяется оракул $U_f$ к состоянию $|x\rangle|-\rangle$. Каков результат при $f(x) = 1$?

Что доказывает Deutsch-Jozsa: оракульная модель

**Deutsch-Jozsa бесполезен практически - никто не ставит вопрос 'константная или сбалансированная функция'. Но алгоритм сделал главное: доказал принцип.** Ускорение существует не в произвольных задачах, а в оракульной модели - где сложность измеряется числом запросов к черному ящику. В этой модели D-J даёт экспоненциальное ускорение над детерминированными классическими алгоритмами. Это точная, математически строгая разница - не приближение, не эвристика.

**Генеалогия квантовых алгоритмов из D-J:** - Bernstein-Vazirani (1993): найти скрытую строку $s$ в $f(x) = s \cdot x \mod 2$ - один запрос квантово против $n$ классически - Simon (1994): найти скрытый период - экспоненциальное ускорение, прямой предшественник алгоритма Шора - Shor (1994): факторизация больших чисел - использует квантовое преобразование Фурье (QFT) как обобщение идей оракульного параллелизма - Grover (1996): поиск в неструктурированных данных за $O(\sqrt{N})$ вместо $O(N)$

**QML и оракульные допущения:** многие заявления о квантовом машинном обучении (Quantum ML) предполагают оракульный доступ к данным - $O(1)$ или $O(\log N)$ на чтение одного элемента. На реальных данных загрузка сама занимает $O(N)$ (QRAM problem). Квантовое ускорение в QML часто существует только при этом нереалистичном допущении.

Квантовый параллелизм означает, что квантовый компьютер проверяет все $2^n$ входов одновременно и получает все ответы сразу

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

После вызова оракула состояние $\sum_x (-1)^{f(x)}|x\rangle$ содержит информацию обо всех входах одновременно - но получить её целиком нельзя. Алгоритм специально конструирует интерференцию так, чтобы из суперпозиции извлечь именно нужный глобальный признак (константность/сбалансированность) детерминированно. Это не параллелизм - это управление фазами.

Алгоритм D-J даёт экспоненциальное ускорение над детерминированным классическим. Почему это не означает, что квантовые компьютеры экспоненциально быстрее для всех задач?