Algorytm Deutscha-Jozsy

W tym module Qiskit in Classrooms studenci muszą mieć działające środowisko Python z zainstalowanymi następującymi pakietami:

• qiskit w wersji 2.1.0 lub nowszej
• qiskit-ibm-runtime w wersji 0.40.1 lub nowszej
• qiskit-aer w wersji 0.17.0 lub nowszej
• qiskit.visualization
• numpy
• pylatexenc

Aby skonfigurować i zainstalować powyższe pakiety, zapoznaj się z przewodnikiem Instalacja Qiskit. Aby uruchamiać zadania na prawdziwych komputerach kwantowych, studenci będą musieli założyć konto w IBM Quantum®, wykonując kroki opisane w przewodniku Konfiguracja konta IBM Cloud.

Ten moduł został przetestowany i zużył cztery sekundy czasu QPU. Jest to jedynie szacunek. Rzeczywiste zużycie może się różnić.

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

# Uncomment and modify this line as needed to install dependencies
#!pip install 'qiskit>=2.1.0' 'qiskit-ibm-runtime>=0.40.1' 'qiskit-aer>=0.17.0' 'numpy' 'pylatexenc'

Obejrzyj poniżej przewodnik po module autorstwa dr Katie McCormick lub kliknij tutaj, aby obejrzeć go na YouTube.

---

Wprowadzenie

Na początku lat 80. XX wieku fizycy kwantowi i informatycy mieli ogólne przeczucie, że mechanika kwantowa może zostać wykorzystana do wykonywania obliczeń znacznie potężniejszych niż te, które są w stanie wykonać klasyczne komputery. Rozumowanie było następujące: klasycznemu komputerowi trudno jest symulować układy kwantowe, ale kwantowy komputer powinien być w stanie robić to wydajniej. A jeśli komputer kwantowy mógłby wydajniej symulować układy kwantowe, być może istniałyby inne zadania, które mógłby wykonywać wydajniej niż klasyczny komputer.

Logika była trafna, ale szczegóły wymagały jeszcze dopracowania. Zaczęło się to w 1985 roku, gdy David Deutsch opisał pierwszy „uniwersalny komputer kwantowy". W tej samej pracy podał pierwszy przykład problemu, w którym komputer kwantowy mógłby rozwiązać coś wydajniej niż klasyczny komputer. Ten pierwszy zabawkowy przykład znany jest dziś jako „algorytm Deutscha". Poprawa w algorytmie Deutscha była skromna, ale Deutsch kilka lat później współpracował z Richardem Jozsą, aby jeszcze bardziej poszerzyć przepaść między komputerami klasycznymi a kwantowymi.

Te algorytmy — Deutscha oraz rozszerzenie Deutscha-Jozsy — nie są szczególnie użyteczne, ale nadal mają ogromne znaczenie z kilku powodów:

1. Historycznie były jednymi z pierwszych algorytmów kwantowych, które wykazały przewagę nad klasycznymi odpowiednikami. Zrozumienie ich może pomóc nam zrozumieć, jak myślenie społeczności o obliczeniach kwantowych ewoluowało w czasie.
2. Mogą pomóc nam zrozumieć pewne aspekty odpowiedzi na zaskakująco subtelne pytanie: Co daje obliczeniom kwantowym ich moc? Czasami komputery kwantowe są porównywane do ogromnych, wykładniczo skalujących się procesorów równoległych. Ale to nie jest do końca prawda. Choć część odpowiedzi na to pytanie leży w tak zwanym „kwantowym równoległości", wydobycie jak największej ilości informacji w jednym uruchomieniu jest subtelną sztuką. Algorytmy Deutscha i Deutscha-Jozsy pokazują, jak można to osiągnąć.

W tym module poznamy algorytm Deutscha, algorytm Deutscha-Jozsy oraz to, czego uczą nas o mocy obliczeń kwantowych.

Kwantowy równoległy obliczenia i jego ograniczenia

Część mocy obliczeń kwantowych wynika z „kwantowego równoległości", czyli zasadniczo zdolności do wykonywania operacji na wielu wejściach jednocześnie, ponieważ stany wejściowe Qubit mogą znajdować się w superpozycji wielu klasycznie dozwolonych stanów. JEDNAK, choć obwód kwantowy może być w stanie ocenić wiele stanów wejściowych naraz, wydobycie wszystkich tych informacji za jednym razem jest niemożliwe.

Aby zobaczyć, co mam na myśli, powiedzmy, że mamy bit, $x$, i pewną funkcję zastosowaną do tego bitu, $f(x)$. Istnieją cztery możliwe funkcje binarne odwzorowujące pojedynczy bit na inny pojedynczy bit:

$x$	$f_1(x)$	$f_2(x)$	$f_3(x)$	$f_4(x)$
0	0	0	1	1
1	0	1	0	1

Chcielibyśmy dowiedzieć się, która z tych funkcji (1–4) jest naszą $f(x)$. Klasycznie musielibyśmy uruchomić funkcję dwa razy — raz dla $x=0$, raz dla $x=1$. Sprawdźmy jednak, czy możemy zrobić to lepiej z obwodem kwantowym. Możemy poznać funkcję za pomocą następującej bramki:

