Algorytm Grovera

W tym module Qiskit w klasie uczniowie 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, uczniowie będą musieli założyć konto IBM Quantum®, postępując zgodnie z krokami opisanymi w przewodniku Skonfiguruj konto IBM Cloud.

Ten moduł był testowany i wykorzystał 12 sekund czasu QPU. Jest to szacunek w dobrej wierze; rzeczywiste użycie może się różnić.

# Added by doQumentation — required packages for this notebook
!pip install -q qiskit 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'

Wprowadzenie

Algorytm Grovera to fundamentalny algorytm kwantowy, który rozwiązuje problem nieustrukturyzowanego wyszukiwania: mając zbiór $N$ elementów oraz sposób sprawdzania, czy dany element jest tym, którego szukamy, jak szybko można znaleźć poszukiwany element? W obliczeniach klasycznych, jeśli dane są nieposortowane i nie ma żadnej struktury do wykorzystania, najlepszym podejściem jest sprawdzanie każdego elementu po kolei, co prowadzi do złożoności zapytaniowej $O(N)$ — średnio trzeba sprawdzić około połowy elementów przed znalezieniem celu.

Algorytm Grovera, wprowadzony przez Lova Grovera w 1996 roku, pokazuje, jak komputer kwantowy może rozwiązać ten problem znacznie wydajniej, wymagając jedynie $O(\sqrt{N})$ kroków do znalezienia zaznaczonego elementu z wysokim prawdopodobieństwem. Oznacza to kwadratowe przyspieszenie w porównaniu z metodami klasycznymi, co jest istotne w przypadku dużych zbiorów danych.

Algorytm działa w następującym kontekście:

• Konfiguracja problemu: Masz funkcję $f(x)$, która zwraca 1, jeśli $x$ jest szukanym elementem, i 0 w przeciwnym razie. Funkcja ta jest często nazywana wyrocznią lub czarną skrzynką, ponieważ o danych można dowiedzieć się jedynie poprzez odpytywanie $f(x)$.
• Użyteczność podejścia kwantowego: Podczas gdy klasyczne algorytmy dla tego problemu wymagają średnio $N/2$ zapytań, algorytm Grovera może znaleźć rozwiązanie w około $\pi\sqrt{N}/4$ zapytaniach, co jest znacznie szybsze dla dużych $N$.
• Jak to działa (na wysokim poziomie ogólności):
  • Komputer kwantowy najpierw tworzy superpozycję wszystkich możliwych stanów, reprezentując jednocześnie wszystkie możliwe elementy.
  • Następnie wielokrotnie stosuje sekwencję operacji kwantowych (iteracja Grovera), która wzmacnia prawdopodobieństwo poprawnej odpowiedzi i osłabia pozostałe.
  • Po wystarczającej liczbie iteracji pomiar stanu kwantowego daje poprawną odpowiedź z wysokim prawdopodobieństwem.

Poniżej znajduje się bardzo uproszczony diagram algorytmu Grovera, pomijający wiele szczegółów. Bardziej szczegółowy diagram znajdziesz w tym artykule.

Kilka rzeczy wartych uwagi na temat algorytmu Grovera:

• Jest optymalny dla nieustrukturyzowanego wyszukiwania: żaden algorytm kwantowy nie może rozwiązać tego problemu przy mniej niż $O(\sqrt{N})$ zapytaniach.
• Zapewnia jedynie kwadratowe, a nie wykładnicze, przyspieszenie — w przeciwieństwie do niektórych innych algorytmów kwantowych (na przykład algorytmu Shora do faktoryzacji).
• Ma praktyczne implikacje, takie jak potencjalne przyspieszenie ataków brute-force na systemy kryptograficzne, choć przyspieszenie nie jest wystarczające, aby samodzielnie złamać większość nowoczesnych szyfrów.

Dla studentów studiów licencjackich zaznajomionych z podstawowymi koncepcjami obliczeniowymi i modelami zapytaniowymi, algorytm Grovera stanowi czytelną ilustrację tego, jak obliczenia kwantowe mogą przewyższać podejścia klasyczne w przypadku pewnych problemów, nawet gdy poprawa jest „jedynie" kwadratowa. Służy też jako punkt wejścia do zrozumienia bardziej zaawansowanych algorytmów kwantowych i szerszego potencjału obliczeń kwantowych.

Wzmocnienie amplitudy to ogólny algorytm kwantowy, lub podprogram, który można wykorzystać do uzyskania kwadratowego przyspieszenia względem garstki klasycznych algorytmów. Algorytm Grovera był pierwszym, który zademonstrował to przyspieszenie dla nieustrukturyzowanych problemów wyszukiwania. Sformułowanie problemu wyszukiwania Grovera wymaga funkcji wyroczni, która zaznacza jeden lub więcej obliczeniowych stanów bazowych jako stany, które chcemy znaleźć, oraz obwodu wzmacniającego, który zwiększa amplitudę zaznaczonych stanów, tłumiąc tym samym pozostałe stany.

Tutaj pokazujemy, jak konstruować wyroczni Grovera i używać GroverOperator z biblioteki obwodów Qiskit, aby łatwo skonfigurować instancję wyszukiwania Grovera. Primityw środowiska uruchomieniowego Sampler umożliwia bezproblemowe wykonywanie obwodów Grovera.

Matematyka

Załóżmy, że istnieje funkcja $f$ odwzorowująca łańcuchy binarne na pojedynczą zmienną binarną, co oznacza

$$f: \Sigma^n \rightarrow \Sigma$$

Jeden przykład zdefiniowany na $\Sigma^6$ to

$$f(x)= \begin{cases} 1 \qquad \text{jeśli }x=\{010101\}\\ 0 \qquad \text{w przeciwnym razie } \end{cases}$$

Inny przykład zdefiniowany na $\Sigma^{2n}$ to

$$f(x)= \begin{cases} 1 \qquad \text{jeśli w łańcuchu jest równa liczba jedynek i zer}\\ 0 \qquad \text{w przeciwnym razie } \end{cases}$$

Twoim zadaniem jest znalezienie stanów kwantowych odpowiadających tym argumentom $x$ funkcji $f(x)$, które są odwzorowane na 1. Innymi słowy, znajdź wszystkie $\{x_1\}\in \Sigma^n$ takie, że $f(x_1)=1$ (lub jeśli nie istnieje rozwiązanie, zgłoś ten fakt). Nie-rozwiązania będziemy oznaczać jako $x_0$. Oczywiście będziemy to robić na komputerze kwantowym, używając stanów kwantowych, więc przydatne jest wyrażenie tych łańcuchów binarnych jako stanów:

$$\{|x_1\rangle\} \in |\Sigma^n\rangle$$

