Алгоритм Дойча: один запрос вместо двух

Цельный разобранный пример и связанный вопрос из лекции 24.

Неизвестная функция $f:\{0,1\}\to\{0,1\}$ переводит один бит в один бит. Вычислять её дорого: один запрос стоит один миллион долларов. Нужно с определённостью узнать, одинаковы ли $f(0)$ и $f(1)$, не узнавая обязательно каждое значение отдельно. Классический способ — вычислить оба значения за два запроса. В лекции предлагается получить ответ квантовым способом за один запрос.

В распоряжении есть два кубита и квантовая операция запроса

$$U_f|x\rangle|y\rangle=|x\rangle|y\oplus f(x)\rangle,$$

где $x,y\in\{0,1\}$, а $\oplus$ означает сложение по модулю 2. На суперпозициях операция действует линейно. Связанный вопрос автора: почему нужен второй, вспомогательный кубит? Почему нельзя для любой такой функции использовать только преобразование $|x\rangle\mapsto|f(x)\rangle$?

Проследите предложенный в лекции алгоритм Дойча целиком:

1. Приготовьте $|\psi_{\mathrm{in}}\rangle=|0\rangle|1\rangle$ и примените преобразование Адамара $H$ к обоим кубитам.
2. Один раз примените $U_f$. Запишите состояние и выделите зависимость первого кубита от $f(0)\oplus f(1)$.
3. Перестаньте учитывать второй кубит: далее рассматривается только первый. В каких состояниях он находится при одинаковых и разных значениях функции? Почему измерение сейчас в базисе $|0\rangle,|1\rangle$ ещё не различает эти случаи?
4. Примените $H$ к первому кубиту.
5. Измерьте первый кубит в базисе $|0\rangle,|1\rangle$. Как результат отвечает на исходный вопрос? Сколько раз использована операция запроса?

Для самостоятельного чтения: кубит — система с ортонормированными базисными состояниями $|0\rangle,|1\rangle$. Здесь

$$H|0\rangle=\frac{|0\rangle+|1\rangle}{\sqrt2},\qquad H|1\rangle=\frac{|0\rangle-|1\rangle}{\sqrt2},\qquad H^2=I.$$

Вероятность базисного результата равна квадрату модуля его амплитуды. Унитарная операция сохраняет скалярные произведения. Шаг «не учитывать второй кубит» не означает унитарно стереть его неизвестное состояние: к нему просто больше не обращаются.