Перейти до основного вмісту

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

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

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

af1(a)0010af2(a)0011af3(a)0110af4(a)0111\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}→{0,1}f:\{0,1\}\rightarrow\{0,1\}
Вихід: 00 якщо ff константна, 11 якщо ff збалансована

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

functionstringf100f201f310f411\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(0) і f(1).f(1). Якщо ми дізнаємось, що f(1)=1,f(1) = 1, відповідь все одно може бути 00 або 11 залежно від того, чи f(0)=1f(0) = 1 або f(0)=0f(0) = 0 відповідно. Усі інші випадки аналогічні: знання лише одного з двох бітів не дає жодної інформації про їхню парність. Отже, булева схема, описана в попередньому розділі, є найкращим, чого ми можемо досягти з точки зору кількості запитів, необхідних для розв'язання цієї задачі.

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

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

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

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

Аналіз​

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

Стани під час виконання алгоритму Дойча

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

∣π1⟩=∣−⟩∣+⟩=12(∣0⟩−∣1⟩)∣0⟩+12(∣0⟩−∣1⟩)∣1⟩.\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 у вигляді множника), але це зробить подальші вирази компактнішими.

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

∣π2⟩=12(∣0⊕f(0)⟩−∣1⊕f(0)⟩)∣0⟩+12(∣0⊕f(1)⟩−∣1⊕f(1)⟩)∣1⟩.\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.

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

∣0⊕a⟩−∣1⊕a⟩=(−1)a(∣0⟩−∣1⟩)\vert 0 \oplus a\rangle - \vert 1 \oplus a\rangle = (-1)^a \bigl( \vert 0\rangle - \vert 1\rangle \bigr)

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

∣0⊕0⟩−∣1⊕0⟩=∣0⟩−∣1⟩=(−1)0(∣0⟩−∣1⟩)∣0⊕1⟩−∣1⊕1⟩=∣1⟩−∣0⟩=(−1)1(∣0⟩−∣1⟩)\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}

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

∣π2⟩=12(−1)f(0)(∣0⟩−∣1⟩)∣0⟩+12(−1)f(1)(∣0⟩−∣1⟩)∣1⟩=∣−⟩((−1)f(0)∣0⟩+(−1)f(1)∣1⟩2).\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}

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

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

∣π2⟩=(−1)f(0)∣−⟩(∣0⟩+(−1)f(0)⊕f(1)∣1⟩2)={(−1)f(0)∣−⟩∣+⟩якщо f(0)⊕f(1)=0(−1)f(0)∣−⟩∣−⟩якщо f(0)⊕f(1)=1.\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)⊕f(1)f(0) \oplus f(1) у показнику степеня −1-1 на відміну від f(1)−f(0),f(1) - f(0), чого можна було б очікувати з чисто алгебраїчної точки зору, проте результат у обох випадках однаковий. Це пояснюється тим, що значення (−1)k(-1)^k для будь-якого цілого числа kk залежить лише від того, чи kk парне, чи непарне.

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

∣π3⟩={(−1)f(0)∣−⟩∣0⟩якщо f(0)⊕f(1)=0(−1)f(0)∣−⟩∣1⟩якщо f(0)⊕f(1)=1,\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}

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

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

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

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

∣b⊕c⟩=Xc∣b⟩\vert b \oplus c\rangle = X^c \vert b \rangle

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

∣b⊕0⟩=∣b⟩=I∣b⟩=X0∣b⟩∣b⊕1⟩=∣¬b⟩=X∣b⟩=X1∣b⟩.\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}

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

Uf(∣b⟩∣a⟩)=∣b⊕f(a)⟩∣a⟩=(Xf(a)∣b⟩)∣a⟩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∈Σ.a,b\in\Sigma. Оскільки ця формула справджується при b=0b=0 і b=1,b=1, з лінійності бачимо, що

Uf(∣ψ⟩∣a⟩)=(Xf(a)∣ψ⟩)∣a⟩U_f \bigl( \vert \psi \rangle \vert a \rangle \bigr) = \bigl(X^{f(a)}\vert \psi \rangle\bigr) \vert a \rangle

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

Uf(∣−⟩∣a⟩)=(Xf(a)∣−⟩)∣a⟩=(−1)f(a)∣−⟩∣a⟩.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∣−⟩=−∣−⟩.X\vert - \rangle = - \vert - \rangle. Математично кажучи, вектор ∣−⟩\vert - \rangle є власним вектором матриці XX з власним значенням −1.-1.

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

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

∣π2⟩=Uf(∣−⟩∣+⟩)=12Uf(∣−⟩∣0⟩)+12Uf(∣−⟩∣1⟩)=∣−⟩((−1)f(0)∣0⟩+(−1)f(1)∣1⟩2).\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

Спочатку визначимо квантову схему, яка реалізує гейт запиту для однієї з чотирьох функцій f1,f_1, f2,f_2, f3f_3 або f4f_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. Ось схема для функції f3.f_3.

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

Output of the previous code cell

Далі створимо власне квантову схему для алгоритму Дойча, замінивши гейт запиту на реалізацію у вигляді квантової схеми, переданої як аргумент. Незабаром ми підставимо одну з чотирьох схем, визначених функцією 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"))

Output of the previous code cell

Нарешті, створимо функцію, яка запускає попередньо визначену схему один раз і виводить відповідний результат: «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'