Używając notacji stanów kwantowych (notacja Diraca), szukamy jednego lub więcej specjalnych stanów $\{|x_1\rangle\}$ w zbiorze $N=2^n$ możliwych stanów, gdzie $n$ to liczba Qubitów, a nie-rozwiązania oznaczamy $\{|x_0\rangle\}.$

Możemy myśleć o funkcji $f$ jako dostarczonej przez wyrocznię: czarną skrzynkę, którą możemy odpytywać, aby określić jej wpływ na stan $|x\rangle.$ W praktyce często znamy tę funkcję, ale jej implementacja może być bardzo skomplikowana, co oznacza, że zmniejszenie liczby zapytań lub zastosowań $f$ może być istotne. Alternatywnie możemy wyobrazić sobie paradygmat, w którym jedna osoba odpytuje wyrocznię kontrolowaną przez inną osobę, tak że nie znamy funkcji wyroczni — znamy jedynie jej działanie na konkretnych stanach uzyskiwane poprzez zapytania.

Jest to "problem nieustrukturyzowanego wyszukiwania", ponieważ nie ma w $f$ niczego szczególnego, co ułatwiałoby nasze poszukiwania. Dane wyjściowe nie są posortowane ani nie jest wiadome, że rozwiązania grupują się, i tak dalej. Jako analogię rozważmy stare papierowe książki telefoniczne. To nieustrukturyzowane wyszukiwanie byłoby jak przeglądanie jej w poszukiwaniu określonego numeru, a nie jak przeglądanie alfabetycznie ułożonej listy nazwisk.

W przypadku szukania jednego rozwiązania, klasycznie wymaga to liczby zapytań liniowej w $N$. Oczywiście możesz znaleźć rozwiązanie za pierwszym razem, lub możesz nie znaleźć żadnego rozwiązania w pierwszych $N-1$ próbach, tak że musisz zapytać o $N$-te wejście, aby sprawdzić, czy w ogóle istnieje jakieś rozwiązanie. Ponieważ funkcje nie mają żadnej struktury, którą można by wykorzystać, będziesz potrzebować średnio $N/2$ prób. Algorytm Grovera wymaga liczby zapytań lub obliczeń $f$, która skaluje się jak $\sqrt{N}.$

Zarys obwodów w algorytmie Grovera

Pełne matematyczne omówienie algorytmu Grovera można znaleźć na przykład w Podstawy algorytmów kwantowych, kursie Johna Watrusa na IBM Quantum Learning. Skrócone omówienie znajduje się w dodatku na końcu tego modułu. Na razie omówimy jednak tylko ogólną strukturę obwodu kwantowego implementującego algorytm Grovera.

Algorytm Grovera można podzielić na następujące etapy:

• Przygotowanie początkowej superpozycji (zastosowanie bramek Hadamarda do wszystkich Qubitów)
• „Zaznaczenie" docelowego stanu (stanów) poprzez odwrócenie fazy
• Etap „dyfuzji", w którym bramki Hadamarda i odwrócenie fazy są stosowane do wszystkich Qubitów.
• Możliwe powtórzenia etapów zaznaczania i dyfuzji w celu maksymalizacji prawdopodobieństwa pomiaru stanu docelowego
• Pomiar

Często bramka zaznaczająca $Z_f$ oraz warstwy dyfuzji składające się z $H,$ $Z_{\text{OR}}$ i $H$ są łącznie nazywane „operatorem Grovera". Na tym diagramie pokazano tylko jedno powtórzenie operatora Grovera.

Bramki Hadamarda $H$ są dobrze znane i szeroko stosowane w obliczeniach kwantowych. Bramka Hadamarda tworzy stany superpozycji. Konkretnie jest zdefiniowana przez

$$H|0\rangle = \frac{1}{\sqrt{2}}\left(|0\rangle+|1\rangle\right)\\ H|1\rangle = \frac{1}{\sqrt{2}}\left(|0\rangle-|1\rangle\right)$$

Jej działanie na dowolny inny stan jest zdefiniowane przez liniowość. W szczególności warstwa bramek Hadamarda pozwala nam przejść od stanu początkowego, w którym wszystkie Qubity są w $|0\rangle$ (oznaczanego $|0\rangle^{\otimes n}$), do stanu, w którym każdy Qubit ma pewne prawdopodobieństwo zmierzenia $|0\rangle$ lub $|1\rangle$; pozwala nam to badać przestrzeń wszystkich możliwych stanów inaczej niż w obliczeniach klasycznych.

Ważna właściwość poboczna bramki Hadamarda polega na tym, że drugie jej zastosowanie może cofnąć takie stany superpozycji:

$$H\frac{1}{\sqrt{2}}\left(|0\rangle+|1\rangle\right)=|0\rangle\\ H\frac{1}{\sqrt{2}}\left(|0\rangle-|1\rangle\right)=|1\rangle$$

Będzie to ważne za chwilę.

Sprawdź swoje rozumienie

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

Wychodząc z definicji bramki Hadamarda, wykaż, że drugie zastosowanie bramki Hadamarda cofa takie superpozycje, jak stwierdzono powyżej.

Odpowiedź:

Gdy zastosujemy X do stanu $|+\rangle$, otrzymujemy wartość +1, a do stanu $|-\rangle$ otrzymujemy -1, więc jeśli mielibyśmy rozkład 50-50, uzyskalibyśmy wartość oczekiwaną równą 0.

Bramka $Z_\text{OR}$ jest mniej powszechna i jest zdefiniowana jako

$$\text{Z}_\text{OR}|x\rangle = \begin{cases} |x\rangle & \text{jeśli } x = 0^n \\ -|x\rangle & \text{jeśli } x \neq 0^n \end{cases} \qquad \forall x \in \Sigma^n$$

Na koniec bramka $Z_f$ jest zdefiniowana przez

$$Z_f:|x\rangle \rightarrow (-1)^{f(x)}|x\rangle \qquad \forall x \in \Sigma^n$$

Zauważmy, że efektem tego jest to, że $Z_f$ odwraca znak docelowego stanu, dla którego $f(x) = 1$, i pozostawia pozostałe stany bez zmian.

Na bardzo wysokim, abstrakcyjnym poziomie możesz myśleć o krokach w obwodzie w następujący sposób:

