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

Алгоритм Дойча розв'язує задачу перевірки парності для окремого випадку $n = 1.$ У контексті квантових обчислень ця задача іноді називається задачею Дойча, і в цьому уроці ми будемо дотримуватися такої термінології.

Точніше кажучи, вхідними даними є функція $f:\Sigma \rightarrow \Sigma$ з одного біта в один біт. Існують чотири такі функції:

$$\rule[-10mm]{0mm}{10mm} \begin{array}{c|c} a & f_1(a)\\ \hline 0 & 0\\ 1 & 0 \end{array} \qquad \begin{array}{c|c} a & f_2(a)\\ \hline 0 & 0\\ 1 & 1 \end{array} \qquad \begin{array}{c|c} a & f_3(a)\\ \hline 0 & 1\\ 1 & 0 \end{array} \qquad \begin{array}{c|c} a & f_4(a)\\ \hline 0 & 1\\ 1 & 1 \end{array}$$

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

Задача Дойча

Вхід: функція $f:\{0,1\}\rightarrow\{0,1\}$
Вихід: $0$ якщо $f$ константна, $1$ якщо $f$ збалансована

Якщо розглядати вхідну функцію $f$ у задачі Дойча як доступ до рядка, ми маємо справу з дворозрядним рядком: $f(0)f(1).$

$$\begin{array}{cc} \mathsf{function} & \mathsf{string}\\ \hline f_1 & 00 \\ f_2 & 01 \\ f_3 & 10 \\ f_4 & 11 \end{array}$$

Розглядаючи задачу в такому ракурсі, задача Дойча — це обчислення парності (або, еквівалентно, виключного АБО) двох бітів.

Кожен класичний алгоритм запитів, що правильно розв'язує цю задачу, повинен звертатися до обох бітів: $f(0)$ і $f(1).$ Якщо ми дізнаємось, що $f(1) = 1,$ відповідь все одно може бути $0$ або $1$ залежно від того, чи $f(0) = 1$ або $f(0) = 0$ відповідно. Усі інші випадки аналогічні: знання лише одного з двох бітів не дає жодної інформації про їхню парність. Отже, булева схема, описана в попередньому розділі, є найкращим, чого ми можемо досягти з точки зору кількості запитів, необхідних для розв'язання цієї задачі.

Опис квантової схеми

Алгоритм Дойча розв'язує задачу Дойча за допомогою одного запиту, забезпечуючи тим самим вимірювану перевагу квантових обчислень над класичними. Це може здатися скромною перевагою — один запит проти двох — але з чогось треба починати. Наукові досягнення іноді мають, здавалось би, скромне походження.

Ось квантова схема, що описує алгоритм Дойча:

Аналіз

Щоб проаналізувати алгоритм Дойча, простежимо дію наведеної вище схеми та визначимо стани кубітів у моменти, позначені на цьому рисунку:

Початковий стан — $\vert 1\rangle \vert 0 \rangle,$ і дві операції Адамара з лівого боку схеми перетворюють цей стан на

$$\vert \pi_1 \rangle = \vert - \rangle \vert + \rangle = \frac{1}{2} \bigl( \vert 0\rangle - \vert 1\rangle \bigr) \vert 0\rangle + \frac{1}{2} \bigl( \vert 0\rangle - \vert 1\rangle \bigr) \vert 1\rangle.$$

(Як завжди, ми дотримуємось конвенції Qiskit щодо порядку кубітів, де верхній кубіт стоїть праворуч, а нижній — ліворуч.) Може здатися неінтуїтивним записувати цей добуток стану частково в розгорнутій формі (залишаючи стани кубіта 1 у вигляді множника), але це зробить подальші вирази компактнішими.

Далі виконується гейт $U_f.$ Відповідно до визначення гейта $U_f,$ значення функції $f$ для класичного стану верхнього/правого кубіта накладається за допомогою XOR на нижній/лівий кубіт, що перетворює $\vert \pi_1\rangle$ на стан

$$\vert \pi_2 \rangle = \frac{1}{2} \bigl( \vert 0 \oplus f(0) \rangle - \vert 1 \oplus f(0) \rangle \bigr) \vert 0 \rangle + \frac{1}{2} \bigl( \vert 0 \oplus f(1) \rangle - \vert 1 \oplus f(1) \rangle \bigr) \vert 1 \rangle.$$

Цей вираз можна спростити, зауваживши, що формула

$$\vert 0 \oplus a\rangle - \vert 1 \oplus a\rangle = (-1)^a \bigl( \vert 0\rangle - \vert 1\rangle \bigr)$$

справджується для обох можливих значень $a\in\Sigma.$ Більш явно, два випадки такі:

$$\begin{aligned} \vert 0 \oplus 0\rangle - \vert 1 \oplus 0\rangle & = \vert 0 \rangle - \vert 1 \rangle = (-1)^0 \bigl( \vert 0\rangle - \vert 1\rangle \bigr)\\ \vert 0 \oplus 1\rangle - \vert 1 \oplus 1\rangle & = \vert 1 \rangle - \vert 0\rangle = (-1)^1 \bigl( \vert 0\rangle - \vert 1\rangle \bigr) \end{aligned}$$

Таким чином, $\vert\pi_2\rangle$ можна виразити інакше:

$$\begin{aligned} \vert\pi_2\rangle & = \frac{1}{2} (-1)^{f(0)} \bigl( \vert 0 \rangle - \vert 1 \rangle \bigr) \vert 0 \rangle + \frac{1}{2} (-1)^{f(1)} \bigl( \vert 0 \rangle - \vert 1 \rangle \bigr) \vert 1 \rangle \\ & = \vert - \rangle \biggl( \frac{(-1)^{f(0)} \vert 0\rangle + (-1)^{f(1)} \vert 1\rangle}{\sqrt{2}}\biggr). \end{aligned}$$

Щойно трапилось щось цікаве! Хоча дія гейта $U_f$ на стани стандартного базису залишає верхній/правий кубіт незміненим і накладає значення функції на нижній/лівий кубіт за допомогою XOR, тут ми бачимо, що стан верхнього/правого кубіта змінився (в загальному випадку), тоді як стан нижнього/лівого кубіта залишився незмінним — а саме, перебуває у стані $\vert - \rangle$ до і після виконання гейта $U_f.$ Це явище відоме як відбій фази, і ми скажемо про нього більше дещо пізніше.

З одним остаточним спрощенням — виносячи множник $(-1)^{f(0)}$ за дужки суми — отримуємо такий вираз для стану $\vert\pi_2\rangle$:

$$\begin{aligned} \vert\pi_2\rangle & = (-1)^{f(0)} \vert - \rangle \biggl( \frac{\vert 0\rangle + (-1)^{f(0) \oplus f(1)} \vert 1\rangle}{\sqrt{2}}\biggr) \\ & = \begin{cases} (-1)^{f(0)} \vert - \rangle \vert + \rangle & \text{якщо $f(0) \oplus f(1) = 0$}\\[1mm] (-1)^{f(0)} \vert - \rangle \vert - \rangle & \text{якщо $f(0) \oplus f(1) = 1$}. \end{cases} \end{aligned}$$

Зауважимо, що в цьому виразі маємо $f(0) \oplus f(1)$ у показнику степеня $-1$ на відміну від $f(1) - f(0),$ чого можна було б очікувати з чисто алгебраїчної точки зору, проте результат у обох випадках однаковий. Це пояснюється тим, що значення $(-1)^k$ для будь-якого цілого числа $k$ залежить лише від того, чи $k$ парне, чи непарне.

Застосування останнього гейта Адамара до верхнього кубіта дає стан

$$\vert \pi_3 \rangle = \begin{cases} (-1)^{f(0)} \vert - \rangle \vert 0 \rangle & \text{якщо $f(0) \oplus f(1) = 0$}\\[1mm] (-1)^{f(0)} \vert - \rangle \vert 1 \rangle & \text{якщо $f(0) \oplus f(1) = 1$}, \end{cases}$$

що призводить до правильного результату з імовірністю $1$ при вимірюванні правого/верхнього кубіта.

Додаткові зауваження про відбій фази

Перш ніж рухатися далі, розглянемо наведений вище аналіз під дещо іншим кутом, що може пролити світло на явище відбою фази.

По-перше, зауважимо, що наступна формула справджується для всіх можливих значень бітів $b,c\in\Sigma.$

$$\vert b \oplus c\rangle = X^c \vert b \rangle$$

Це можна перевірити, підставивши два можливих значення $c = 0$ і $c = 1$:

$$\begin{aligned} \vert b \oplus 0 \rangle & = \vert b\rangle = \mathbb{I} \vert b \rangle = X^0 \vert b \rangle\\ \vert b \oplus 1 \rangle & = \vert \neg b\rangle = X \vert b \rangle = X^1 \vert b \rangle. \end{aligned}$$

Використовуючи цю формулу, бачимо, що

$$U_f \bigl(\vert b\rangle \vert a \rangle\bigr) = \vert b \oplus f(a) \rangle \vert a \rangle = \bigl(X^{f(a)}\vert b \rangle\bigr) \vert a \rangle$$

для будь-яких значень бітів $a,b\in\Sigma.$ Оскільки ця формула справджується при $b=0$ і $b=1,$ з лінійності бачимо, що