Tutaj bramka $U_f$ oblicza $f(x)$, gdzie $x$ jest stanem Qubit 0, i stosuje to do Qubit 1. Tak więc wynikowy stan, $|x\rangle|y\oplus f(x)\rangle$, staje się po prostu $|x\rangle|f(x)\rangle$, gdy $|y\rangle = |0\rangle$. Zawiera to wszystkie informacje potrzebne do poznania funkcji $f(x)$: Qubit 0 mówi nam, czym jest $x$, a Qubit 1 mówi nam, czym jest $f(x)$. Tak więc, jeśli zainicjujemy $|x\rangle = \frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$, to końcowy stan obu Qubitów będzie: $|y\rangle|x\rangle = \frac{1}{\sqrt{2}}(|f(0)\rangle|0\rangle+|f(1)\rangle|1\rangle)$. Ale jak możemy uzyskać dostęp do tych informacji?

2.1. Wypróbuj to w Qiskit:

Używając Qiskit, losowo wybierzemy jedną z czterech możliwych funkcji powyżej i uruchomimy obwód. Twoim zadaniem jest użycie pomiarów obwodu kwantowego, aby nauczyć się funkcji w jak najmniejszej liczbie uruchomień.

W tym pierwszym eksperymencie i przez cały moduł będziemy używać frameworku do obliczeń kwantowych znanego jako „wzorce Qiskit" (ang. Qiskit patterns), który dzieli przepływ pracy na następujące kroki:

• Krok 1: Odwzorowanie klasycznych danych wejściowych na problem kwantowy
• Krok 2: Optymalizacja problemu pod kątem wykonania kwantowego
• Krok 3: Wykonanie za pomocą prymitywów Qiskit Runtime
• Krok 4: Przetwarzanie końcowe i klasyczna analiza

Zacznijmy od załadowania niezbędnych pakietów, w tym prymitywów Qiskit Runtime. Wybierzemy też najmniej zajęty dostępny dla nas komputer kwantowy.

Poniżej znajduje się kod służący do zapisania danych uwierzytelniających przy pierwszym użyciu. Pamiętaj, aby usunąć te informacje z notatnika po ich zapisaniu w swoim środowisku, żeby dane uwierzytelniające nie zostały przypadkowo udostępnione podczas dzielenia się notatnikiem. Więcej wskazówek znajdziesz w artykułach Konfiguracja konta IBM Cloud i Inicjalizacja usługi w niezaufanym środowisku.

# Load the Qiskit Runtime service
from qiskit_ibm_runtime import QiskitRuntimeService

# Load the Runtime primitive and session
from qiskit_ibm_runtime import SamplerV2 as Sampler

# Syntax for first saving your token.  Delete these lines after saving your credentials.
# QiskitRuntimeService.save_account(channel='ibm_quantum_platform', instance = '<YOUR_IBM_INSTANCE_CRN>', token='<YOUR_API_KEY>', overwrite=True, set_as_default=True)
# service = QiskitRuntimeService(channel='ibm_quantum_platform')

# Load saved credentials
service = QiskitRuntimeService()

# Use the least busy backend, or uncomment the loading of a specific backend like "ibm_brisbane".
# backend = service.least_busy(operational=True, simulator=False, min_num_qubits = 127)
backend = service.backend("ibm_brisbane")
print(backend.name)

sampler = Sampler(mode=backend)

ibm_brisbane

Poniższa komórka pozwoli ci przełączać się między używaniem symulatora a prawdziwym sprzętem przez cały notatnik. Zalecamy uruchomienie jej teraz:

# Load the backend sampler
from qiskit.primitives import BackendSamplerV2

# Load the Aer simulator and generate a noise model based on the currently-selected backend.
from qiskit_aer import AerSimulator
from qiskit_aer.noise import NoiseModel

# Alternatively, load a fake backend with generic properties and define a simulator.

noise_model = NoiseModel.from_backend(backend)

# Define a simulator using Aer, and use it in Sampler.
backend_sim = AerSimulator(noise_model=noise_model)
sampler_sim = BackendSamplerV2(backend=backend_sim)

# You could also define a simulator-based sampler using a generic backend:
# backend_gen = GenericBackendV2(num_qubits=18)
# sampler_gen = BackendSamplerV2(backend=backend_gen)

Po załadowaniu niezbędnych pakietów możemy przejść do przepływu pracy wzorców Qiskit. W poniższym kroku odwzorowania najpierw tworzymy funkcję, która wybiera spośród czterech możliwych funkcji odwzorowujących pojedynczy bit na inny pojedynczy bit.

# Step 1: Map

from qiskit import QuantumCircuit

qc = QuantumCircuit(2)

def twobit_function(case: int):
    """
    Generate a valid two-bit function as a `QuantumCircuit`.
    """
    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

# first, convert oracle circuit (above) to a single gate for drawing purposes. otherwise, the circuit is too large to display
# blackbox = twobit_function(2).to_gate()  # you may edit the number inside "twobit_function()" to select among the four valid functions
# blackbox.label = "$U_f$"

qc.h(0)
qc.barrier()
qc.compose(twobit_function(2), inplace=True)
qc.measure_all()

qc.draw("mpl")

W powyższym obwodzie bramka Hadamarda „H" przenosi Qubit 0, który początkowo jest w stanie $|0\rangle$, do stanu superpozycji $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$. Następnie $U_f$ oblicza funkcję $f(x)$ i stosuje ją do Qubit 1.

Następnie musimy zoptymalizować i przeprowadzić transpilację obwodu, aby uruchomić go na komputerze kwantowym:

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

qc_isa = pm.run(qc)

Na koniec wykonujemy nasz przeprowadzony transpilację obwód na komputerze kwantowym i wizualizujemy wyniki:

# Step 3: Run the job on a real quantum computer

job = sampler.run([qc_isa], shots=1)
# job = sampler_sim.run([qc_isa],shots=1) # uncomment this line to run on simulator instead
res = job.result()
counts = res[0].data.meas.get_counts()

# Step 4: Visualize and analyze results

## Analysis
from qiskit.visualization import plot_histogram

plot_histogram(counts)

Powyżej widnieje histogram naszych wyników. W zależności od liczby uruchomień (ang. shots), jaką wybrałeś do wykonania obwodu w kroku 3 powyżej, możesz zobaczyć jeden lub dwa słupki reprezentujące zmierzone stany obu Qubitów w każdym uruchomieniu. Jak zawsze w Qiskit i w tym notatniku, używamy notacji „little endian", co oznacza, że stany Qubitów od 0 do n są zapisywane w kolejności rosnącej od prawej do lewej, więc Qubit 0 jest zawsze skrajnie po prawej.

Ponieważ Qubit 0 był w stanie superpozycji, obwód ocenił funkcję dla obu wartości $x=0$ i $x=1$ jednocześnie — czego klasyczne komputery nie potrafią! Ale haczyk pojawia się, gdy chcemy dowiedzieć się czegoś o funkcji $f(x)$ — gdy mierzymy Qubity, ich stan ulega kolapsowi. Jeśli wybierzesz „shots = 1", aby uruchomić obwód tylko raz, w histogramie powyżej zobaczysz tylko jeden słupek, a twoje informacje o funkcji będą niepełne.

Sprawdź swoje zrozumienie

Przeczytaj poniższe pytania, zastanów się nad odpowiedzią, a następnie kliknij trójkąt, aby ujawnić rozwiązanie.

Ile razy musimy uruchomić powyższy algorytm, aby poznać funkcję $f(x)$? Czy jest to lepsze niż w przypadku klasycznym? Czy wolisz mieć klasyczny, czy kwantowy komputer do rozwiązania tego problemu?

Odpowiedź:

Ponieważ pomiar spowoduje kolaps superpozycji i zwróci tylko jedną wartość, musimy uruchomić obwód co najmniej dwa razy, aby uzyskać oba wyjścia funkcji $f(0)$ i $f(1)$. W najlepszym przypadku działa to tak samo dobrze jak w wariancie klasycznym, gdzie obliczamy zarówno $f(0)$, jak i $f(1)$ w ciągu pierwszych dwóch zapytań. Istnieje jednak szansa, że będziemy musieli uruchomić go więcej niż dwa razy, ponieważ końcowy pomiar jest probabilistyczny i może zwrócić tę samą wartość $f(x)$ za pierwszymi dwoma razami. W tym przypadku wolałbym mieć klasyczny komputer.

Chociaż więc kwantowy równoległy obliczenia mogą być potężne, gdy są używane w odpowiedni sposób, nieprawidłowe jest twierdzenie, że komputer kwantowy działa tak jak masywny, klasyczny procesor równoległy. Akt pomiaru powoduje kolaps stanów kwantowych, więc możemy uzyskać dostęp tylko do jednego wyjścia obliczenia.

Algorytm Deutscha

Chociaż sama kwantowa równoległość nie daje nam przewagi nad komputerami klasycznymi, możemy ją połączyć z innym zjawiskiem kwantowym — interferencją — aby uzyskać przyspieszenie. Algorytm znany dziś jako „algorytm Deutscha" jest pierwszym przykładem algorytmu, który to osiąga.

Problem

Oto problem:

Mając dany bit wejściowy $x = \{0,1\}$ oraz funkcję wejściową $f(x) = \{0,1\}$, określ, czy funkcja jest zbalansowana, czy stała. Tzn. jeśli jest zbalansowana, to wynik funkcji wynosi 0 przez połowę czasu i 1 przez drugą połowę. Jeśli jest stała, to wynik funkcji jest zawsze 0 albo zawsze 1. Przypomnijmy tabelę czterech możliwych funkcji przekształcających jeden bit w jeden bit:

$x$	$f_1(x)$	$f_2(x)$	$f_3(x)$	$f_4(x)$
0	0	0	1	1
1	0	1	0	1

Pierwsza i ostatnia funkcja, $f_1(x)$ i $f_4(x)$, są stałe, podczas gdy dwie środkowe funkcje, $f_2(x)$ i $f_3(x)$, są zbalansowane.

Algorytm

Deutsch podszedł do tego problemu przez „model zapytań". W modelu zapytań funkcja wejściowa ($f_i(x)$ powyżej) jest zamknięta w „czarnej skrzynce" — nie mamy bezpośredniego dostępu do jej zawartości, ale możemy wysyłać zapytania do czarnej skrzynki, a ona zwróci nam wynik funkcji. Mówimy czasem, że informacji tych dostarcza „wyrocznia". Więcej o modelu zapytań znajdziesz w Lekcji 1: Kwantowe algorytmy zapytań kursu Fundamentals of Quantum Algorithms.

Aby określić, czy algorytm kwantowy jest wydajniejszy od klasycznego w modelu zapytań, wystarczy porównać liczbę zapytań do czarnej skrzynki w obu przypadkach. Klasycznie, aby ustalić, czy funkcja zawarta w czarnej skrzynce jest zbalansowana czy stała, musielibyśmy zapytać skrzynkę dwa razy — raz dla $f(0)$ i raz dla $f(1)$.

