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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\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 ,$

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

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

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

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

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

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

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

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

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

${\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 ))=$

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

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

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

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

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

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

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

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

Література

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

Див. також

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