Algorytm Deutscha

Algorytm Deutscha rozwiązuje problem parzystości dla szczególnego przypadku, gdy $n = 1.$ W kontekście obliczeń kwantowych problem ten jest czasem nazywany problemem Deutscha i takiej nomenklatury będziemy się trzymać w tej lekcji.

Dokładnie rzecz ujmując, dane wejściowe są reprezentowane przez funkcję $f:\Sigma \rightarrow \Sigma$ z jednego bitu do jednego bitu. Istnieją cztery takie funkcje:

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

Pierwsza i ostatnia z tych funkcji są stałe, a środkowe dwie są zrównoważone (ang. balanced), co oznacza, że dwie możliwe wartości wyjściowe funkcji występują tyle samo razy, gdy przebiegamy po wszystkich wejściach. Problem Deutscha polega na ustaleniu, do której z tych dwóch kategorii należy dana funkcja wejściowa: stała czy zrównoważona.

Problem Deutscha

Wejście: funkcja $f:\{0,1\}\rightarrow\{0,1\}$
Wyjście: $0$ jeśli $f$ jest stała, $1$ jeśli $f$ jest zrównoważona

Jeśli potraktujemy funkcję wejściową $f$ w problemie Deutscha jako reprezentację losowego dostępu do ciągu znaków, myślimy o dwubitowym ciągu: $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}$$

Patrząc na to w ten sposób, problem Deutscha sprowadza się do obliczenia parzystości (lub, co równoważne, XOR) dwóch bitów.

Każdy klasyczny algorytm z zapytaniami, który poprawnie rozwiązuje ten problem, musi zapytać oba bity: $f(0)$ i $f(1).$ Jeśli na przykład dowiemy się, że $f(1) = 1,$ odpowiedź nadal może wynosić $0$ lub $1$, zależnie od tego, czy $f(0) = 1$, czy $f(0) = 0.$ Każdy inny przypadek jest podobny; znajomość tylko jednego z dwóch bitów nie dostarcza żadnej informacji o ich parzystości. Tak więc circuit logiczny opisany w poprzedniej sekcji jest najlepszym, co możemy osiągnąć pod względem liczby zapytań potrzebnych do rozwiązania tego problemu.

Opis Circuit kwantowego

Algorytm Deutscha rozwiązuje problem Deutscha za pomocą jednego zapytania, zapewniając tym samym wymierną przewagę obliczeń kwantowych nad klasycznymi. Może to być skromna przewaga — jedno zapytanie zamiast dwóch — ale od czegoś trzeba zacząć. Postęp naukowy czasem rodzi się z pozornie skromnych początków.

Oto circuit kwantowy opisujący algorytm Deutscha:

Analiza

Aby przeanalizować algorytm Deutscha, prześledzmy działanie powyższego układu i określmy stany qubitów w momentach zaznaczonych na poniższym rysunku:

Stan początkowy to $\vert 1\rangle \vert 0 \rangle,$ a dwie operacje Hadamarda po lewej stronie układu przekształcają go do postaci

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

(Jak zawsze, stosujemy tu konwencję kolejności qubitów przyjętą w Qiskit, gdzie górny qubit jest po prawej, a dolny po lewej.) Zapisanie tego stanu iloczynowego częściowo w postaci rozłożonej (z wyciągniętymi stanami qubitu 1) może wydawać się nieintuicyjne, jednak dzięki temu późniejsze wyrażenia będą bardziej zwięzłe.

Następnie wykonywana jest bramka $U_f$. Zgodnie z definicją bramki $U_f$, wartość funkcji $f$ dla klasycznego stanu górnego/prawego qubitu jest XORowana na dolny/lewy qubit, co przekształca $\vert \pi_1\rangle$ w stan

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

Możemy uprościć to wyrażenie, korzystając z obserwacji, że wzór

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

zachodzi dla obu możliwych wartości $a\in\Sigma.$ Oba przypadki wyglądają następująco:

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

Możemy zatem zapisać $\vert\pi_2\rangle$ w następujący sposób:

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

Właśnie stało się coś interesującego! Mimo że działanie bramki $U_f$ na stany bazy standardowej pozostawia górny/prawy qubit bez zmian i XORuje wartość funkcji na dolny/lewy qubit, tutaj widzimy, że stan górnego/prawego qubitu zmienił się (ogólnie rzecz biorąc), podczas gdy stan dolnego/lewego qubitu pozostał taki sam — przed i po zastosowaniu bramki $U_f$ jest on w stanie $\vert - \rangle$. Zjawisko to znane jest jako phase kickback i wrócimy do niego niebawem.