• Pierwsza warstwa Hadamarda: wprowadza Qubity w superpozycję wszystkich możliwych stanów.
• $Z_f$: zaznacza docelowy stan (stany) poprzez dodanie znaku „-" z przodu. Nie zmienia to natychmiast prawdopodobieństw pomiaru, ale zmienia zachowanie stanu docelowego w kolejnych krokach.
• Kolejna warstwa Hadamarda: znak „-" wprowadzony w poprzednim kroku zmieni względny znak między pewnymi wyrazami. Ponieważ bramki Hadamarda zamieniają jedną mieszaninę stanów obliczeniowych $(|0\rangle+|1\rangle)/\sqrt{2}$ w jeden stan obliczeniowy $|0\rangle,$ a $(|0\rangle-|1\rangle)/\sqrt{2}$ w $|1\rangle$, ta różnica znaków względnych może teraz zacząć odgrywać rolę w tym, jakie stany są mierzone.
• Stosowana jest ostatnia warstwa bramek Hadamarda, a następnie wykonywane są pomiary. Zobaczymy bardziej szczegółowo, jak to działa, w następnej sekcji.

Przykład

Aby lepiej zrozumieć, jak działa algorytm Grovera, przeanalizujmy mały, dwuqubitowy przykład. Można go uznać za opcjonalny dla tych, którzy nie skupiają się na mechanice kwantowej i notacji Diraca. Ale dla tych, którzy chcą poważnie pracować z komputerami kwantowymi, jest to wysoce zalecane.

Oto diagram obwodu z zaznaczonymi stanami kwantowymi w różnych miejscach. Zauważ, że przy zaledwie dwóch Qubitach istnieją tylko cztery możliwe stany, które można zmierzyć w jakichkolwiek okolicznościach: $|00\rangle$, $|01\rangle$, $|10\rangle$ i $|11\rangle$.

Przyjmijmy, że wyrocznia ($Z_f$, nieznana nam) zaznacza stan $|01\rangle$. Przeanalizujemy działanie każdego zestawu bramek kwantowych, w tym wyroczni, i zobaczymy, jaki rozkład możliwych stanów pojawia się w chwili pomiaru. Na samym początku mamy

$$|\psi_0\rangle = |00\rangle$$

Korzystając z definicji bramek Hadamarda, mamy

$$|\psi_1\rangle = \frac{1}{2}\left(|0\rangle+|1\rangle\right)\left(|0\rangle+|1\rangle\right)=\frac{1}{2}\left(|00\rangle+|01\rangle+|10\rangle+|11\rangle\right)$$

Teraz wyrocznia zaznacza stan docelowy:

$$|\psi_2\rangle = \frac{1}{2}\left(|00\rangle-|01\rangle+|10\rangle+|11\rangle\right)$$

Zauważmy, że w tym stanie wszystkie cztery możliwe wyniki mają takie samo prawdopodobieństwo zmierzenia. Wszystkie mają wagę o wartości bezwzględnej $1/2,$ co oznacza, że każdy z nich ma szansę $|1/2|^2=1/4$ na zmierzenie. Tak więc, choć stan $|01\rangle$ jest zaznaczony poprzez fazę „-", nie spowodowało to jeszcze zwiększenia prawdopodobieństwa zmierzenia tego stanu. Kontynuujemy, stosując następną warstwę bramek Hadamarda.

$$\begin{aligned} |\psi_3\rangle = &\frac{1}{4}\left(|00\rangle+|01\rangle+|10\rangle+|11\rangle\right)\\ -&\frac{1}{4}\left(|00\rangle-|01\rangle+|10\rangle-|11\rangle\right)\\ +&\frac{1}{4}\left(|00\rangle+|01\rangle-|10\rangle-|11\rangle\right)\\ +&\frac{1}{4}\left(|00\rangle-|01\rangle-|10\rangle+|11\rangle\right) \end{aligned}$$

Łącząc podobne wyrazy, otrzymujemy

$$|\psi_3\rangle = \frac{1}{2}\left(|00\rangle+|01\rangle-|10\rangle+|11\rangle\right)$$

Teraz $Z_{\text{OR}}$ odwraca znak wszystkich stanów oprócz $|00\rangle$:

$$|\psi_4\rangle = \frac{1}{2}\left(|00\rangle-|01\rangle+|10\rangle-|11\rangle\right)$$

I na koniec stosujemy ostatnią warstwę bramek Hadamarda:

$$\begin{aligned} |\psi_5\rangle =&\frac{1}{4}\left(|00\rangle+|01\rangle+|10\rangle+|11\rangle\right)\\ -&\frac{1}{4}\left(|00\rangle-|01\rangle+|10\rangle-|11\rangle\right)\\ +&\frac{1}{4}\left(|00\rangle+|01\rangle-|10\rangle-|11\rangle\right)\\ -&\frac{1}{4}\left(|00\rangle-|01\rangle-|10\rangle+|11\rangle\right) \end{aligned}$$

Warto samodzielnie połączyć te wyrazy, aby przekonać się, że wynik to rzeczywiście:

$$|\psi_5\rangle =|01\rangle$$

Oznacza to, że prawdopodobieństwo zmierzenia $|01\rangle$ wynosi 100% (przy braku szumów i błędów), a prawdopodobieństwo zmierzenia dowolnego innego stanu wynosi zero.

Ten dwuqubitowy przykład był wyjątkowo czystym przypadkiem; algorytm Grovera nie zawsze da 100% szansy na zmierzenie stanu docelowego. Raczej wzmacnia prawdopodobieństwo zmierzenia stanu docelowego. Ponadto operator Grovera może wymagać więcej niż jednego powtórzenia.

W następnej sekcji wprowadzimy ten algorytm w praktykę, używając prawdziwych komputerów kwantowych IBM®.

Oczywiste zastrzeżenie

Aby zastosować algorytm Grovera, musieliśmy zbudować operator Grovera, co oznacza, że musimy umieć odwracać fazę stanów spełniających nasze kryteria rozwiązania. Nasuwa się pytanie: jeśli znamy nasz zbiór rozwiązań tak dobrze, że możemy zaprojektować obwód kwantowy oznaczający każde z nich, to czego właściwie szukamy?! Odpowiedź jest trójdzielna i będziemy do niej wracać przez cały ten samouczek:

(1) Tego rodzaju algorytmy zapytań często angażują dwie strony: jedną, która dysponuje wyrocznią określającą kryteria rozwiązania, i drugą, która stara się odgadnąć lub znaleźć stan będący rozwiązaniem. Fakt, że jedna osoba potrafi zbudować wyrocznię, nie eliminuje potrzeby przeszukiwania.

(2) Istnieją problemy, w których łatwiej jest określić kryterium rozwiązania, niż znaleźć samo rozwiązanie. Najlepiej znany przykład to identyfikacja pierwszych czynników dużych liczb. Algorytm Grovera nie jest szczególnie skuteczny w rozwiązywaniu tego konkretnego problemu — do faktoryzacji na czynniki pierwsze używalibyśmy algorytmu Shora. To tylko przykład pokazujący, że znajomość kryterium dotyczącego zachowania stanu nie zawsze jest równoznaczna ze znajomością samego stanu.

