Algorytm Deutscha-Jozsy

Algorytm Deutscha przewyższa wszystkie klasyczne algorytmy w pewnym problemie zapytaniowym, ale przewaga ta jest dość skromna: jedno zapytanie zamiast dwóch. Algorytm Deutsch-Jozsa rozszerza tę przewagę — a w rzeczywistości może być używany do rozwiązywania kilku różnych problemów zapytaniowych.

Oto opis algorytmu Deutsch-Jozsa w postaci obwodu kwantowego. W zależności od konkretnego rozwiązywanego problemu może być również wymagany dodatkowy klasyczny krok przetwarzania końcowego, którego nie przedstawiono na rysunku.

Oczywiście, nie omówiliśmy jeszcze, jakie problemy rozwiązuje ten algorytm; zostanie to zrobione w dwóch kolejnych sekcjach.

Problem Deutsch-Jozsa

Zaczniemy od problemu zapytaniowego, który algorytm Deutsch-Jozsa miał pierwotnie rozwiązywać, znanego jako problem Deutsch-Jozsa.

Funkcja wejściowa dla tego problemu ma postać $f:\Sigma^n \rightarrow \Sigma$ dla dowolnej dodatniej liczby całkowitej $n.$ Podobnie jak w problemie Deutscha, zadaniem jest zwrócenie wartości $0$, jeśli $f$ jest stała, oraz $1$, jeśli $f$ jest zrównoważona, co ponownie oznacza, że liczba ciągów wejściowych, dla których funkcja przyjmuje wartość $0$, jest równa liczbie ciągów wejściowych, dla których funkcja przyjmuje wartość $1$.

Zauważ, że gdy $n$ jest większe niż $1,$ istnieją funkcje postaci $f:\Sigma^n \rightarrow \Sigma$, które nie są ani stałe, ani zrównoważone. Na przykład funkcja $f:\Sigma^2\rightarrow\Sigma$ zdefiniowana jako

$$\begin{aligned} f(00) & = 0 \\ f(01) & = 0 \\ f(10) & = 0 \\ f(11) & = 1 \end{aligned}$$

nie należy do żadnej z tych dwóch kategorii. W problemie Deutsch-Jozsa po prostu nie przejmujemy się takimi funkcjami — są one traktowane jako wejścia „nieistotne”. Oznacza to, że dla tego problemu mamy obietnicę, że $f$ jest albo stała, albo zrównoważona.

Problem Deutsch-Jozsa

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

Algorytm Deutsch-Jozsa, za pomocą pojedynczego zapytania, rozwiązuje ten problem w następującym sensie: jeśli każdy z $n$ wyników pomiaru wynosi $0,$ to funkcja $f$ jest stała; w przeciwnym razie, jeśli co najmniej jeden z wyników pomiaru wynosi $1,$ to funkcja $f$ jest zrównoważona. Inaczej mówiąc, po opisanym powyżej obwodzie następuje klasyczny krok przetwarzania końcowego, w którym obliczana jest operacja OR wyników pomiarów w celu uzyskania wyjścia.

Analiza algorytmu

Aby przeanalizować wydajność algorytmu Deutsch-Jozsa w problemie Deutsch-Jozsa, pomocne jest zacząć od rozważenia działania pojedynczej warstwy bramek Hadamarda. Operację Hadamarda można wyrazić jako macierz w zwykły sposób,