W kwantowym algorytmie Deutscha znalazł on jednak sposób na uzyskanie tej informacji przy użyciu tylko jednego zapytania! Wprowadził jedną modyfikację do powyższego układu „kwantowej równoległości": przygotował stan superpozycji na obu qubitach, zamiast tylko na qubicie 0. Następnie dwa wyjścia funkcji, $f(0)$ i $f(1)$, interferowały ze sobą, zwracając 0, jeśli oba były takie same — tzn. oba 0 lub oba 1 (funkcja była stała) — i zwracając 1, jeśli były różne (funkcja była zbalansowana). W ten sposób Deutsch mógł odróżnić funkcję stałą od zbalansowanej przy użyciu jednego zapytania.

Oto diagram układu algorytmu Deutscha:

Aby zrozumieć, jak działa ten algorytm, przyjrzyjmy się stanom kwantowym qubitów w trzech punktach zaznaczonych na powyższym diagramie. Spróbuj samodzielnie wyznaczyć te stany, zanim klikniesz, aby zobaczyć odpowiedzi:

Sprawdź swoje rozumienie

Przeczytaj poniższe pytania, zastanów się nad odpowiedziami, a następnie kliknij trójkąty, aby zobaczyć rozwiązania.

Jaki jest stan $|\pi_1\rangle$?

Odpowiedź:

Zastosowanie bramki Hadamarda przekształca stan $|0\rangle$ w $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$, a stan $|1\rangle$ w $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$. Zatem pełny stan przyjmuje postać: $|\pi_1\rangle = [\frac{|0\rangle-|1\rangle}{\sqrt{2}}][\frac{|0\rangle+|1\rangle}{\sqrt{2}}]$

Jaki jest stan $|\pi_2\rangle$?

Odpowiedź:

Zanim zastosujemy $U_f$, przypomnijmy, co ona robi. Zmienia stan qubitu 1 w zależności od stanu qubitu 0. Dlatego sensowne jest wydzielenie stanu qubitu 0: $|\pi_1\rangle = \frac{1}{2} (|0\rangle-|1\rangle)|0\rangle+\frac{1}{2}(|0\rangle-|1\rangle)|1\rangle$. Następnie, jeśli $f(0)=f(1)$, oba człony transformują się tak samo i względny znak między nimi pozostaje dodatni, ale jeśli $f(0)\neq f(1)$, drugi człon zyskuje dodatkowy znak minus względem pierwszego, zmieniając stan qubitu 0 z $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ na $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$. Zatem:

$$|\pi_2\rangle = \begin{cases} \pm[\frac{|0\rangle-|1\rangle}{\sqrt{2}}][\frac{|0\rangle+|1\rangle}{\sqrt{2}}] & \text{if} & f(0) = f(1) \\ \pm[\frac{|0\rangle-|1\rangle}{\sqrt{2}}][\frac{|0\rangle-|1\rangle}{\sqrt{2}}] &\text{if} & f(0) \neq f(1) \\ \end{cases}$$

Jaki jest stan $|\pi_3\rangle$?

Odpowiedź:

Teraz stan qubitu 0 wynosi albo $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$, albo $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$, w zależności od funkcji. Zastosowanie bramki Hadamarda da odpowiednio $|0\rangle$ lub $|1\rangle$.

$$|\pi_3\rangle = \begin{cases} \pm[\frac{|0\rangle-|1\rangle}{\sqrt{2}}]|0\rangle & \text{if} & f(0) = f(1) \\ \pm[\frac{|0\rangle-|1\rangle}{\sqrt{2}}]|1\rangle &\text{if} & f(0) \neq f(1) \\ \end{cases}$$

Analizując odpowiedzi na powyższe pytania, zauważamy, że dzieje się coś nieco zaskakującego. Chociaż $U_f$ nie robi niczego jawnie ze stanem qubitu 0, to ponieważ zmienia qubit 1 w zależności od stanu qubitu 0, może to powodować przesunięcie fazy w qubicie 0. Zjawisko to jest znane jako „phase-kickback" i zostało omówione bardziej szczegółowo w Lekcji 1: Kwantowe algorytmy zapytań kursu Fundamentals of Quantum Algorithms.

Teraz, gdy rozumiemy, jak działa ten algorytm, zaimplementujmy go przy użyciu Qiskit.

## Deutsch's algorithm:

## Step 1: Map the problem

# first, convert oracle circuit (above) to a single gate for drawing purposes. otherwise, the circuit is too large to display
blackbox = twobit_function(
    3
).to_gate()  # you may edit the number (1-4) inside "twobit_function()" to select among the four valid functions
blackbox.label = "$U_f$"

qc_deutsch = QuantumCircuit(2, 1)

qc_deutsch.x(1)
qc_deutsch.h(range(2))

qc_deutsch.barrier()
qc_deutsch.compose(twobit_function(2), inplace=True)
qc_deutsch.barrier()

qc_deutsch.h(0)
qc_deutsch.measure(0, 0)

qc_deutsch.draw("mpl")

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

qc_isa = pm.run(qc_deutsch)

# Step 3: Run the job on a real quantum computer

job = sampler.run([qc_isa], shots=1)
# job = sampler_sim.run([qc_isa],shots=1) # uncomment this line to run on simulator instead
res = job.result()
counts = res[0].data.c.get_counts()

# Step 4: Visualize and analyze results

## Analysis
print(counts)
if "1" in counts:
    print("balanced")
else:
    print("constant")

{'1': 1}
balanced

Algorytm Deutscha-Jozsy

