Algoritmul lui Deutsch

Algoritmul lui Deutsch rezolvă problema parității pentru cazul special în care $n = 1.$ În contextul calculului cuantic, această problemă este uneori denumită problema lui Deutsch, iar în această lecție vom folosi această nomenclatură.

Mai precis, intrarea este reprezentată printr-o funcție $f:\Sigma \rightarrow \Sigma$ de la un bit la un bit. Există patru astfel de funcții:

$$\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}$$

Prima și ultima dintre aceste funcții sunt constante, iar celelalte două din mijloc sunt echilibrate, adică cele două valori posibile de ieșire ale funcției apar de același număr de ori pe măsură ce parcurgem toate intrările. Problema lui Deutsch constă în a determina căreia dintre aceste două categorii îi aparține funcția de intrare: constantă sau echilibrată.

Problema lui Deutsch

Intrare: o funcție $f:\{0,1\}\rightarrow\{0,1\}$
Ieșire: $0$ dacă $f$ este constantă, $1$ dacă $f$ este echilibrată

Dacă privim funcția de intrare $f$ din problema lui Deutsch ca pe un acces aleator la un șir de caractere, ne gândim la un șir de doi biți: $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}$$

Privind astfel, problema lui Deutsch constă în calcularea parității (sau, echivalent, a SAU-EXCLUSIV) celor doi biți.

Orice algoritm clasic de interogare care rezolvă corect această problemă trebuie să interogheze ambii biți: $f(0)$ și $f(1).$ Dacă aflăm, de exemplu, că $f(1) = 1,$ răspunsul poate fi în continuare $0$ sau $1,$ în funcție de dacă $f(0) = 1$ sau $f(0) = 0,$ respectiv. Fiecare alt caz este similar; cunoașterea a doar unui singur bit din doi nu oferă nicio informație despre paritatea lor. Prin urmare, circuitul boolean descris în secțiunea anterioară este cel mai bun rezultat posibil din punctul de vedere al numărului de interogări necesare pentru a rezolva această problemă.

Descrierea circuitului cuantic

Algoritmul lui Deutsch rezolvă problema lui Deutsch folosind o singură interogare, oferind astfel un avantaj cuantificabil al calculului cuantic față de cel clasic. Acesta poate părea un avantaj modest — o interogare față de două — dar trebuie să începem de undeva. Progresele științifice au uneori origini aparent modeste.

Iată un circuit cuantic care descrie algoritmul lui Deutsch:

Analiză

Pentru a analiza algoritmul lui Deutsch, vom parcurge acțiunea circuitului de mai sus și vom identifica stările qubiților la momentele sugerate de această figură:

Starea inițială este $\vert 1\rangle \vert 0 \rangle,$ iar cele două operații Hadamard din partea stângă a circuitului transformă această stare în

$$\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.$$

(Ca întotdeauna, urmăm convenția de ordonare a qubiților din Qiskit, care plasează qubit-ul de sus la dreapta și qubit-ul de jos la stânga.) Poate părea neintuitivă scrierea acestei stări produs parțial distribuită (lăsând stările qubit-ului 1 factorizate), dar acest lucru va face expresiile ulterioare mai compacte.

În continuare, se aplică poarta $U_f$. Conform definiției porții $U_f$, valoarea funcției $f$ pentru starea clasică a qubit-ului din dreapta/sus este aplicată prin XOR pe qubit-ul din stânga/jos, transformând $\vert \pi_1\rangle$ în starea

$$\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.$$

Putem simplifica această expresie observând că formula

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

este valabilă pentru ambele valori posibile $a\in\Sigma.$ Mai explicit, cele două cazuri sunt următoarele.

$$\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}$$

Astfel, putem exprima alternativ $\vert\pi_2\rangle$ în felul următor:

$$\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}$$

Tocmai s-a întâmplat ceva interesant! Deși acțiunea porții $U_f$ asupra stărilor din baza standard lasă qubit-ul din dreapta/sus neschimbat și aplică XOR cu valoarea funcției pe qubit-ul din stânga/jos, vedem că starea qubit-ului din dreapta/sus s-a schimbat (în general), în timp ce starea qubit-ului din stânga/jos rămâne aceeași — aflându-se în starea $\vert - \rangle$ atât înainte, cât și după aplicarea porții $U_f$. Acest fenomen este cunoscut sub numele de phase kickback și vom vorbi mai mult despre el în curând.