$$H = \begin{pmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\[2mm] \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \end{pmatrix},$$

ale możemy również wyrazić tę operację poprzez jej działanie na stanach bazy standardowej:

$$\begin{aligned} H \vert 0\rangle & = \frac{1}{\sqrt{2}} \vert 0 \rangle + \frac{1}{\sqrt{2}} \vert 1 \rangle\\[3mm] H \vert 1\rangle & = \frac{1}{\sqrt{2}} \vert 0 \rangle - \frac{1}{\sqrt{2}} \vert 1 \rangle. \end{aligned}$$

Te dwa równania można połączyć w jeden wzór,

$$H \vert a \rangle = \frac{1}{\sqrt{2}} \vert 0 \rangle + \frac{1}{\sqrt{2}} (-1)^a \vert 1 \rangle = \frac{1}{\sqrt{2}} \sum_{b\in\{0,1\}} (-1)^{ab} \vert b\rangle,$$

który jest prawdziwy dla obu wyborów $a\in\Sigma.$

Załóżmy teraz, że zamiast pojedynczego kubitu mamy $n$ kubitów, i na każdym z nich wykonywana jest operacja Hadamarda. Połączoną operację na $n$ kubitach opisuje iloczyn tensorowy $H\otimes \cdots \otimes H$ ($n$ razy), który dla zwięzłości i przejrzystości zapisujemy jako $H^{\otimes n}$. Korzystając z powyższego wzoru, a następnie rozwijając i upraszczając, możemy wyrazić działanie tej połączonej operacji na stanach bazy standardowej $n$ kubitów w następujący sposób:

$$\begin{aligned} & H^{\otimes n} \vert x_{n-1} \cdots x_1 x_0 \rangle \\ & \qquad = \bigl(H \vert x_{n-1} \rangle \bigr) \otimes \cdots \otimes \bigl(H \vert x_{0} \rangle \bigr) \\ & \qquad = \Biggl( \frac{1}{\sqrt{2}} \sum_{y_{n-1}\in\Sigma} (-1)^{x_{n-1} y_{n-1}} \vert y_{n-1} \rangle \Biggr) \otimes \cdots \otimes \Biggl( \frac{1}{\sqrt{2}} \sum_{y_{0}\in\Sigma} (-1)^{x_{0} y_{0}} \vert y_{0} \rangle \Biggr) \\ & \qquad = \frac{1}{\sqrt{2^n}} \sum_{y_{n-1}\cdots y_0 \in \Sigma^n} (-1)^{x_{n-1}y_{n-1} + \cdots + x_0 y_0} \vert y_{n-1} \cdots y_0 \rangle. \end{aligned}$$

Przy okazji, zapisujemy tutaj ciągi binarne o długości $n$ jako $x_{n-1}\cdots x_0$ oraz $y_{n-1}\cdots y_0,$ zgodnie z konwencją indeksowania Qiskit.

Ten wzór dostarcza nam użytecznego narzędzia do analizy powyższego obwodu kwantowego. Po wykonaniu pierwszej warstwy bramek Hadamarda stan $n+1$ kubitów (w tym skrajnie lewego/dolnego kubitu, który jest traktowany oddzielnie od pozostałych) wynosi

$$\bigl( H \vert 1 \rangle \bigr) \bigl( H^{\otimes n} \vert 0 \cdots 0 \rangle \bigr) = \vert - \rangle \otimes \frac{1}{\sqrt{2^n}} \sum_{x_{n-1}\cdots x_0 \in \Sigma^n} \vert x_{n-1} \cdots x_0 \rangle.$$

Gdy wykonywana jest operacja $U_f$, stan ten zostaje przekształcony w

$$\vert - \rangle \otimes \frac{1}{\sqrt{2^n}} \sum_{x_{n-1}\cdots x_0 \in \Sigma^n} (-1)^{f(x_{n-1}\cdots x_0)} \vert x_{n-1} \cdots x_0 \rangle$$

dokładnie poprzez to samo zjawisko odrzutu fazy (phase kick-back), które widzieliśmy w analizie algorytmu Deutscha.

Następnie wykonywana jest druga warstwa bramek Hadamarda, która (zgodnie z powyższym wzorem) przekształca ten stan w

$$\vert - \rangle \otimes \frac{1}{2^n} \sum_{x_{n-1}\cdots x_0 \in \Sigma^n} \sum_{y_{n-1}\cdots y_0 \in \Sigma^n} (-1)^{f(x_{n-1}\cdots x_0) + x_{n-1}y_{n-1} + \cdots + x_0 y_0} \vert y_{n-1} \cdots y_0 \rangle.$$

To wyrażenie wygląda nieco skomplikowanie i nie można wiele wywnioskować na temat prawdopodobieństw uzyskania różnych wyników pomiarów bez posiadania większej wiedzy o funkcji $f.$

Na szczęście wszystko, co musimy wiedzieć, to prawdopodobieństwo, że każdy z wyników pomiarów wynosi $0$ — ponieważ jest to prawdopodobieństwo, że algorytm stwierdzi, iż $f$ jest stała. To prawdopodobieństwo ma prosty wzór.

$$\Biggl\vert \frac{1}{2^n} \sum_{x_{n-1}\cdots x_0 \in \Sigma^n} (-1)^{f(x_{n-1}\cdots x_0)} \Biggr\vert^2 = \begin{cases} 1 & \text{jeśli $f$ jest stała}\\[1mm] 0 & \text{jeśli $f$ jest zrównoważona} \end{cases}$$

Bardziej szczegółowo, jeśli $f$ jest stała, to albo $f(x_{n-1}\cdots x_0) = 0$ dla każdego ciągu $x_{n-1}\cdots x_0,$ w którym to przypadku wartość sumy wynosi $2^n,$ albo $f(x_{n-1}\cdots x_0) = 1$ dla każdego ciągu $x_{n-1}\cdots x_0,$ w którym to przypadku wartość sumy wynosi $-2^n.$ Dzielenie przez $2^n$ i podniesienie wartości bezwzględnej do kwadratu daje $1.$

Jeśli natomiast $f$ jest zrównoważona, to $f$ przyjmuje wartość $0$ na połowie ciągów $x_{n-1}\cdots x_0$ i wartość $1$ na drugiej połowie, więc wyrazy $+1$ i $-1$ w sumie się znoszą i pozostaje nam wartość $0.$

Wnioskujemy, że algorytm działa poprawnie, pod warunkiem że obietnica jest spełniona.

Trudność klasyczna

Algorytm Deutscha-Jozsy działa za każdym razem, zawsze dając nam poprawną odpowiedź, gdy obietnica jest spełniona, i wymaga jednego zapytania. Jak to wypada w porównaniu z klasycznymi algorytmami zapytań dla problemu Deutscha-Jozsy?

Po pierwsze, każdy deterministyczny klasyczny algorytm, który poprawnie rozwiązuje problem Deutscha-Jozsy, musi wykonać wykładniczo wiele zapytań: w najgorszym przypadku wymagane jest $2^{n-1} + 1$ zapytań. Rozumowanie jest takie, że jeśli algorytm deterministyczny zapyta $f$ o $2^{n-1}$ lub mniej różnych ciągów i za każdym razem otrzyma tę samą wartość funkcji, to obie odpowiedzi są nadal możliwe. Funkcja może być stała lub może być zrównoważona, ale przez pech wszystkie zapytania zwróciły tę samą wartość funkcji.

Druga możliwość może wydawać się mało prawdopodobna — ale dla algorytmów deterministycznych nie ma losowości ani niepewności, więc będą one systematycznie zawodzić na pewnych funkcjach. Mamy zatem pod tym względem znaczącą przewagę algorytmów kwantowych nad klasycznymi.

Jest jednak pewien haczyk, a mianowicie probabilistyczne klasyczne algorytmy mogą rozwiązać problem Deutscha-Jozsy z bardzo wysokim prawdopodobieństwem, używając zaledwie kilku zapytań. W szczególności, jeśli po prostu wybierzemy kilka różnych losowych ciągów długości $n$ i zapytamy $f$ o te ciągi, jest mało prawdopodobne, że otrzymamy tę samą wartość funkcji dla wszystkich z nich, gdy $f$ jest zrównoważona.

Mówiąc konkretnie, jeśli wybierzemy $k$ ciągów wejściowych $x^1,\ldots,x^k \in \Sigma^n$ jednostajnie losowo, obliczymy $f(x^1),\ldots,f(x^k),$ i odpowiemy $0$, jeśli wszystkie wartości funkcji są takie same, oraz $1$ w przeciwnym razie, to zawsze będziemy mieli rację, gdy $f$ jest stała, a pomylimy się w przypadku, gdy $f$ jest zrównoważona, z prawdopodobieństwem zaledwie $2^{-k + 1}.$ Na przykład, jeśli weźmiemy $k = 11,$ ten algorytm odpowie poprawnie z prawdopodobieństwem większym niż $99{,}9$%.

Z tego powodu wciąż mamy raczej skromną przewagę algorytmów kwantowych nad klasycznymi — niemniej jednak jest to wymierna przewaga stanowiąca poprawę względem algorytmu Deutscha.

Deutsch-Jozsa w Qiskit

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

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator
import numpy as np

Aby zaimplementować algorytm Deutscha-Jozsy w Qiskit, zaczniemy od zdefiniowania funkcji dj_query, która generuje obwód kwantowy realizujący bramkę zapytania dla losowo wybranej funkcji spełniającej obietnicę problemu Deutscha-Jozsy. Z prawdopodobieństwem 50% funkcja jest stała, a z prawdopodobieństwem 50% funkcja jest zrównoważona. Dla każdej z tych dwóch możliwości funkcja jest wybierana jednostajnie spośród funkcji danego typu. Argumentem jest liczba bitów wejściowych funkcji.

def dj_query(num_qubits):
    # Create a circuit implementing for a query gate for a random function
    # satisfying the promise for the Deutsch-Jozsa problem.

    qc = QuantumCircuit(num_qubits + 1)

    if np.random.randint(0, 2):
        # Flip output qubit with 50% chance
        qc.x(num_qubits)
    if np.random.randint(0, 2):
        # return constant circuit with 50% chance
        return qc

    # Choose half the possible input strings
    on_states = np.random.choice(
        range(2**num_qubits),  # numbers to sample from
        2**num_qubits // 2,  # number of samples
        replace=False,  # makes sure states are only sampled once
    )

    def add_cx(qc, bit_string):
        for qubit, bit in enumerate(reversed(bit_string)):
            if bit == "1":
                qc.x(qubit)
        return qc

    for state in on_states:
        qc.barrier()  # Barriers are added to help visualize how the functions are created.
        qc = add_cx(qc, f"{state:0b}")
        qc.mcx(list(range(num_qubits)), num_qubits)
        qc = add_cx(qc, f"{state:0b}")

    qc.barrier()

    return qc

Implementację bramki zapytania w postaci obwodu kwantowego możemy pokazać za pomocą metody draw jak zwykle.

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

Następnie definiujemy funkcję, która tworzy obwód Deutscha-Jozsy, przyjmując jako argument implementację bramki zapytania w postaci obwodu kwantowego.

def compile_circuit(function: QuantumCircuit):
    # Compiles a circuit for use in the Deutsch-Jozsa algorithm.

    n = function.num_qubits - 1
    qc = QuantumCircuit(n + 1, n)
    qc.x(n)
    qc.h(range(n + 1))
    qc.compose(function, inplace=True)
    qc.h(range(n))
    qc.measure(range(n), range(n))
    return qc

Na koniec definiujemy funkcję, która uruchamia obwód Deutscha-Jozsy jeden raz.

def dj_algorithm(function: QuantumCircuit):
    # Determine if a function is constant or balanced.

    qc = compile_circuit(function)

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

Możemy przetestować naszą implementację, wybierając losowo funkcję, wyświetlając implementację bramki zapytania dla tej funkcji w postaci obwodu kwantowego, a następnie uruchamiając algorytm Deutscha-Jozsy na tej funkcji.

f = dj_query(3)
display(f.draw("mpl"))
display(dj_algorithm(f))

'balanced'

Problem Bernsteina-Vaziraniego

Następnie omówimy problem znany jako problem Bernsteina-Vaziraniego. Nazywany jest również problemem próbkowania Fouriera, choć istnieją bardziej ogólne sformułowania tego problemu, które również noszą tę nazwę.

Najpierw wprowadźmy pewną notację. Dla dowolnych dwóch łańcuchów binarnych $x = x_{n-1} \cdots x_0$ i $y = y_{n-1}\cdots y_0$ o długości $n,$ definiujemy

$$x \cdot y = x_{n-1} y_{n-1} \oplus \cdots \oplus x_0 y_0.$$

Będziemy nazywać tę operację binarnym iloczynem skalarnym. Alternatywny sposób jej zdefiniowania jest następujący.

$$x \cdot y = \begin{cases} 1 & x_{{n-1}} y_{n-1} + \cdots + x_0 y_0 \text{ jest nieparzysta}\\[0.5mm] 0 & x_{{n-1}} y_{n-1} + \cdots + x_0 y_0 \text{ jest parzysta} \end{cases}$$

Zauważmy, że jest to operacja symetryczna, co oznacza, że wynik nie zmienia się, jeśli zamienimy $x$ i $y,$ więc możemy to robić kiedy jest to wygodne. Czasem przydatne jest myślenie o binarnym iloczynie skalarnym $x \cdot y$ jako o parzystości bitów $x$ na pozycjach, na których łańcuch $y$ ma $1,$ lub równoważnie, parzystości bitów $y$ na pozycjach, na których łańcuch $x$ ma $1.$

Mając tę notację, możemy teraz zdefiniować problem Bernsteina-Vaziraniego.

Problem Bernsteina-Vaziraniego

Wejście: funkcja $f:\{0,1\}^n\rightarrow\{0,1\}$
Obietnica: istnieje łańcuch binarny $s = s_{n-1} \cdots s_0,$ dla którego $f(x) = s\cdot x$ dla wszystkich $x\in\Sigma^n$
Wyjście: łańcuch $s$

Tak naprawdę nie potrzebujemy nowego algorytmu kwantowego do tego problemu; rozwiązuje go algorytm Deutscha-Jozsy. Dla jasności nazwijmy obwód kwantowy z góry, który nie obejmuje klasycznego etapu przetwarzania końcowego polegającego na obliczaniu OR, obwodem Deutscha-Jozsy.

Analiza algorytmu

Aby przeanalizować, jak działa obwód Deutscha-Jozsy dla funkcji spełniającej obietnicę problemu Bernsteina-Vaziraniego, zaczniemy od krótkiej obserwacji. Używając binarnego iloczynu skalarnego, możemy alternatywnie opisać działanie $n$ bramek Hadamarda na stanach bazy standardowej $n$ kubitów w następujący sposób.

$$H^{\otimes n} \vert x \rangle = \frac{1}{\sqrt{2^n}} \sum_{y\in\Sigma^n} (-1)^{x\cdot y} \vert y\rangle$$

Podobnie jak widzieliśmy przy analizie algorytmu Deutscha, wynika to z faktu, że wartość $(-1)^k$ dla dowolnej liczby całkowitej $k$ zależy tylko od tego, czy $k$ jest parzysta czy nieparzysta.

Wracając do obwodu Deutscha-Jozsy, po wykonaniu pierwszej warstwy bramek Hadamarda stan $n+1$ kubitów wynosi

$$\vert - \rangle \otimes \frac{1}{\sqrt{2^n}} \sum_{x \in \Sigma^n} \vert x \rangle.$$

Następnie wykonywana jest bramka zapytania, która (poprzez zjawisko phase kickback) przekształca stan w

$$\vert - \rangle \otimes \frac{1}{\sqrt{2^n}} \sum_{x \in \Sigma^n} (-1)^{f(x)} \vert x \rangle.$$

Korzystając z naszego wzoru na działanie warstwy bramek Hadamarda, widzimy, że druga warstwa bramek Hadamarda przekształca następnie ten stan w

$$\vert - \rangle \otimes \frac{1}{2^n} \sum_{x \in \Sigma^n} \sum_{y \in \Sigma^n} (-1)^{f(x) + x \cdot y} \vert y \rangle.$$

Teraz możemy dokonać pewnych uproszczeń w wykładniku $-1$ wewnątrz sumy. Mamy obietnicę, że $f(x) = s\cdot x$ dla pewnego łańcucha $s = s_{n-1} \cdots s_0,$ więc możemy wyrazić stan jako

$$\vert - \rangle \otimes \frac{1}{2^n} \sum_{x \in \Sigma^n} \sum_{y \in \Sigma^n} (-1)^{s\cdot x + x \cdot y} \vert y \rangle.$$

Ponieważ $s\cdot x$ i $x\cdot y$ są wartościami binarnymi, możemy zastąpić dodawanie operacją exclusive-OR — znowu dlatego, że jedyne, co ma znaczenie dla liczby całkowitej w wykładniku $-1,$ to czy jest ona parzysta czy nieparzysta. Wykorzystując symetrię binarnego iloczynu skalarnego, otrzymujemy następujące wyrażenie dla stanu:

$$\vert - \rangle \otimes \frac{1}{2^n} \sum_{x \in \Sigma^n} \sum_{y \in \Sigma^n} (-1)^{(s\cdot x) \oplus (y \cdot x)} \vert y \rangle.$$

(Nawiasy zostały dodane dla jasności, chociaż nie są one naprawdę konieczne, ponieważ zwyczajowo traktuje się binarny iloczyn skalarny jako mający wyższy priorytet niż exclusive-OR.)

W tym momencie skorzystamy z następującego wzoru.

$$(s\cdot x) \oplus (y \cdot x) = (s \oplus y) \cdot x$$

Możemy uzyskać ten wzór dzięki podobnemu wzorowi dla bitów,

$$(a c) \oplus (b c) = (a \oplus b) c,$$

wraz z rozwinięciem binarnego iloczynu skalarnego i bitowego exclusive-OR:

$$\begin{aligned} (s\cdot x) \oplus (y \cdot x) & = (s_{n-1} x_{n-1}) \oplus \cdots \oplus (s_{0} x_{0}) \oplus (y_{n-1} x_{n-1}) \oplus \cdots \oplus (y_{0} x_{0}) \\ & = (s_{n-1} \oplus y_{n-1}) x_{n-1} \oplus \cdots \oplus (s_{0} \oplus y_{0}) x_{0} \\ & = (s \oplus y) \cdot x \end{aligned}$$

Pozwala to wyrazić stan obwodu bezpośrednio przed pomiarami w następujący sposób:

$$\vert - \rangle \otimes \frac{1}{2^n} \sum_{x \in \Sigma^n} \sum_{y \in \Sigma^n} (-1)^{(s\oplus y)\cdot x} \vert y \rangle.$$

Ostatnim krokiem jest wykorzystanie jeszcze jednego wzoru, który działa dla każdego łańcucha binarnego $z = z_{n-1}\cdots z_0.$

$$\frac{1}{2^n} \sum_{x \in \Sigma^n} (-1)^{z \cdot x} = \begin{cases} 1 & \text{jeśli $z = 0^n$}\\ 0 & \text{jeśli $z\neq 0^n$} \end{cases}$$

Używamy tu prostej notacji dla łańcuchów, której użyjemy jeszcze kilka razy w tej lekcji: $0^n$ to łańcuch samych zer o długości $n.$

Prostym sposobem uzasadnienia tego wzoru jest rozważenie dwóch przypadków osobno. Jeśli $z = 0^n,$ to $z\cdot x = 0$ dla każdego łańcucha $x\in\Sigma^n,$ więc wartość każdego składnika sumy wynosi $1,$ i otrzymujemy $1$ poprzez zsumowanie i podzielenie przez $2^n.$ Z drugiej strony, jeśli którykolwiek z bitów $z$ jest równy $1,$ to binarny iloczyn skalarny $z\cdot x$ jest równy $0$ dla dokładnie połowy możliwych wyborów $x\in\Sigma^n$ oraz $1$ dla drugiej połowy — ponieważ wartość binarnego iloczynu skalarnego $z\cdot x$ zmienia się (z $0$ na $1$ lub z $1$ na $0$), gdy zmienimy którykolwiek bit $x$ na pozycji, na której $z$ ma $1.$

Jeśli teraz zastosujemy ten wzór do uproszczenia stanu obwodu przed pomiarami, otrzymamy

$$\vert - \rangle \otimes \frac{1}{2^n} \sum_{x \in \Sigma^n} \sum_{y \in \Sigma^n} (-1)^{(s\oplus y)\cdot x} \vert y \rangle = \vert - \rangle \otimes \vert s \rangle,$$

dzięki temu, że $s\oplus y = 0^n$ wtedy i tylko wtedy, gdy $y = s.$ Zatem pomiary ujawniają dokładnie ten łańcuch $s,$ którego szukamy.

Trudność klasyczna

Podczas gdy obwód Deutscha-Jozsy rozwiązuje problem Bernsteina-Vaziraniego za pomocą jednego zapytania, każdy klasyczny algorytm zapytaniowy musi wykonać co najmniej $n$ zapytań, aby rozwiązać ten problem.

Można to uzasadnić za pomocą tzw. argumentu teorio-informacyjnego, który w tym przypadku jest bardzo prosty. Każde klasyczne zapytanie ujawnia pojedynczy bit informacji o rozwiązaniu, a mamy $n$ bitów informacji, które należy odkryć — więc potrzeba co najmniej $n$ zapytań.

W istocie możliwe jest klasyczne rozwiązanie problemu Bernsteina-Vaziraniego poprzez odpytanie funkcji na każdym z $n$ łańcuchów mających pojedynczą $1,$ na każdej możliwej pozycji, oraz $0$ dla wszystkich pozostałych bitów, co ujawnia bity $s$ jeden po drugim. Dlatego przewaga algorytmów kwantowych nad klasycznymi dla tego problemu wynosi $1$ zapytanie względem $n$ zapytań.

Bernstein-Vazirani z Qiskit

Zaimplementowaliśmy już obwód Deutscha-Jozsy powyżej i tutaj wykorzystamy go do rozwiązania problemu Bernsteina-Vaziraniego. Najpierw zdefiniujemy funkcję, która implementuje bramkę zapytania dla problemu Bernsteina-Vaziraniego dla dowolnego łańcucha binarnego $s.$

def bv_query(s):
    # Create a quantum circuit implementing a query gate for the
    # Bernstein-Vazirani problem.

    qc = QuantumCircuit(len(s) + 1)
    for index, bit in enumerate(reversed(s)):
        if bit == "1":
            qc.cx(index, len(s))
    return qc

display(bv_query("1011").draw(output="mpl"))

Teraz możemy utworzyć funkcję, która uruchamia obwód Deutscha-Jozsy na funkcji, używając funkcji compile_circuit zdefiniowanej wcześniej.

def bv_algorithm(function: QuantumCircuit):
    qc = compile_circuit(function)
    result = AerSimulator().run(qc, shots=1, memory=True).result()
    return result.get_memory()[0]

display(bv_algorithm(bv_query("1011")))

'1011'

Uwaga dotycząca nazewnictwa

W kontekście problemu Bernsteina-Vaziraniego często zdarza się, że algorytm Deutscha-Jozsy jest nazywany "algorytmem Bernsteina-Vaziraniego". Jest to nieco mylące, ponieważ ten algorytm jest algorytmem Deutscha-Jozsy, o czym Bernstein i Vazirani jasno pisali w swojej pracy.

To, co Bernstein i Vazirani zrobili po pokazaniu, że algorytm Deutscha-Jozsy rozwiązuje problem Bernsteina-Vaziraniego (tak jak został on sformułowany powyżej), to zdefiniowanie znacznie bardziej skomplikowanego problemu, znanego jako problem rekurencyjnego próbkowania Fouriera. Jest to wysoce sztuczny problem, w którym rozwiązania różnych instancji problemu faktycznie odblokowują nowe poziomy problemu ułożone w strukturę drzewiastą. Problem Bernsteina-Vaziraniego jest zasadniczo tylko przypadkiem bazowym tego bardziej skomplikowanego problemu.

Problem rekurencyjnego próbkowania Fouriera był pierwszym znanym przykładem problemu zapytaniowego, w którym algorytmy kwantowe mają tak zwaną superwielomianową przewagę nad algorytmami probabilistycznymi, tym samym przewyższając przewagę kwantowych nad klasycznymi oferowaną przez algorytm Deutscha-Jozsy. Intuicyjnie mówiąc, rekurencyjna wersja problemu wzmacnia przewagę $1$ kontra $n$ algorytmów kwantowych do czegoś znacznie większego.

Najbardziej wymagającym aspektem analizy matematycznej ustanawiającej tę przewagę jest wykazanie, że klasyczne algorytmy zapytaniowe nie mogą rozwiązać problemu bez wykonania wielu zapytań. Jest to dość typowe; dla wielu problemów wykluczenie kreatywnych podejść klasycznych, które rozwiązują je efektywnie, może być bardzo trudne.

Problem Simona oraz algorytm do jego rozwiązania opisany w następnej sekcji stanowi znacznie prostszy przykład superwielomianowej (a w zasadzie wykładniczej) przewagi algorytmów kwantowych nad klasycznymi i z tego powodu problem rekurencyjnego próbkowania Fouriera jest rzadziej omawiany. Jest on jednak sam w sobie interesującym problemem obliczeniowym.