Algorytm Deutscha był ważnym pierwszym krokiem w demonstrowaniu, jak komputer kwantowy może być bardziej wydajny niż klasyczny, ale był to jedynie skromny postęp: wymagał tylko jednego zapytania, w porównaniu z dwoma w przypadku klasycznym. W 1992 roku Deutsch i jego kolega, Richard Jozsa, rozszerzyli pierwotny algorytm dwuqubitowy na większą liczbę qubitów. Problem pozostał ten sam: określić, czy funkcja jest zrównoważona czy stała. Tym razem jednak funkcja przechodzi z $n$ bitów do jednego bitu. Albo funkcja zwraca 0 i 1 tę samą liczbę razy (jest zrównoważona), albo zawsze zwraca 1 lub zawsze 0 (jest stała).

Oto diagram obwodu algorytmu:

Algorytm ten działa tak samo jak algorytm Deutscha: efekt phase-kickback pozwala odczytać stan qubitu 0, aby określić, czy funkcja jest stała czy zrównoważona. Jest to nieco trudniejsze do zauważenia niż w przypadku dwuqubitowego algorytmu Deutscha, ponieważ stany będą zawierać sumy po $n$ qubitach — dlatego wyznaczenie tych stanów zostanie pozostawione jako opcjonalne ćwiczenie na koniec modułu. Algorytm zwróci ciąg bitów złożony z samych 0, jeśli funkcja jest stała, oraz ciąg bitów zawierający przynajmniej jedną 1, jeśli funkcja jest zrównoważona.

Aby zobaczyć, jak algorytm działa w Qiskit, najpierw musimy wygenerować naszą wyrocznię: losową funkcję, która jest zagwarantowana jako stała lub zrównoważona. Poniższy kod wygeneruje funkcję zrównoważoną z prawdopodobieństwem 50% i funkcję stałą z prawdopodobieństwem 50%. Nie martw się, jeśli nie rozumiesz w pełni kodu — jest on skomplikowany i nie jest konieczny do zrozumienia algorytmu kwantowego.

from qiskit import QuantumCircuit
import numpy as np

def dj_function(num_qubits):
    """
    Create a random Deutsch-Jozsa function.
    """

    qc_dj = QuantumCircuit(num_qubits + 1)
    if np.random.randint(0, 2):
        # Flip output qubits with 50% chance
        qc_dj.x(num_qubits)
    if np.random.randint(0, 2):
        # return constant circuit with 50% chance.
        return qc_dj

    # If the "if" statement above was "TRUE" then we've returned the constant
    # function and the function is complete. If not, we proceed in creating our
    # balanced function. Everything below is to produce the balanced function:

    # select half of all possible states at random:
    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_dj, bit_string):
        for qubit, bit in enumerate(reversed(bit_string)):
            if bit == "1":
                qc_dj.x(qubit)
        return qc_dj

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

    # qc_dj.barrier()

    return qc_dj

n = 3  # number of input qubits

oracle = dj_function(n)

display(oracle.draw("mpl"))

To jest funkcja wyroczni, która jest albo zrównoważona, albo stała. Czy patrząc na nią, możesz określić, czy wyjście na ostatnim qubicie zależy od wartości wprowadzonych dla pierwszych $n$ qubitów? Jeśli wyjście dla ostatniego qubitu zależy od pierwszych $n$ qubitów, czy możesz stwierdzić, czy to zależne wyjście jest zrównoważone?

Możemy stwierdzić, czy funkcja jest zrównoważona czy stała, patrząc na powyższy obwód, ale pamiętaj, że na potrzeby tego problemu traktujemy tę funkcję jako „czarną skrzynkę". Nie możemy zajrzeć do środka, żeby zobaczyć diagram obwodu. Zamiast tego musimy odpytywać skrzynkę.

Aby odpytać skrzynkę, używamy algorytmu Deutscha-Jozsy i określamy, czy funkcja jest stała czy zrównoważona:

blackbox = oracle.to_gate()
blackbox.label = "$U_f$"

qc_dj = QuantumCircuit(n + 1, n)
qc_dj.x(n)
qc_dj.h(range(n + 1))
qc_dj.barrier()
qc_dj.compose(blackbox, inplace=True)
qc_dj.barrier()
qc_dj.h(range(n))
qc_dj.measure(range(n), range(n))

qc_dj.decompose().decompose()

qc_dj.draw("mpl")

# Step 1: Map the problem

qc_dj = QuantumCircuit(n + 1, n)
qc_dj.x(n)
qc_dj.h(range(n + 1))
qc_dj.barrier()
qc_dj.compose(oracle, inplace=True)
qc_dj.barrier()
qc_dj.h(range(n))
qc_dj.measure(range(n), range(n))

qc_dj.decompose().decompose()

qc_dj.draw("mpl")

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

qc_isa = pm.run(qc_dj)

# Step 3: Run the job on a real quantum computer

job = sampler.run([qc_isa], shots=1)
# job = sampler_sim.run([qc_isa],shots=1) # uncomment this line to run on simulator instead
res = job.result()
counts = res[0].data.c.get_counts()

# Step 4: Visualize and analyze results

## Analysis
print(counts)

if (
    "0" * n in counts
):  # The D-J algorithm returns all zeroes if the function was constant
    print("constant")
else:
    print("balanced")  # anything other than all zeroes means the function is balanced.

{'110': 1}
balanced