(3) Algorytm Grovera nie zwraca wyłącznie danych klasycznych. Rzeczywiście, jeśli dokonamy pomiaru stanu końcowego po $t$ powtórzeniach operatora Grovera, najprawdopodobniej uzyskamy klasyczne informacje identyfikujące stan będący rozwiązaniem. Ale co, jeśli nie chcemy informacji klasycznych — co, jeśli chcemy stanu rozwiązania przygotowanego na komputerze kwantowym do dalszego wykorzystania w innym algorytmie? Algorytm Grovera faktycznie produkuje stan kwantowy, w którym stany będące rozwiązaniami mają silnie wzmocnione amplitudy. Można więc spodziewać się, że algorytm Grovera będzie występował jako podprogram w bardziej złożonych algorytmach kwantowych.

Mając to na uwadze, przejdźmy przez kilka przykładów. Zaczniemy od przykładu, w którym stan będący rozwiązaniem jest wyraźnie określony, abyśmy mogli śledzić logikę algorytmu, a następnie przejdziemy do przykładów, w których użyteczność algorytmu Grovera staje się bardziej oczywista.

Ogólne importy i podejście

Zaczynamy od zaimportowania kilku niezbędnych pakietów.

# Built-in modules
import math

# Imports from Qiskit
from qiskit import QuantumCircuit
from qiskit.circuit.library import grover_operator, MCMTGate, ZGate
from qiskit.visualization import plot_distribution
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

W tym i w innych samouczkach będziemy korzystać z podejścia do obliczeń kwantowych zwanego „wzorcami Qiskit" (Qiskit patterns), które dzieli przepływy 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 przy użyciu prymitywów Qiskit Runtime
• Krok 4: Przetwarzanie końcowe i klasyczna analiza

Będziemy generalnie trzymać się tych kroków, choć nie zawsze będziemy je jawnie oznaczać.

Aktywność 1: Znajdź pojedynczy zadany stan docelowy

Krok 1: Odwzorowanie klasycznych danych wejściowych na problem kwantowy

Potrzebujemy bramki zapytania fazowego, która nada stałą fazę (-1) stanom będącym rozwiązaniami, a stany niebędące rozwiązaniami pozostawi bez zmian. Inaczej mówiąc, algorytm Grovera wymaga wyroczni, która wskazuje jeden lub więcej zaznaczonych stanów bazowych przestrzeni obliczeniowej, gdzie „zaznaczony" oznacza stan z fazą -1. Realizuje się to przy użyciu bramki kontrolowanej Z lub jej wielokontrolowanego uogólnienia na $N$ Qubitów. Aby zobaczyć, jak to działa, rozważmy konkretny przykład ciągu bitowego {110}. Chcemy Circuit, który działa na stanie $|\psi\rangle = |q_2,q_1,q_0\rangle$ i stosuje fazę, jeśli $|\psi\rangle = |011\rangle$ (kolejność bitów binarnych jest odwrócona ze względu na konwencję w Qiskit, która umieszcza najmniej znaczący Qubit — często oznaczony 0 — po prawej stronie).

Chcemy zatem Circuit $Z_f$, który realizuje

$$Z_f|\psi\rangle = \begin{cases} -|\psi\rangle \qquad \text{if} \qquad |\psi\rangle = |011\rangle \\ |\psi\rangle \qquad \text{if} \qquad |\psi\rangle \neq |011\rangle\end{cases}$$

Możemy użyć bramki wielokrotnie kontrolowanej z wieloma celami (MCMTGate), aby zastosować bramkę Z kontrolowaną przez wszystkie Quibty (odwrócenie fazy, gdy wszystkie Qubity są w stanie $|1\rangle$). Oczywiście niektóre Qubity w naszym docelowym stanie mogą być w stanie $|0\rangle$. Dlatego dla tych Qubitów musimy najpierw zastosować bramkę X, następnie wykonać wielokrotnie kontrolowaną bramkę Z, a potem zastosować kolejną bramkę X, aby cofnąć naszą zmianę. Wygląd MCMTGate:

mcmt_ex = QuantumCircuit(3)
mcmt_ex.compose(MCMTGate(ZGate(), 3 - 1, 1), inplace=True)
mcmt_ex.draw(output="mpl", style="iqp")

Zauważ, że w procesie kontroli może uczestniczyć wiele Qubitów (tutaj trzy), ale żaden z nich nie jest oznaczony jako cel. Dzieje się tak, ponieważ cały stan otrzymuje ogólną zmianę znaku (odwrócenie fazy); bramka oddziałuje na wszystkie Qubity jednakowo. Różni się to od wielu innych bramek wieloqubitowych, takich jak bramka CX, która ma jeden Qubit kontrolny i jeden Qubit docelowy.

W poniższym kodzie definiujemy bramkę zapytania fazowego (wyrocznię), która robi dokładnie to, co opisaliśmy powyżej: zaznacza jeden lub więcej wejściowych stanów bazowych określonych przez ich reprezentację w postaci ciągu bitowego. Bramka MCMT służy do implementacji wielokontrolowanej bramki Z.

def grover_oracle(marked_states):
    """Build a Grover oracle for multiple marked states

    Here we assume all input marked states have the same number of bits

    Parameters:
        marked_states (str or list): Marked states of oracle

    Returns:
        QuantumCircuit: Quantum circuit representing Grover oracle
    """
    if not isinstance(marked_states, list):
        marked_states = [marked_states]
    # Compute the number of qubits in circuit
    num_qubits = len(marked_states[0])

    qc = QuantumCircuit(num_qubits)
    # Mark each target state in the input list
    for target in marked_states:
        # Flip target bitstring to match Qiskit bit-ordering
        rev_target = target[::-1]
        # Find the indices of all the '0' elements in bitstring
        zero_inds = [
            ind for ind in range(num_qubits) if rev_target.startswith("0", ind)
        ]
        # Add a multi-controlled Z-gate with pre- and post-applied X-gates (open-controls)
        # where the target bitstring has a '0' entry
        qc.x(zero_inds)
        qc.compose(MCMTGate(ZGate(), num_qubits - 1, 1), inplace=True)
        qc.x(zero_inds)
    return qc

Teraz wybieramy konkretny „zaznaczony" stan jako nasz cel i stosujemy właśnie zdefiniowaną funkcję. Zobaczmy, jaki Circuit został stworzony.

marked_states = ["1110"]
oracle = grover_oracle(marked_states)
oracle.draw(output="mpl", style="iqp")

