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

Квантова схема алгоритму Дойча — Йожи для функції f, що залежить від n змінних. H — оператор Адамара. U_f — запит фази. Нижній кубіт — допоміжний, що використовується для запиту фази.

Алгоритм Дойча — Йожи (іноді алгоритм Дойча — Джози, англ. Deutsch–Jozsa algorithm) — квантовий алгоритм, запропонований Девідом Дойчем і Річардом Йожею в 1992 році^[1] й вдосконалений Річардом Клівом, Артуром Екертом, К'ярою Маккіавелло й Мішелем Моска в 1998 році^[2]. Цей алгоритм став одним із перших прикладів алгоритму для квантового комп'ютера. Завдяки використанню квантової сплутаності й принципу суперпозиції такий алгоритм має значний приріст швидкості виконання в порівнянні з відповідним класичним аналогом.

Задача Дойча — Йожи полягає у визначенні, чи є функція двійкової змінної ${\displaystyle f(n)}$ константою (тобто, набуває або значення 0, або значення 1 за будь-яких аргументів) або збалансованою (для половини області визначення набуває значення 1, для іншої половини — значення 0). При цьому вважається, що функція a priori є або константою, або збалансованою.

Для розв'язання цієї задачі класичний детермінований алгоритм має виконати в найгіршому випадку ${\displaystyle 2^{n-1}+1}$ обчислень функції ${\displaystyle f}$. Класичний детермінований алгоритм потребує меншого часу, щоб дати правильну відповідь із високою ймовірністю. Але в будь-якому разі для отримання правильної відповіді з одиничною ймовірністю потрібно виконати ${\displaystyle 2^{n-1}+1}$ обчислень. Алгоритм Дойча — Йожи завжди дає правильну відповідь, виконуючи лише одне обчислення функції ${\displaystyle f}$.

Якщо функція ${\displaystyle f}$ незбалансована, то алгоритм може дати відповідь «константа» з деякою ймовірністю, причому при збільшенні різниці між кількістю «0» і «1» збільшується й ця ймовірність^[3].

Алгоритм Дойча — Йожи оснований на схожому алгоритмі (алгоритм Дойча, розроблений Девідом Дойчем у 1985 році), який є частковим випадком першого. В цьому алгоритмі функція ${\displaystyle f(x_{1})}$ є функцією однієї змінної, на відміну від функції багатьох змінних ${\displaystyle f(x_{1},...,x_{n})}$, яка використовується в алгоритмі Дойча — Йожи.

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

На вході алгоритму маємо (n+1)-кубітовий стан ${\displaystyle |0\rangle ^{\otimes n}|1\rangle }$. Тобто, останній кубіт знаходиться в стані ${\displaystyle |1\rangle }$, а інші n кубітів — стані ${\displaystyle |0\rangle }$. До кожного кубіту застосовується оператор Адамара для отримання стану:

${\displaystyle {\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}|x\rangle (|0\rangle -|1\rangle )}$

Функція ${\displaystyle f}$ в алгоритмі грає роль квантового оракула, який перетворює стан ${\displaystyle |x\rangle |y\rangle }$ на стан ${\displaystyle |x\rangle |y\oplus f(x)\rangle }$. Звертання до оракула призводить до наступної зміни стану:

${\displaystyle {\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}|x\rangle (|f(x)\rangle -|1\oplus f(x)\rangle )}$.

Оскільки для кожного ${\displaystyle x}$ функція ${\displaystyle f(x)}$ дорівнює або 0, або 1, то вираз для стану спрощується:

${\displaystyle {\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}|x\rangle (|0\rangle -|1\rangle )}$.

Після цього кроку останній кубіт, який є допоміжним, можна відкинути. До кожного з n кубітів, що залишилися, знову застосовується оператор Адамара, який змінює стан так:

${\displaystyle {\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}\sum _{y=0}^{2^{n}-1}(-1)^{x\cdot y}|y\rangle ={\frac {1}{2^{n}}}\sum _{y=0}^{2^{n}-1}\left[\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}(-1)^{x\cdot y}\right]|y\rangle ,}$

де ${\displaystyle x\cdot y=x_{0}y_{0}\oplus x_{1}y_{1}\oplus \cdots \oplus x_{n-1}y_{n-1}}$ — побітовий добуток.