Cu o ultimă simplificare, și anume extragerea factorului $(-1)^{f(0)}$ în afara sumei, obținem această expresie a stării $\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{if $f(0) \oplus f(1) = 0$}\\[1mm] (-1)^{f(0)} \vert - \rangle \vert - \rangle & \text{if $f(0) \oplus f(1) = 1$}. \end{cases} \end{aligned}$$

Observă că în această expresie avem $f(0) \oplus f(1)$ în exponentul lui $-1$ în loc de $f(1) - f(0),$ ceea ce ne-am putea aștepta dintr-un punct de vedere pur algebric, dar obținem același rezultat în ambele cazuri. Aceasta deoarece valoarea $(-1)^k$ pentru orice număr întreg $k$ depinde doar de dacă $k$ este par sau impar.

Aplicând ultima poartă Hadamard qubit-ului de sus, obținem starea

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

care conduce la rezultatul corect cu probabilitatea $1$ atunci când qubit-ul din dreapta/sus este măsurat.

Observații suplimentare despre phase kickback

Înainte de a continua, să privim analiza de mai sus dintr-un unghi ușor diferit, care poate clarifica fenomenul de phase kickback.

În primul rând, observă că formula de mai jos este valabilă pentru orice alegere de biți $b,c\in\Sigma.$

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

Aceasta poate fi verificată pentru cele două valori posibile $c = 0$ și $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}$$

Folosind această formulă, vedem că

$$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$$

pentru orice alegere de biți $a,b\in\Sigma.$ Deoarece această formulă este adevărată pentru $b=0$ și $b=1,$ vedem prin liniaritate că

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

pentru orice vector de stare qubit $\vert \psi\rangle,$ și prin urmare

$$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.$$

Cheia care face ca asta să funcționeze este că $X\vert - \rangle = - \vert - \rangle.$ În termeni matematici, vectorul $\vert - \rangle$ este un vector propriu al matricei $X$ cu valoarea proprie $-1.$

Vom discuta vectorii proprii și valorile proprii în mai mare detaliu în lecția viitoare despre estimarea fazei și factorizare, unde fenomenul de phase kickback este generalizat la alte operații unitare.

Ținând cont că scalarele se propagă liber prin produse tensoriale, găsim o modalitate alternativă de a explica cum operația $U_f$ transformă $\vert \pi_1\rangle$ în $\vert \pi_2\rangle$ în analiza de mai sus:

$$\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}$$

Implementare în Qiskit

Acum să vedem cum putem implementa algoritmul lui Deutsch în Qiskit. Vom începe cu o verificare a versiunii și apoi vom efectua importurile necesare exclusiv pentru această implementare. Pentru implementările altor algoritmi care urmează, vom efectua importurile necesare separat, pentru o modularitate mai mare.

# 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

Mai întâi vom defini un Circuit cuantic care implementează un query gate pentru una dintre cele patru funcții $f_1,$ $f_2,$ $f_3,$ sau $f_4$ de la un bit la un bit, descrise anterior. Cum am menționat deja, implementarea query gate-urilor nu face cu adevărat parte din algoritmul lui Deutsch în sine; aici arătăm practic o modalitate de a pregăti intrarea, sub forma unei implementări cu circuit a unui query gate.

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

Putem vedea cum arată fiecare circuit folosind metoda draw. Iată circuitul pentru funcția $f_3.$

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

În continuare vom crea circuitul cuantic propriu-zis pentru algoritmul lui Deutsch, înlocuind query gate-ul cu o implementare de circuit cuantic furnizată ca argument. În scurt timp vom introduce unul dintre cele patru circuite definite de funcția deutsch_function pe care am definit-o anterior. Barierele sunt incluse pentru a arăta separarea vizuală dintre implementarea query gate-ului și restul circuitului.

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

Din nou, putem vedea cum arată circuitul folosind metoda draw.

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

În final, vom crea o funcție care rulează circuitul definit anterior o singură dată și afișează rezultatul corespunzător: „constant" sau „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"

Putem rula acum algoritmul lui Deutsch pe oricare dintre cele patru funcții definite mai sus.

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

'balanced'