Jeśli Qubity 1–3 są w stanie $|1\rangle$, a Qubit 0 jest początkowo w stanie $|0\rangle$, pierwsza bramka X przerzuci Qubit 0 do $|1\rangle$ i wszystkie Qubity będą w stanie $|1\rangle.$ Oznacza to, że bramka MCMT zastosuje ogólną zmianę znaku, czyli odwrócenie fazy, zgodnie z zamierzeniem. W każdym innym przypadku albo Qubity 1–3 są w stanie $|0\rangle$, albo Qubit 0 zostaje przerzucony do stanu $|0\rangle$ i odwrócenie fazy nie zostanie zastosowane. Widzimy, że ten Circuit rzeczywiście zaznacza nasz pożądany stan $|0111\rangle$, czyli ciąg bitowy {1110}. Pełny operator Grovera składa się z bramki zapytania fazowego (wyroczni), warstw Hadamarda i operatora $Z_\text{OR}$. Możemy użyć wbudowanej funkcji grover_operator, aby zbudować go na podstawie wyroczni zdefiniowanej powyżej.

grover_op = grover_operator(oracle)
grover_op.decompose(reps=0).draw(output="mpl", style="iqp")

Jak argumentowaliśmy powyżej, może być konieczne wielokrotne stosowanie operatora Grovera. Optymalną liczbę iteracji $t$, która maksymalizuje amplitudę stanu docelowego przy braku szumów, można uzyskać z następującego wyrażenia:

$$(2t+1)\theta = (2t+1)\sin^{-1}\left( \sqrt{\frac{|A_1|}{N}}\right) \approx (2t+1)\sqrt{\frac{|A_1|}{N}} \approx \frac{\pi}{2}\\ t\approx \frac{\pi}{4} \sqrt{\frac{N}{|A_1|}}-\frac{1}{2}$$

Tutaj $A_1$ to liczba rozwiązań lub stanów docelowych. Na nowoczesnych, zaszumionych komputerach kwantowych eksperymentalnie optymalna liczba iteracji może być inna — ale tutaj obliczamy i stosujemy tę teoretyczną, optymalną liczbę, przyjmując $A_1=1$.

optimal_num_iterations = math.floor(
    math.pi / (4 * math.asin(math.sqrt(len(marked_states) / 2**grover_op.num_qubits)))
)
print(optimal_num_iterations)

3

Zbudujmy teraz Circuit zawierający początkowe bramki Hadamarda, które tworzą superpozycję wszystkich możliwych stanów, i zastosujmy operator Grovera optymalną liczbę razy.

qc = QuantumCircuit(grover_op.num_qubits)
# Create even superposition of all basis states
qc.h(range(grover_op.num_qubits))
# Apply Grover operator the optimal number of times
qc.compose(grover_op.power(optimal_num_iterations), inplace=True)
# Measure all qubits
qc.measure_all()
qc.draw(output="mpl", style="iqp")

Nasz Circuit Grovera został zbudowany!

Krok 2: Optymalizacja problemu pod kątem wykonania na sprzęcie kwantowym

Zdefiniowaliśmy nasz abstrakcyjny Circuit kwantowy, ale musimy go przepisać w kategoriach bramek natywnych dla komputera kwantowego, którego faktycznie chcemy użyć. Musimy też wskazać, które Qubity na komputerze kwantowym powinny zostać użyte. Z tych i innych powodów musimy teraz dokonać transpilacji naszego Circuitu. Najpierw określmy komputer kwantowy, którego chcemy użyć.

Poniżej znajduje się kod do jednorazowego zapisania danych uwierzytelniających. Pamiętaj, aby usunąć te informacje z notatnika po ich zapisaniu w środowisku, tak aby dane uwierzytelniające nie zostały przypadkowo udostępnione razem z notatnikiem. Więcej wskazówek znajdziesz w Skonfiguruj swoje konto IBM Cloud oraz Zainicjuj usługę w niezaufanym środowisku.

# To run on hardware, select the backend with the fewest number of jobs in the queue
from qiskit_ibm_runtime import QiskitRuntimeService

# 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()

backend = service.least_busy(operational=True, simulator=False)
backend.name

qiskit_runtime_service._resolve_cloud_instances:WARNING:2025-08-08 14:14:19,931: Default instance not set. Searching all available instances.

'ibm_brisbane'

Teraz używamy wstępnie skonfigurowanego menedżera przebiegów (pass manager), aby zoptymalizować nasz Circuit kwantowy dla wybranego Backend.

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

circuit_isa = pm.run(qc)
# The transpiled circuit will be very large. Only draw it if you are really curious.
# circuit_isa.draw(output="mpl", idle_wires=False, style="iqp")

Warto zauważyć, że głębokość przetranspilowanego Circuitu kwantowego jest znaczna.

print("The total depth is ", circuit_isa.depth())
print(
    "The depth of two-qubit gates is ",
    circuit_isa.depth(lambda instruction: instruction.operation.num_qubits == 2),
)

The total depth is  439
The depth of two-qubit gates is  113

To naprawdę dość duże liczby, nawet w tym prostym przypadku. Ponieważ wszystkie bramki kwantowe (a zwłaszcza bramki dwuQubitowe) są podatne na błędy i szumy, seria ponad 100 bramek dwuQubitowych dałaby w wyniku jedynie szum, gdyby Qubity nie były wyjątkowo wysokiej jakości. Zobaczmy, jak sobie poradzą.

Wykonanie przy użyciu prymitywów Qiskit

Chcemy wykonać wiele pomiarów i sprawdzić, który stan jest najbardziej prawdopodobny. Takie wzmacnianie amplitudy jest problemem próbkowania, odpowiednim do wykonania przy użyciu prymitywu Qiskit Runtime Sampler.

Zauważ, że metoda run() Qiskit Runtime SamplerV2 przyjmuje iterowalną kolekcję prymitywnych zunifikowanych bloków (PUBs). Dla Samplera każdy PUB to iterowalny element w formacie (circuit, parameter_values). Jednak co najmniej wymaga listy Circuit(ów) kwantowych.

# To run on a real quantum computer (this was tested on a Heron r2 processor and used 4 sec. of QPU time)

from qiskit_ibm_runtime import SamplerV2 as Sampler

sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_isa]).result()
dist = result[0].data.meas.get_counts()

Aby jak najlepiej wykorzystać to doświadczenie, gorąco zachęcamy do uruchamiania eksperymentów na prawdziwych komputerach kwantowych dostępnych w IBM Quantum. Jeśli jednak wyczerpałeś swój czas QPU, możesz odkomentować poniższe linie i ukończyć tę aktywność przy użyciu symulatora.

# To run on local simulator:
# from qiskit.primitives import StatevectorSampler as Sampler
# sampler = Sampler()
# result = sampler.run([qc]).result()
# dist = result[0].data.meas.get_counts()

Krok 4: Przetwarzanie końcowe i zwrócenie wyniku w pożądanym formacie klasycznym

