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

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

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

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

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

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

Алгоритм Дойча — Джози оснований на схожому алгоритмі (алгоритм Дойча, розроблений Девідом Дойчем у 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, і функція є збалансованою.

Виноски[ред.ред. код]

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

Література[ред.ред. код]

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

Див. також[ред.ред. код]