$$U_f \bigl( \vert \psi \rangle \vert a \rangle \bigr) = \bigl(X^{f(a)}\vert \psi \rangle\bigr) \vert a \rangle$$

для будь-яких векторів стану кубіта $\vert \psi\rangle,$ і тому

$$U_f \bigl( \vert - \rangle \vert a \rangle \bigr) = \bigl(X^{f(a)} \vert - \rangle \bigr) \vert a \rangle = (-1)^{f(a)} \vert - \rangle \vert a \rangle.$$

Ключем до цього є те, що $X\vert - \rangle = - \vert - \rangle.$ Математично кажучи, вектор $\vert - \rangle$ є власним вектором матриці $X$ з власним значенням $-1.$

Ми детальніше розглянемо власні вектори та власні значення в майбутньому уроці про оцінку фази та факторизацію, де явище відбою фази узагальнюється на інші унітарні операції.

Пам'ятаючи, що скаляри вільно проходять через тензорні добутки, знаходимо альтернативний спосіб пояснення того, як операція $U_f$ перетворює $\vert \pi_1\rangle$ на $\vert \pi_2\rangle$ у наведеному вище аналізі:

$$\begin{aligned} \vert \pi_2 \rangle & = U_f \bigl( \vert - \rangle \vert + \rangle \bigr)\\ & = \frac{1}{\sqrt{2}} U_f \bigl(\vert - \rangle \vert 0\rangle \bigr) + \frac{1}{\sqrt{2}} U_f \bigl(\vert - \rangle \vert 1\rangle \bigr)\\ & = \vert - \rangle \biggl( \frac{(-1)^{f(0)} \vert 0\rangle + (-1)^{f(1)} \vert 1\rangle}{\sqrt{2}}\biggr). \end{aligned}$$

Реалізація в Qiskit

Тепер подивимось, як реалізувати алгоритм Дойча в Qiskit. Починаємо з перевірки версії та виконання імпортів, необхідних лише для цієї реалізації. Для реалізацій інших алгоритмів, що слідують далі, ми будемо виконувати потрібні імпорти окремо для більшої модульності.

# Added by doQumentation — required packages for this notebook
!pip install -q qiskit qiskit-aer

from qiskit import __version__

print(__version__)

2.1.1

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator

Спочатку визначимо квантову схему, яка реалізує гейт запиту для однієї з чотирьох функцій $f_1,$ $f_2,$ $f_3$ або $f_4$ з одного біта в один біт, описаних раніше. Як вже зазначалося, реалізація гейтів запиту насправді не є частиною самого алгоритму Дойча; тут ми, по суті, просто показуємо один спосіб підготувати вхідні дані у вигляді схемної реалізації гейта запиту.

def deutsch_function(case: int):
    # This function generates a quantum circuit for one of the 4 functions
    # from one bit to one bit

    if case not in [1, 2, 3, 4]:
        raise ValueError("`case` must be 1, 2, 3, or 4.")

    f = QuantumCircuit(2)
    if case in [2, 3]:
        f.cx(0, 1)
    if case in [3, 4]:
        f.x(1)
    return f

Побачити, як виглядає кожна схема, можна за допомогою методу draw. Ось схема для функції $f_3.$

display(deutsch_function(3).draw(output="mpl"))

Далі створимо власне квантову схему для алгоритму Дойча, замінивши гейт запиту на реалізацію у вигляді квантової схеми, переданої як аргумент. Незабаром ми підставимо одну з чотирьох схем, визначених функцією deutsch_function. Бар'єри включені для наочного розділення реалізації гейта запиту і решти схеми.

def compile_circuit(function: QuantumCircuit):
    # Compiles a circuit for use in Deutsch's algorithm.

    n = function.num_qubits - 1
    qc = QuantumCircuit(n + 1, n)

    qc.x(n)
    qc.h(range(n + 1))

    qc.barrier()
    qc.compose(function, inplace=True)
    qc.barrier()

    qc.h(range(n))
    qc.measure(range(n), range(n))

    return qc

Знову можна побачити, як виглядає схема, за допомогою методу draw.

display(compile_circuit(deutsch_function(3)).draw(output="mpl"))

Нарешті, створимо функцію, яка запускає попередньо визначену схему один раз і виводить відповідний результат: «constant» або «balanced».

def deutsch_algorithm(function: QuantumCircuit):
    # Determine if a one-bit function is constant or balanced.

    qc = compile_circuit(function)

    result = AerSimulator().run(qc, shots=1, memory=True).result()
    measurements = result.get_memory()
    if measurements[0] == "0":
        return "constant"
    return "balanced"

Тепер можна запустити алгоритм Дойча для будь-якої з чотирьох функцій, визначених вище.

f = deutsch_function(3)
display(deutsch_algorithm(f))

'balanced'