Powyżej pierwszy wiersz wyjścia to ciąg bitów wyników pomiarów. Drugi wiersz wskazuje, czy ciąg bitów oznacza, że funkcja była zrównoważona czy stała. Jeśli ciąg bitów zawierał same zera, to funkcja była stała; jeśli nie — była zrównoważona. Tak więc przy jednym uruchomieniu powyższego obwodu kwantowego możemy określić, czy funkcja jest stała czy zrównoważona!

Sprawdź swoje zrozumienie

Przeczytaj poniższe pytania, zastanów się nad odpowiedziami, a następnie kliknij trójkąty, aby zobaczyć rozwiązania.

Ile zapytań potrzebowałby klasyczny komputer, aby z 100% pewnością określić, czy funkcja jest stała czy zrównoważona? Pamiętaj, że klasycznie jedno zapytanie pozwala zastosować funkcję tylko do jednego ciągu bitów.

Odpowiedź:

Istnieje $2^n$ możliwych ciągów bitów do sprawdzenia, a w najgorszym przypadku trzeba by przetestować $2^n/2+1$ z nich. Na przykład, gdyby funkcja była stała, a ty wciąż mierzył „1" jako wynik funkcji, nie mógłbyś być pewien, że jest ona naprawdę stała, dopóki nie sprawdziłeś ponad połowy wyników. Do tego momentu mógłbyś mieć po prostu pecha i ciągle mierzyć „1" na zrównoważonej funkcji. To jak rzucanie monetą wielokrotnie i za każdym razem wypadanie orła. Jest to mało prawdopodobne, ale nie niemożliwe.

Jak zmieniłaby się twoja powyższa odpowiedź, gdybyś musiał tylko mierzyć, aż jeden wynik (zrównoważony lub stały) stanie się bardziej prawdopodobny niż drugi? Ile zapytań byłoby potrzebnych w tym przypadku?

Odpowiedź:

W tym przypadku wystarczyłoby zmierzyć dwukrotnie. Jeśli dwa pomiary są różne, wiesz, że funkcja jest zrównoważona. Jeśli dwa pomiary są takie same, funkcja może być zrównoważona lub stała. Prawdopodobieństwo, że jest zrównoważona przy takim zestawie pomiarów wynosi: $\frac{1}{2}\frac{2^n /2 - 1}{2^n-1}$. Jest to mniej niż 1/2, więc w tym przypadku bardziej prawdopodobne jest, że funkcja jest stała.

Zatem algorytm Deutscha-Jozsy wykazał wykładnicze przyspieszenie w stosunku do deterministycznego algorytmu klasycznego (takiego, który zwraca odpowiedź z 100% pewnością), ale żadnego istotnego przyspieszenia w stosunku do probabilistycznego (takiego, który zwraca wynik, który prawdopodobnie jest poprawny).

Problem Bernsteina-Vaziraniego

W 1997 roku Ethan Bernstein i Umesh Vazirani wykorzystali algorytm Deutscha-Jozsy do rozwiązania bardziej szczegółowego, ograniczonego problemu w porównaniu do problemu Deutscha-Jozsy. Zamiast tylko rozróżniać między dwoma różnymi klasami funkcji, jak w przypadku D-J, Bernstein i Vazirani użyli algorytmu Deutscha-Jozsy, aby faktycznie nauczyć się ciągu zakodowanego w funkcji. Oto problem:

Funkcja $f:\{0,1\}^n \rightarrow \{0,1\}$ nadal przyjmuje $n$-bitowy ciąg i zwraca jeden bit. Ale teraz, zamiast obiecywać, że funkcja jest zrównoważona lub stała, obiecuje się, że funkcja jest iloczynem skalarnym między wejściowym ciągiem $x$ a pewnym tajnym $n$-bitowym ciągiem $s$, modulo 2. (Ten iloczyn skalarny modulo 2 nazywa się „binarnym iloczynem skalarnym".) Zadanie polega na odkryciu, jaki jest ten tajny, $n$-bitowy ciąg.

Inaczej mówiąc, mamy daną funkcję czarnej skrzynki $f: {0,1}^n \rightarrow {0,1}$, która spełnia $f(x) = s \cdot x$ dla pewnego ciągu $s$, i chcemy poznać ciąg $s$.

Przyjrzyjmy się, jak algorytm D-J rozwiązuje ten problem:

1. Najpierw Gate Hadamarda jest stosowana do $n$ qubitów wejściowych, a bramka NOT plus Hadamard jest stosowana do qubitu wyjściowego, tworząc stan:

$$|\Psi\rangle = |-\rangle_{n} \otimes |+\rangle_{n-1} \otimes |+\rangle_{n-2} \otimes ... \otimes |+\rangle_0$$

Stan qubitów od 1 do $n$ można zapisać prościej jako sumę po wszystkich $2^n$ bazowych stanach $n$-qubitowych $|00...00\rangle, |00...01\rangle, |000...11\rangle, ..., |111...11\rangle$. Zbiór tych stanów bazowych nazywamy $\Sigma^n$. (Więcej szczegółów znajdziesz w kursie Fundamentals of Quantum Algorithms.)

$$|\Psi\rangle = |-\rangle \otimes \frac{1}{\sqrt{2^n}}\sum\limits_{x \in \Sigma^n}{|x\rangle}$$

2. Następnie Gate $U_f$ jest stosowana do qubitów. Ta bramka przyjmuje pierwsze n qubitów jako wejście (które są teraz w równej superpozycji wszystkich możliwych $n$-bitowych ciągów) i stosuje funkcję $f(x)=s \cdot x$ do qubitu wyjściowego, tak że ten qubit jest teraz w stanie: $|- \oplus f(x)\rangle$. Dzięki mechanizmowi phase kickback stan tego qubitu pozostaje niezmieniony, ale niektóre człony w stanie qubitów wejściowych przyjmują znak minus:

$$|\Psi\rangle = |-\rangle \otimes \frac{1}{\sqrt{2^n}}\sum\limits_{x \in \Sigma^n}{(-1)^{f(x)}|x\rangle}$$

3. Teraz kolejny zestaw bramek Hadamarda jest stosowany do qubitów od 0 do $n-1$. Śledzenie znaków minus w tym przypadku może być trudne. Pomocna jest wiedza, że zastosowanie warstwy bramek Hadamarda do $n$ qubitów w standardowym stanie bazowym $|x\rangle$ można zapisać jako:

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

Więc stan staje się:

$$|\Psi\rangle = |-\rangle \otimes \frac{1}{2^n}\sum\limits_{x \in \Sigma^n}\sum\limits_{y \in \Sigma^n}{(-1)^{(s \cdot x) + (x \cdot y)}|y\rangle}$$

4. Następnym krokiem jest zmierzenie pierwszych $n$ bitów. Ale co zmierzymy? Okazuje się, że powyższy stan upraszcza się do: $|\Psi\rangle = |-\rangle \otimes |s\rangle$, ale to wcale nie jest oczywiste. Jeśli chcesz prześledzić matematykę, zapoznaj się z kursem Johna Watrousego Fundamentals of Quantum Algorithms. Sedno sprawy jest jednak takie, że mechanizm phase kickback powoduje, że qubity wejściowe są w stanie $|s\rangle$. Aby dowiedzieć się, jaki był tajny ciąg $s$, wystarczy zmierzyć qubity!

Sprawdź swoje zrozumienie

Przeczytaj poniższe pytania, zastanów się nad odpowiedziami, a następnie kliknij trójkąty, aby zobaczyć rozwiązania.

Zweryfikuj, że stan z Kroku 3 powyżej jest rzeczywiście stanem $|s\rangle$ dla szczególnego przypadku $n=1$.

Odpowiedź:

Gdy jawnie wypiszesz dwie sumy, powinieneś otrzymać stan z czterema członami (pomińmy stan wyjściowy $|-\rangle$):

$$|\Psi\rangle = \frac{1}{2}[|0\rangle + (-1)^s |0\rangle + |1\rangle + (-1)^{(s+1)} |1\rangle]$$

Jeśli $s=0$, to pierwsze dwa człony dodają się konstruktywnie, a ostatnie dwa się znoszą, pozostawiając nas z $|\Psi\rangle = |0\rangle$. Jeśli $s=1$, to ostatnie dwa człony dodają się konstruktywnie, a pierwsze dwa się znoszą, pozostawiając nas z $|\Psi\rangle = |1\rangle$. Tak więc w obu przypadkach $|\Psi\rangle = |s\rangle$. Mamy nadzieję, że ten najprostszy przypadek daje ci pewne wyobrażenie o tym, jak działa ogólny przypadek z $n$ qubitami: wszystkie człony inne niż $|s\rangle$ interferują i znikają, pozostawiając jedynie stan $|s\rangle$.

Jak ten sam algorytm może rozwiązywać zarówno problem Bernsteina-Vaziraniego, jak i Deutscha-Jozsy? Aby to zrozumieć, pomyśl o funkcjach Bernsteina-Vaziraniego, które mają postać $f(x) = s \cdot x$. Czy te funkcje są również funkcjami Deutscha-Jozsy? To znaczy, ustal, czy funkcje tej postaci spełniają obietnicę problemu Deutscha-Jozsy: że są albo stałe, albo zrównoważone. Jak to pomaga nam zrozumieć, w jaki sposób ten sam algorytm rozwiązuje dwa różne problemy?

Odpowiedź:

Każda funkcja Bernsteina-Vaziraniego postaci $f(x) = s \cdot x$ spełnia również obietnicę problemu Deutscha-Jozsy: jeśli s=00...00, to funkcja jest stała (zawsze zwraca 0 dla każdego ciągu x). Jeśli s jest dowolnym innym ciągiem, to funkcja jest zrównoważona. Tak więc zastosowanie algorytmu Deutscha-Jozsy do jednej z tych funkcji jednocześnie rozwiązuje oba problemy! Zwraca ciąg, a jeśli ten ciąg to 00...00, to wiemy, że jest stały; jeśli jest w nim przynajmniej jedna „1", wiemy, że jest zrównoważony.

Możemy również zweryfikować, że ten algorytm skutecznie rozwiązuje problem Bernsteina-Vaziraniego, testując go eksperymentalnie. Najpierw tworzymy funkcję B-V, która żyje wewnątrz czarnej skrzynki:

# Step 1: Map the problem

def bv_function(s):
    """
    Create a Bernstein-Vazirani function from a string of 1s and 0s.
    """
    qc = QuantumCircuit(len(s) + 1)
    for index, bit in enumerate(reversed(s)):
        if bit == "1":
            qc.cx(index, len(s))
    return qc

display(bv_function("1000").draw("mpl"))

string = "1000"  # secret string that we'll pretend we don't know or have access to
n = len(string)

qc = QuantumCircuit(n + 1, n)
qc.x(n)
qc.h(range(n + 1))
qc.barrier()
# qc.compose(oracle, inplace = True)
qc.compose(bv_function(string), inplace=True)
qc.barrier()
qc.h(range(n))
qc.measure(range(n), range(n))

qc.draw("mpl")

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

qc_isa = pm.run(qc)

# Step 3: Run the job on a real quantum computer

job = sampler.run([qc_isa], shots=1)
# job = sampler_sim.run([qc_isa],shots=1) # uncomment this line to run on simulator instead
res = job.result()
counts = res[0].data.c.get_counts()

# Step 4: Visualize and analyze results

## Analysis
print(counts)

{'0000': 1}

Tak więc przy jednym zapytaniu algorytm Deutscha-Jozsy zwróci ciąg $s$ użyty w funkcji: $f(x)=x \cdot s$, gdy zastosujemy go do problemu Bernsteina-Vaziraniego. Przy użyciu algorytmu klasycznego do rozwiązania tego samego problemu potrzeba by $n$ zapytań.

Podsumowanie

Mamy nadzieję, że dzięki tym prostym przykładom udało nam się dać ci lepszą intuicję co do tego, w jaki sposób komputery kwantowe mogą wykorzystywać superpozycję, splątanie i interferencję, aby przewyższać klasyczne komputery.

Algorytm Deutscha-Jozsy ma ogromne znaczenie historyczne, ponieważ był pierwszym, który wykazał jakiekolwiek przyspieszenie w stosunku do algorytmu klasycznego — choć było to jedynie przyspieszenie wielomianowe. Algorytm Deutscha-Jozsy to dopiero początek tej historii.

Po zastosowaniu algorytmu do rozwiązania własnego problemu, Bernstein i Vazirani wykorzystali go jako podstawę bardziej złożonego, rekurencyjnego problemu zwanego rekurencyjnym próbkowaniem Fouriera. Ich rozwiązanie oferowało ponadwielomianowe przyspieszenie w stosunku do algorytmów klasycznych. A nawet przed Bernsteinem i Vazirani, Peter Shor opracował już swój słynny algorytm, który pozwala komputerom kwantowym rozkładać duże liczby na czynniki wykładniczo szybciej niż jakikolwiek algorytm klasyczny. Wyniki te zbiorowo pokazały ekscytujący potencjał przyszłych komputerów kwantowych i zachęciły fizyków oraz inżynierów do urzeczywistnienia tej przyszłości.

Pytania

Wykładowcy mogą poprosić o wersje tych notebooków z kluczami odpowiedzi i wskazówkami dotyczącymi umieszczenia ich w typowych programach nauczania, wypełniając tę krótką ankietę dotyczącą sposobu wykorzystania notebooków.

Kluczowe pojęcia

• Algorytmy Deutscha i Deutscha-Jozsy wykorzystują kwantowy paralelizm w połączeniu z interferencją, aby znaleźć odpowiedź na problem szybciej, niż może to zrobić komputer klasyczny.
• Mechanizm cofnięcia fazy to kontrprzykładowe zjawisko kwantowe, które przenosi operacje na jednym Qubicie do fazy innego Qubitu. Algorytmy Deutscha i Deutscha-Jozsy korzystają z tego mechanizmu.
• Algorytm Deutscha-Jozsy oferuje wielomianowe przyspieszenie w stosunku do każdego deterministycznego algorytmu klasycznego.
• Algorytm Deutscha-Jozsy można zastosować do innego problemu, zwanego problemem Bernsteina-Vaziraniego, aby znaleźć ukryty ciąg zakodowany w funkcji.

Prawda/fałsz

1. P/F Algorytm Deutscha jest szczególnym przypadkiem algorytmu Deutscha-Jozsy, gdzie wejściem jest jeden Qubit.
2. P/F Algorytmy Deutscha i Deutscha-Jozsy wykorzystują kwantową superpozycję i interferencję, aby osiągnąć swoją efektywność.
3. P/F Algorytm Deutscha-Jozsy wymaga wielu ewaluacji funkcji, aby określić, czy funkcja jest stała, czy zrównoważona.
4. P/F „Algorytm Bernsteina-Vaziraniego" jest tak naprawdę tym samym algorytmem co algorytm Deutscha-Jozsy, zastosowanym do innego problemu.
5. P/F Algorytm Bernsteina-Vaziraniego może jednocześnie znajdować wiele ukrytych ciągów.

Krótka odpowiedź

1. Ile czasu zajęłoby klasycznemu algorytmowi rozwiązanie problemu Deutscha-Jozsy w najgorszym przypadku?

2. Ile czasu zajęłoby klasycznemu algorytmowi rozwiązanie problemu Bernsteina-Vaziraniego? Jakie przyspieszenie oferuje w tym przypadku algorytm DJ?

3. Opisz mechanizm cofnięcia fazy i to, jak działa on przy rozwiązywaniu problemów Deutscha-Jozsy i Bernsteina-Vaziraniego.

Zadanie dodatkowe

1. Algorytm Deutscha-Jozsy: Przypomnij sobie, że powyżej mieliście pytanie z prośbą o wyznaczenie pośrednich stanów Qubitów $\pi_1$ i $\pi_2$ algorytmu Deutscha. Zrób to samo dla pośrednich stanów $n+1$ Qubitów $\pi_1$ i $\pi_2$ algorytmu Deutscha-Jozsy, dla szczególnego przypadku $n=2$. Następnie zweryfikuj, że $\pi_3 = |-\rangle \otimes \sum\limits_{x_0...x_n}(-1)^{f(x_0...x_n)}|x_0 ... x_n\rangle$, ponownie dla szczególnego przypadku $n=2$.