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

На вході алгоритму маємо (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}$, і функція є збалансованою.

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

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