Po ostatnim uproszczeniu, polegającym na wyciągnięciu czynnika $(-1)^{f(0)}$ przed nawias, otrzymujemy następujące wyrażenie na stan $\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}$$

Zauważ, że w tym wyrażeniu w wykładniku $-1$ mamy $f(0) \oplus f(1)$, a nie $f(1) - f(0),$ czego moglibyśmy się spodziewać patrząc czysto algebraicznie — jednak wynik jest w obu przypadkach identyczny. Wynika to z tego, że wartość $(-1)^k$ dla dowolnej liczby całkowitej $k$ zależy wyłącznie od tego, czy $k$ jest parzyste, czy nieparzyste.

Po zastosowaniu ostatniej bramki Hadamarda do górnego qubitu otrzymujemy stan

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

który przy pomiarze prawego/górnego qubitu daje poprawny wynik z prawdopodobieństwem $1$.

Dalsze uwagi na temat phase kickback

Zanim przejdziemy dalej, przyjrzyjmy się powyższej analizie z nieco innego kąta — może to rzucić nieco światła na zjawisko phase kickback.

Na początku zauważmy, że poniższy wzór działa dla wszystkich możliwych wartości bitów $b,c\in\Sigma.$

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

Można to sprawdzić, podstawiając dwie możliwe wartości $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}$$

Korzystając z tego wzoru, widzimy, że

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

dla dowolnych bitów $a,b\in\Sigma.$ Ponieważ ten wzór jest prawdziwy dla $b=0$ i $b=1,$ widzimy na mocy liniowości, że

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

dla wszystkich wektorów stanu qubit $\vert \psi\rangle,$ a zatem

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

Kluczem, który sprawia, że to działa, jest fakt, że $X\vert - \rangle = - \vert - \rangle.$ W języku matematyki wektor $\vert - \rangle$ jest wektorem własnym macierzy $X$ o wartości własnej $-1.$

Wektory własne i wartości własne omówimy szczegółowo w nadchodzącej lekcji poświęconej estymacji fazy i faktoryzacji, gdzie zjawisko phase kickback zostanie uogólnione na inne operacje unitarne.

Mając na uwadze, że skalary swobodnie „przepływają" przez iloczyny tensorowe, znajdujemy alternatywny sposób uzasadnienia, jak operacja $U_f$ przekształca $\vert \pi_1\rangle$ w $\vert \pi_2\rangle$ w powyższej analizie:

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

Implementacja w Qiskit

Zobaczmy teraz, jak możemy zaimplementować algorytm Deutscha w Qiskit. Zaczniemy od sprawdzenia wersji, a następnie wykonamy importy wymagane wyłącznie na potrzeby tej implementacji. W przypadku implementacji pozostałych algorytmów, które pojawią się później, będziemy wykonywać wymagane importy osobno, dla większej modularności.

# 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

Najpierw zdefiniujemy Circuit kwantowy implementujący query Gate dla jednej z czterech funkcji $f_1,$ $f_2,$ $f_3$ lub $f_4$ z jednego bitu na jeden bit, opisanych wcześniej. Jak już wspomnieliśmy, implementacja query Gate nie jest tak naprawdę częścią samego algorytmu Deutscha; tutaj pokazujemy po prostu jeden ze sposobów przygotowania danych wejściowych w postaci implementacji query Gate jako Circuit.

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

Możemy zobaczyć, jak wygląda każdy Circuit, używając metody draw. Oto Circuit dla funkcji $f_3.$

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

Następnie stworzymy właściwy Circuit kwantowy dla algorytmu Deutscha, zastępując query Gate implementacją jako Circuit podanym jako argument. Za chwilę podłączymy jeden z czterech Circuit zdefiniowanych przez funkcję deutsch_function, którą zdefiniowaliśmy wcześniej. Bariery zostały dodane, aby pokazać wizualne oddzielenie między implementacją query Gate a resztą Circuit.

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

Ponownie możemy zobaczyć, jak wygląda Circuit, używając metody draw.

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

Na koniec stworzymy funkcję, która uruchamia wcześniej zdefiniowany Circuit jeden raz i zwraca odpowiedni wynik: „constant" lub „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"

Możemy teraz uruchomić algorytm Deutscha dla dowolnej z czterech funkcji zdefiniowanych powyżej.

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

'balanced'