Teraz możemy przedstawić wyniki próbkowania w postaci histogramu.

plot_distribution(dist)

Widzimy, że algorytm Grovera zwrócił pożądany stan z najwyższym prawdopodobieństwem — przynajmniej o rząd wielkości wyższym niż pozostałe opcje. W następnej aktywności użyjemy algorytmu w sposób bardziej spójny z dwustronnym przepływem pracy algorytmu zapytaniowego.

Sprawdź swoje zrozumienie

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

Właśnie szukaliśmy jednego rozwiązania w zbiorze $2^4=16$ możliwych stanów. Ustaliliśmy, że optymalna liczba powtórzeń operatora Grovera wynosi $t=3$. Czy ta optymalna liczba wzrosłaby, czy zmalała, gdybyśmy szukali (a) któregokolwiek z kilku rozwiązań, lub (b) jednego rozwiązania w przestrzeni większej liczby możliwych stanów?

Odpowiedź:

Przypomnij sobie, że dopóki liczba rozwiązań jest mała w porównaniu z całą przestrzenią rozwiązań, możemy rozwinąć funkcję sinus dla małych kątów i skorzystać z

$$(2t+1)\theta = (2t+1) \sin^{-1}{\sqrt{\frac{|\mathcal{A}_1|}{N}}}\approx (2t+1) \sqrt{\frac{|\mathcal{A}_1|}{N}} \approx \pi/2\\ t \approx \frac{\pi}{4}\sqrt{\frac{N}{|\mathcal{A}_1|}}-\frac{1}{2}$$

(a) Z powyższego wyrażenia widzimy, że zwiększenie liczby stanów będących rozwiązaniami zmniejszyłoby liczbę iteracji. Zakładając, że ułamek $\frac{|\mathcal{A}_1|}{N}$ jest nadal mały, możemy opisać, jak $t$ maleje: $t~\frac{1}{\sqrt{|\mathcal{A}_1|}}.$

(b) Wraz ze wzrostem przestrzeni możliwych rozwiązań ($N$) wymagana liczba iteracji rośnie, ale jedynie jak $t~\sqrt{N}$.

Załóżmy, że możemy dowolnie wydłużać docelowy ciąg bitowy i nadal uzyskiwać wynik, w którym amplituda prawdopodobieństwa stanu docelowego jest co najmniej o rząd wielkości większa niż każdego innego stanu. Czy oznacza to, że moglibyśmy używać algorytmu Grovera do niezawodnego znajdowania stanu docelowego?

Odpowiedź:

Nie. Załóżmy, że powtórzymy pierwszą aktywność z 20 Qubitami i uruchomimy Circuit kwantowy pewną liczbę razy num_shots = 10,000. Równomierny rozkład prawdopodobieństwa oznaczałby, że każdy stan ma prawdopodobieństwo $10\,000/2^{20}=0{,}00954$ zmierzenia choćby raz. Gdyby prawdopodobieństwo zmierzenia stanu docelowego było 10 razy większe niż dla nie-rozwiązań (a prawdopodobieństwo każdego nie-rozwiązania odpowiednio nieznacznie zmalało), szansa na zmierzenie stanu docelowego choćby raz wynosiłaby tylko około 10%. Wielokrotne zmierzenie stanu docelowego byłoby wysoce nieprawdopodobne, co czyniłoby go nieodróżnialnym od wielu losowo uzyskanych stanów nie-rozwiązań. Dobra wiadomość jest taka, że możemy uzyskać wyniki o wyższej wierności, stosując tłumienie i mitygację błędów.

Aktywność 2: Dokładny przepływ pracy algorytmu zapytaniowego

Zaczniemy tę aktywność dokładnie tak jak pierwszą, z tą różnicą, że teraz dobierzesz się w parę z innym entuzjastą Qiskit. Wybierzesz tajny ciąg bitowy, a twój partner wybierze (zazwyczaj) inny ciąg. Każde z was wygeneruje Circuit kwantowy działający jako wyrocznia i wymienicie się nimi. Następnie użyjesz algorytmu Grovera z tą wyrocznią, aby określić tajny ciąg bitowy swojego partnera.

Krok 1: Odwzoruj klasyczne dane wejściowe na problem kwantowy

Korzystając z funkcji grover_oracle zdefiniowanej powyżej, skonstruuj obwód wyroczni dla jednego lub więcej oznaczonych stanów. Pamiętaj, żeby powiedzieć partnerowi, ile stanów oznaczyłeś(-aś), aby mógł zastosować operator Grovera optymalną liczbę razy. Nie twórz zbyt długiego ciągu bitów. 3–5 bitów powinno działać bez większych trudności. Dłuższe ciągi bitów prowadzą do głębokich obwodów, które wymagają bardziej zaawansowanych technik, takich jak mitygacja błędów.

# Modify the marked states to mark those you wish to target.
marked_states = ["1000"]
oracle = grover_oracle(marked_states)

Właśnie stworzyłeś(-aś) obwód kwantowy, który odwraca fazę twojego docelowego stanu. Możesz zapisać ten obwód jako my_circuit.qpy, korzystając z poniższej składni.

from qiskit import qpy

# Save to a QPY file at a location where you can easily find it.
# You might want to specify a global address.
with open("C:\\Users\\...put your own address here...\\my_circuit.qpy", "wb") as f:
    qpy.dump(oracle, f)

Teraz wyślij ten plik partnerowi (e-mailem, przez komunikator, wspólne repozytorium itp.). Poproś partnera, żeby przesłał ci swój obwód. Upewnij się, że zapiszesz plik w miejscu, które łatwo znajdziesz. Gdy już masz obwód partnera, możesz go zwizualizować – ale to zepsuje model zapytań. Modelujemy bowiem sytuację, w której można odpytywać wyrocznię (używać obwodu wyroczni), ale nie przeglądać jej, żeby ustalić, jaki stan jest celem.

from qiskit import qpy

# Load the circuit from your partner's qpy file from the folder where you saved it.
with open("C:\\Users\\...file location here...\\my_circuit.qpy", "rb") as f:
    circuits = qpy.load(f)

# qpy.load always returns a list of circuits
oracle_partner = circuits[0]

# You could visualize the circuit, but this would break the model of a query algorithm.
# oracle_partner.draw("mpl")

Zapytaj partnera, ile stanów docelowych zakodował, i wprowadź tę liczbę poniżej.

# Update according to your partner's number of target states.
num_marked_states = 1

Wartość ta jest używana w kolejnym wyrażeniu do wyznaczenia optymalnej liczby iteracji Grovera.

