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

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

Алгоритм Дойча — Йожи (іноді алгоритм Дойча — Джози, Шаблон:Lang-en) — квантовий алгоритм, запропонований Девідом Дойчем і Річардом Йожею в 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{⟩}^{\otimes n}|1⟩$. Тобто, останній кубіт знаходиться в стані $|1⟩$, а інші n кубітів — стані $|0⟩$. До кожного кубіту застосовується оператор Адамара для отримання стану:

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

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

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

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

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

Після цього кроку останній кубіт, який є допоміжним, можна відкинути. До кожного з 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⟩=\frac{1}{2^n}\sum _{y=0}^{2^n-1}[\sum _{x=0}^{2^n-1}(-1{)}^{f(x)}(-1{)}^{x\cdot y}]|y⟩,$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Література

• Шаблон:Книга
• Шаблон:Книга

Див. також

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