Зрештою, вимірюючи стан ${\displaystyle |0\rangle ^{\otimes n}}$, отримуємо на виході алгоритму ймовірність

${\displaystyle {\bigg |}{\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}{\bigg |}^{2},}$

яка дорівнює 1, якщо функція ${\displaystyle f}$ — константа, і 0, якщо вона збалансована.

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

Алгоритм Дойча — це частковий випадок алгоритму Дойча — Йожи: тепер функція ${\displaystyle f}$ є функцією однієї змінної. Задачею цього алгоритму є перевірка умови ${\displaystyle f(0)=f(1)}$. Або, що те ж саме, обчислення ${\displaystyle f(0)\oplus f(1)}$ (де ${\displaystyle \oplus }$ — операція додавання за модулем 2, яка може бути представлена вентилем CNOT): якщо цей вираз дорівнює 0, то ${\displaystyle f}$ — константа.

На вході алгоритму маємо двокубітний стан ${\displaystyle |0\rangle |1\rangle }$. До кожного з кубітів застосовується оператор Адамара, що призводить до зміни стану:

${\displaystyle {\frac {1}{2}}(|0\rangle +|1\rangle )(|0\rangle -|1\rangle ).}$

Як і в минулому випадку ${\displaystyle f}$ грає роль квантового оракула, який змінює стан ${\displaystyle |x\rangle |y\rangle }$ на ${\displaystyle |x\rangle |f(x)\oplus y\rangle }$. Звертання до оракула дає:

${\displaystyle {\frac {1}{2}}(|0\rangle (|f(0)\oplus 0\rangle -|f(0)\oplus 1\rangle )+|1\rangle (|f(1)\oplus 0\rangle -|f(1)\oplus 1\rangle ))=}$

${\displaystyle ={\frac {1}{2}}((-1)^{f(0)}|0\rangle (|0\rangle -|1\rangle )+(-1)^{f(1)}|1\rangle (|0\rangle -|1\rangle ))=}$

${\displaystyle =(-1)^{f(0)}{\frac {1}{2}}(|0\rangle +(-1)^{f(0)\oplus f(1)}|1\rangle )(|0\rangle -|1\rangle ).}$

Відкидаючи другий (допоміжний) кубіт і фазу ${\displaystyle (-1)^{f(0)}}$, загострюємо увагу на стані

${\displaystyle {\frac {1}{\sqrt {2}}}(|0\rangle +(-1)^{f(0)\oplus f(1)}|1\rangle ),}$

до якого знову застосовується оператор Адамара:

${\displaystyle {\frac {1}{2}}(|0\rangle +|1\rangle +(-1)^{f(0)\oplus f(1)}|0\rangle -(-1)^{f(0)\oplus f(1)}|1\rangle )=}$

${\displaystyle ={\frac {1}{2}}((1+(-1)^{f(0)\oplus f(1)})|0\rangle +(1-(-1)^{f(0)\oplus f(1)})|1\rangle ).}$

Тепер можна виконати вимірювання стану першого кубіта. Легко бачити, що якщо вимірювання дає 0, то ${\displaystyle f(0)\oplus f(1)=0}$, тобто функція є константою. Якщо ж вимірювання дає 1, то ${\displaystyle f(0)\oplus f(1)=1}$, і функція є збалансованою.

Виноски

1. Deutsch D., Jozsa R. Rapid solutions of problems by quantum computation // Proceedings of the Royal Society of London A. — 1992. — Т. 439. — С. 553. (рос. переклад: Дойч Д., Джозса Р. Быстрое решение задач с помощью квантовых вычислений // Квантовый компьютер и квантовые вычисления (том II). — Ижевск : РХД, 1999. — 288 с.)
2. Cleve R., Ekert A., Macchiavello C., Mosca M. Quantum algorithms revisited // Proceedings of the Royal Society of London A. — 1998. — Т. 454. — С. 339-354.
3. Вялый М. Квантовые алгоритмы (Лекция 2) [Архівовано 26 квітня 2013 у Wayback Machine.].

Література

• Кайе Ф., Лафламм Р., Моска М. Введение в квантовые вычисления. — Ижевск : РХД, 2009. — 360 с.
• Нильсен М., Чанг И. Квантовые вычисления и квантовая информация. — М. : Мир, 2006. — 824 с.

Див. також

• Квантовий алгоритм
• Квантовий комп'ютер