grover_op = grover_operator(oracle_partner)
optimal_num_iterations = math.floor(
    math.pi / (4 * math.asin(math.sqrt(num_marked_states / 2**grover_op.num_qubits)))
)
qc = QuantumCircuit(grover_op.num_qubits)
qc.h(range(grover_op.num_qubits))
qc.compose(grover_op.power(optimal_num_iterations), inplace=True)
qc.measure_all()

Krok 2: Zoptymalizuj problem pod kątem wykonania na sprzęcie kwantowym

Postępuj dokładnie tak samo jak poprzednio.

# To run on hardware, select the backend with the fewest number of jobs in the queue
service = QiskitRuntimeService()
backend = service.least_busy(operational=True, simulator=False)
backend.name

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)
circuit_partner_isa = pm.run(qc)

Krok 3: Wykonaj przy użyciu prymitywów Qiskit

Ten krok jest identyczny jak w pierwszym ćwiczeniu.

# To run on a real quantum computer (this was tested on a Heron r2 processor and used 4 seconds of QPU time)

from qiskit_ibm_runtime import SamplerV2 as Sampler

sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_partner_isa]).result()
dist = result[0].data.meas.get_counts()

Krok 4: Przetwórz wyniki i zwróć je w żądanym formacie klasycznym

Wyświetl teraz histogram wyników próbkowania. Jeden lub więcej stanów powinno mieć znacznie wyższe prawdopodobieństwo pomiaru niż pozostałe. Przekaż te wyniki partnerowi i sprawdź, czy poprawnie wyznaczyłeś(-aś) stany docelowe. Domyślnie wyświetlany histogram pochodzi z tego samego obwodu co w pierwszym ćwiczeniu. Wyniki dla obwodu partnera powinny być inne.

plot_distribution(dist)

Sprawdź swoje zrozumienie

Przeczytaj poniższe pytania lub polecenia, przemyśl odpowiedź lub omów proces z partnerem. Kliknij trójkąt, aby zobaczyć podpowiedzi lub sugestie.

Powinieneś(-naś) był(a) poprawnie wyznaczyć stan(y) docelowe partnera. Jeśli ci się to nie udało, porozmawiaj z partnerem, żeby ustalić, co poszło nie tak. Kliknij poniżej, żeby zobaczyć kilka wskazówek.

Wskazówki:

• Zwizualizuj/narysuj obwód partnera i upewnij się, że wczytał się poprawnie.
• Porównaj użyte obwody i zestawij oczekiwany wynik z uzyskanym.
• Sprawdź głębokość użytych obwodów, żeby upewnić się, że ciąg bitów nie był zbyt długi, a liczba iteracji Grovera – nie za wysoka.

Jeśli jeszcze tego nie zrobiłeś(-aś), narysuj obwód wyroczni przesłany przez partnera. Spróbuj omówić wpływ każdej bramki i uzasadnić, jaki musiał być stan docelowy. Będzie to znacznie łatwiejsze w przypadku jednego oznaczonego stanu niż wielu.

Wskazówki:

• Przypomnij sobie, że zadaniem wyroczni jest odwrócenie znaku stanu docelowego.
• Przypomnij sobie, że MCMTGate odwraca znak stanu wtedy i tylko wtedy, gdy wszystkie Qubit zaangażowane w sterowanie znajdują się w stanie $|1\rangle$.
• Jeśli twój stan docelowy ma już $|1\rangle$ na danym Qubit, nie musisz nic z nim robić. Jeśli docelowy stan ma $|0\rangle$ na danym Qubit, a chcesz, żeby MCMTGate odwróciło znak, musisz zastosować bramkę X do tego Qubit w wyroczni (a następnie cofnąć bramkę X po MCMTGate).

Powtórz eksperyment z o jedną iterację mniejszą liczbą zastosowań operatora Grovera. Czy nadal uzyskujesz poprawną odpowiedź? Dlaczego tak lub dlaczego nie?

Wskazówki:

Prawdopodobnie tak, choć może to zależeć od liczby zakodowanych rozwiązań. To pokazuje pewną subtelność: „optymalna" liczba iteracji Grovera to ta, która maksymalizuje prawdopodobieństwo pomiaru oznaczonego stanu. Jednak mniejsza liczba iteracji może nadal sprawić, że oznaczony stan będzie istotnie bardziej prawdopodobny niż pozostałe. Dlatego być może możesz sobie pozwolić na mniejszą liczbę iteracji niż optymalna. Zmniejsza to głębokość obwodu, a tym samym – współczynnik błędów.

Dlaczego ktoś mógłby chcieć zastosować mniejszą liczbę iteracji Grovera niż „optymalna liczba" wyznaczona tutaj?

Odpowiedź:

„Optymalna" liczba iteracji Grovera to ta, która maksymalizuje prawdopodobieństwo pomiaru oznaczonego stanu przy braku szumu. Jednak mniejsza liczba iteracji może nadal sprawić, że oznaczony stan będzie istotnie bardziej prawdopodobny niż pozostałe. Dlatego możesz sobie pozwolić na mniejszą liczbę iteracji niż optymalna. Zmniejsza to głębokość obwodu, a tym samym – współczynnik błędów.

Aktywność 3: Kryterium inne niż konkretny ciąg bitów

Jako ostatnią ilustrację tego, jak algorytm Grovera może być przydatny w roli podprogramu, wyobraźmy sobie, że potrzebujemy stanów kwantowych zawierających określoną liczbę jedynek 1 w reprezentacji bitowej. Jest to powszechne w sytuacjach, gdy obowiązują prawa zachowania. Na przykład w kontekście chemii kwantowej często odwzorowuje się stan 1 Qubitu na obsadzenie orbitalu elektronowego. Aby ładunek był zachowany, całkowita liczba jedynek 1 musi pozostać stała. Ograniczenia tego rodzaju są tak powszechne, że mają specjalną nazwę: ograniczenia wagi Hamminga, a liczba jedynek 1 w stanie nosi nazwę wagi Hamminga.

Krok 1:

Najpierw napiszmy funkcję, która oznacza stany o pożądanej wadze Hamminga. Zapiszemy ją ogólnie dla nieokreślonej liczby Qubitów num_qubits i docelowej wagi Hamminga target_weight.

from qiskit import QuantumCircuit

def grover_oracle_hamming_weight(num_qubits, target_weight):
    """
    Build a Grover oracle that marks all states with Hamming weight == target_weight.

    Parameters:
        num_qubits (int): Number of qubits in the circuit.
        target_weight (int): The Hamming weight to mark.

    Returns:
        QuantumCircuit: Quantum circuit representing Grover oracle.
    """
    qc = QuantumCircuit(num_qubits)
    marked_count = 0
    marked_list = []
    for x in range(2**num_qubits):
        bitstr = format(x, f"0{num_qubits}b")
        if bitstr.count("1") == target_weight:
            # Count the number of target states
            marked_count = marked_count + 1
            marked_list.append(bitstr)
            # Reverse for Qiskit bit order (qubit 0 is rightmost)
            rev_target = bitstr[::-1]
            zero_inds = [i for i, b in enumerate(rev_target) if b == "0"]
            # Apply X gates to 'open' controls (where bit is 0)
            qc.x(zero_inds)
            # Multi-controlled Z (as MCX conjugated by H)
            if num_qubits == 1:
                qc.z(0)
            else:
                qc.h(num_qubits - 1)
                qc.mcx(list(range(num_qubits - 1)), num_qubits - 1)
                qc.h(num_qubits - 1)
            # Undo X gates
            qc.x(zero_inds)
    return qc, marked_count, marked_list

# Completing step 1
oracle, num_marked_states, marked_states = grover_oracle_hamming_weight(3, 2)
print(marked_states)
oracle.draw(output="mpl", style="iqp")

['011', '101', '110']

Od tego miejsca cały proces jest identyczny jak w poprzednich dwóch aktywnościach. Dla zwięzłości kroki wzorca Qiskit są pokazane wyłącznie w komentarzach do kodu.

from qiskit_ibm_runtime import SamplerV2 as Sampler

# Completing step 1
oracle, num_marked_states, marked_states = grover_oracle_hamming_weight(4, 2)
oracle.draw(output="mpl", style="iqp")

grover_op = grover_operator(oracle)
grover_op.decompose().draw(output="mpl", style="iqp")
optimal_num_iterations = math.floor(
    math.pi / (4 * math.asin(math.sqrt(len(marked_states) / 2**grover_op.num_qubits)))
)

qc = QuantumCircuit(grover_op.num_qubits)
qc.h(range(grover_op.num_qubits))
qc.compose(grover_op.power(optimal_num_iterations), inplace=True)
qc.measure_all()
qc.draw(output="mpl", style="iqp")

# Step 2: Optimize for running on real quantum computers

service = QiskitRuntimeService()
backend = service.least_busy(operational=True, simulator=False)
print(backend.name)

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)
circuit_isa = pm.run(qc)

# Step 3: Execute using Qiskit primitives
# To run on a real quantum computer (this was tested on a Heron r2 processor and used 4 seconds of QPU time)

sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_isa]).result()
dist = result[0].data.meas.get_counts()

# To run on local simulator:
# from qiskit.primitives import StatevectorSampler as Sampler
# sampler = Sampler()
# result = sampler.run([qc]).result()
# dist = result[0].data.meas.get_counts()

qiskit_runtime_service._resolve_cloud_instances:WARNING:2025-08-08 14:14:51,686: Default instance not set. Searching all available instances.

ibm_brisbane

print("The total depth is ", circuit_isa.depth())
print(
    "The depth of two-qubit gates is ",
    circuit_isa.depth(lambda instruction: instruction.operation.num_qubits == 2),
)

The total depth is  502
The depth of two-qubit gates is  130

num_marked_states

6

plot_distribution(dist)

Algorytm Grovera rzeczywiście sprawił, że stany o wadze Hamminga równej 2 są o wiele bardziej prawdopodobne do zmierzenia niż jakiekolwiek inne stany — mniej więcej o rząd wielkości.

Kluczowe pojęcia:

W tym module poznaliśmy kilka ważnych cech algorytmu Grovera:

• Podczas gdy klasyczne algorytmy przeszukiwania nieustrukturyzowanego wymagają liczby zapytań rosnącej liniowo wraz z rozmiarem przestrzeni $N$, algorytm Grovera wymaga liczby zapytań rosnącej jak $\sqrt{N}$.
• Algorytm Grovera polega na wielokrotnym stosowaniu ciągu operacji (powszechnie nazywanego „operatorem Grovera") liczbę razy $t$, wybraną tak, aby prawdopodobieństwo zmierzenia stanów docelowych było jak największe.
• Algorytm Grovera można uruchomić przy mniejszej liczbie iteracji niż $t$ i nadal amplifikować stany docelowe.
• Algorytm Grovera wpisuje się w model obliczeniowy oparty na zapytaniach i ma największy sens, gdy jedna osoba kontroluje wyszukiwanie, a inna kontroluje/tworzy wyrocznię. Może być również przydatny jako podprogram w innych obliczeniach kwantowych.

Pytania

Pytania Prawda/Fałsz:

1. P/F Algorytm Grovera zapewnia wykładniczą poprawę w stosunku do algorytmów klasycznych pod względem liczby zapytań potrzebnych do znalezienia pojedynczego oznaczonego stanu w przeszukiwaniu nieustrukturyzowanym.

2. P/F Algorytm Grovera działa poprzez iteracyjne zwiększanie prawdopodobieństwa zmierzenia stanu będącego rozwiązaniem.

3. P/F Im więcej razy wykonasz iterację operatora Grovera, tym wyższe jest prawdopodobieństwo zmierzenia stanu będącego rozwiązaniem.

Pytania wielokrotnego wyboru:

1. Wybierz najlepszą opcję, aby dokończyć zdanie. Najlepsza strategia skutecznego użycia algorytmu Grovera na nowoczesnych komputerach kwantowych to iterowanie operatora Grovera...

• a. Tylko raz.
• b. Zawsze $t$ razy, aby zmaksymalizować amplitudę prawdopodobieństwa stanu(-ów) będącego(-ych) rozwiązaniem.
• c. Do $t$ razy, choć mniejsza liczba może wystarczyć, aby stany będące rozwiązaniami się wyróżniały.
• d. Nie mniej niż 10 razy.

2. Poniżej pokazano układ zapytania fazowego, który pełni rolę wyroczni oznaczającej pewien stan odwróceniem fazy. Który z poniższych stanów jest oznaczany przez ten Circuit?

• a. $|0000\rangle$
• b. $|0101\rangle$
• c. $|0110\rangle$
• d. $|1001\rangle$
• e. $|1010\rangle$
• f. $|1111\rangle$

3. Załóżmy, że chcesz wyszukać trzy oznaczone stany ze zbioru 128. Jaka jest optymalna liczba iteracji operatora Grovera, aby zmaksymalizować amplitudy oznaczonych stanów?

• a. 1
• b. 3
• c. 5
• d. 6
• e. 20
• f. 33

Pytania do dyskusji:

1. Jakie inne warunki możesz zastosować w wyroczni kwantowej? Rozważ warunki, które są łatwe do sformułowania lub narzucenia na ciąg bitów, ale nie polegają jedynie na wypisaniu oznaczonych ciągów bitów.

2. Czy dostrzegasz jakieś problemy ze skalowaniem algorytmu Grovera na nowoczesnych komputerach kwantowych?