Groverův algoritmus

Pro tento modul Qiskit in Classrooms musí mít studenti funkční prostředí Python s následujícími nainstalovanými balíčky:

• qiskit v2.1.0 nebo novější
• qiskit-ibm-runtime v0.40.1 nebo novější
• qiskit-aer v0.17.0 nebo novější
• qiskit.visualization
• numpy
• pylatexenc

Pokyny k nastavení a instalaci výše uvedených balíčků najdeš v průvodci Instalace Qiskit. Aby bylo možné spouštět úlohy na skutečných kvantových počítačích, budou studenti muset si zřídit účet u IBM Quantum® podle kroků v průvodci Nastavení účtu IBM Cloud.

Tento modul byl otestován a využil 12 sekund QPU času. Jedná se o odhad v dobré víře; skutečná spotřeba se může lišit.

# 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'

Úvod

Groverův algoritmus je základní kvantový algoritmus, který řeší problém nestrukturovaného vyhledávání: máš-li množinu $N$ položek a způsob, jak ověřit, zda je daná položka ta, kterou hledáš, jak rychle lze hledanou položku najít? V klasickém výpočetnictví, pokud data nejsou seřazena a nelze využít žádnou strukturu, je nejlepším přístupem kontrolovat každou položku jednu po druhé, což vede ke složitosti dotazů $O(N)$ — v průměru bude nutné zkontrolovat přibližně polovinu položek, než najdeš cíl.

Groverův algoritmus, který představil Lov Grover v roce 1996, ukazuje, jak může kvantový počítač tento problém vyřešit mnohem efektivněji — k nalezení označené položky s vysokou pravděpodobností potřebuje pouze $O(\sqrt{N})$ kroků. To představuje kvadratické zrychlení oproti klasickým metodám, což je pro velké datové sady významné.

Algoritmus funguje v následujícím kontextu:

• Zadání problému: Máš funkci $f(x)$, která vrátí 1, pokud je $x$ hledaná položka, a 0 jinak. Tato funkce se často nazývá orákulum nebo černá skříňka, protože o datech se lze dozvědět jen jejich dotazováním přes $f(x)$.
• Přínos kvantového výpočtu: Zatímco klasické algoritmy pro tento problém vyžadují v průměru $N/2$ dotazů, Groverův algoritmus dokáže najít řešení přibližně v $\pi\sqrt{N}/4$ dotazech, což je pro velké $N$ výrazně rychlejší.
• Jak to funguje (na vysoké úrovni):
  • Kvantový počítač nejprve vytvoří superpozici všech možných stavů, čímž najednou reprezentuje všechny možné položky.
  • Poté opakovaně aplikuje sekvenci kvantových operací (Groverova iterace), která zesiluje pravděpodobnost správné odpovědi a potlačuje ostatní.
  • Po dostatečném počtu iterací měření kvantového stavu s vysokou pravděpodobností vrátí správnou odpověď.

Níže je velmi základní diagram Groverova algoritmu, který přeskakuje mnoho nuancí. Podrobnější diagram najdeš v tomto článku.

Několik poznámek k Groverovu algoritmu:

• Je optimální pro nestrukturované vyhledávání: žádný kvantový algoritmus nemůže tento problém vyřešit s méně než $O(\sqrt{N})$ dotazy.
• Poskytuje pouze kvadratické, nikoli exponenciální zrychlení — na rozdíl od některých jiných kvantových algoritmů (například Shorova algoritmu pro faktorizaci).
• Má praktické důsledky, například potenciální urychlení útoků hrubou silou na kryptografické systémy, ačkoli toto zrychlení samo o sobě nestačí k prolomení většiny moderního šifrování.

Pro vysokoškolské studenty obeznámené se základními koncepty výpočetní techniky a modely dotazů nabízí Groverův algoritmus názornou ukázku toho, jak může kvantové výpočetnictví překonat klasické přístupy u určitých problémů, i když jde „jen" o kvadratické zlepšení. Slouží také jako brána k pochopení pokročilejších kvantových algoritmů a širšího potenciálu kvantového výpočetnictví.

Amplitudová amplifikace je obecný kvantový algoritmus neboli podprogram, který lze použít k dosažení kvadratického zrychlení oproti několika klasickým algoritmům. Groverův algoritmus byl prvním, který toto zrychlení demonstroval na problémech nestrukturovaného vyhledávání. Formulace Groverova vyhledávacího problému vyžaduje orákulovou funkci, která označí jeden nebo více výpočetních bázových stavů jako stavy, které chceme najít, a amplifikační Circuit, který zvyšuje amplitudu označených stavů a tím potlačuje zbývající stavy.

Zde ukážeme, jak sestavit Groverova orákula a použít GroverOperator z knihovny Qiskit circuit library k snadnému nastavení instance Groverova vyhledávání. Primitiv Sampler za běhu umožňuje bezproblémové spouštění Groverových Circuitů.

Matematika

Předpokládejme, že existuje funkce $f$, která zobrazuje binární řetězce na jednu binární proměnnou, tedy

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

Jeden příklad definovaný na $\Sigma^6$ je

$$f(x)= \begin{cases} 1 \qquad \text{if }x=\{010101\}\\ 0 \qquad \text{otherwise } \end{cases}$$

Další příklad definovaný na $\Sigma^{2n}$ je

$$f(x)= \begin{cases} 1 \qquad \text{if equal numbers of 1's and 0's in string}\\ 0 \qquad \text{otherwise } \end{cases}$$

Tvým úkolem je najít kvantové stavy odpovídající těm argumentům $x$ funkce $f(x)$, které jsou zobrazeny na 1. Jinými slovy, najdi všechna $\{x_1\}\in \Sigma^n$ taková, že $f(x_1)=1$ (nebo pokud řešení neexistuje, to oznám). Neřešení bychom označili jako $x_0$. Samozřejmě to budeme dělat na kvantovém počítači, pomocí kvantových stavů, takže je užitečné vyjádřit tyto binární řetězce jako stavy:

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

Pomocí kvantové (Diracovy) notace hledáme jeden nebo více speciálních stavů $\{|x_1\rangle\}$ v množině $N=2^n$ možných stavů, kde $n$ je počet Qubitů, přičemž neřešení jsou označena $\{|x_0\rangle\}.$

Funkci $f$ si můžeme představit jako poskytovanou orákulum: černou skříňku, na kterou se lze dotazovat, abychom zjistili její efekt na stav $|x\rangle.$ V praxi funkci často známe, ale může být velmi složitá na implementaci, takže snížení počtu dotazů nebo aplikací $f$ může být důležité. Případně si lze představit paradigma, ve kterém jedna osoba dotazuje orákulum ovládané jinou osobou, takže neznáme orákulovou funkci — známe pouze její působení na konkrétní stavy z dotazování.

Jedná se o „problém nestrukturovaného vyhledávání", protože na $f$ není nic speciálního, co by nám v hledání pomohlo. Výstupy nejsou seřazeny ani není známo, že by se řešení shlukovala, a tak dále. Jako analogii uvažuj staré papírové telefonní seznamy. Toto nestrukturované vyhledávání by bylo jako listování hledáním určitého čísla, nikoli jako hledání v abecedně seřazeném seznamu jmen.

V případě, kdy se hledá jediné řešení, vyžaduje klasický přístup počet dotazů lineárně závislý na $N$. Je jasné, že řešení můžeš najít hned napoprvé, nebo nemusíš najít žádné řešení v prvních $N-1$ pokusech, takže musíš dotázat $N$-tý vstup, abys zjistil, zda vůbec nějaké řešení existuje. Protože funkce nemají žádnou využitelnou strukturu, budeš průměrně potřebovat $N/2$ pokusů. Groverův algoritmus vyžaduje počet dotazů nebo výpočtů $f$ škálující se jako $\sqrt{N}.$

Nástin Circuitů v Groverově algoritmu

Úplný matematický výklad Groverova algoritmu najdeš například v kurzu Základy kvantových algoritmů, který vytvořil John Watrous na IBM Quantum Learning. Stručné zpracování je uvedeno v příloze na konci tohoto modulu. Prozatím si ale jen přiblížíme celkovou strukturu kvantového Circuitu, který implementuje Groverův algoritmus.

Groverův algoritmus lze rozdělit do následujících fází:

• Příprava počáteční superpozice (aplikace Hadamardových Gate na všechny Qubity)
• „Označení" cílového stavu (stavů) překlopením fáze
• Fáze „difúze", ve které jsou Hadamardovy Gate a překlopení fáze aplikovány na všechny Qubity.
• Možná opakování fází označování a difúze pro maximalizaci pravděpodobnosti naměření cílového stavu
• Měření

Označovací Gate $Z_f$ a difúzní vrstvy sestávající z $H,$ $Z_{\text{OR}}$ a $H$ se souhrnně označují jako „Groverův operátor". V tomto diagramu je zobrazeno pouze jedno opakování Groverova operátoru.

Hadamardovy Gate $H$ jsou dobře známé a hojně používané v celém kvantovém výpočetnictví. Hadamardova Gate vytváří superpozice stavů. Konkrétně je definována jako

$$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í působení na jakýkoli jiný stav je definováno prostřednictvím linearity. Zejména vrstva Hadamardových Gate nám umožňuje přejít z počátečního stavu, kdy jsou všechny Qubity v $|0\rangle$ (označeno $|0\rangle^{\otimes n}$), do stavu, kde má každý Qubit určitou pravděpodobnost naměření v $|0\rangle$ nebo $|1\rangle;$ tím lze prohledávat prostor všech možných stavů odlišně než v klasickém výpočetnictví.

Důležitou důsledkovou vlastností Hadamardovy Gate je, že druhá aplikace dokáže takovéto superpozice zrušit:

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

To bude za chvíli důležité.

Ověř si porozumění

Přečti si otázku níže, zamysli se nad odpovědí a poté klikni na trojúhelník pro zobrazení řešení.

Vycházeje z definice Hadamardovy Gate, dokaž, že druhá aplikace Hadamardovy Gate takovéto superpozice skutečně zruší, jak je tvrzeno výše.

Odpověď:

Když aplikujeme X na stav $|+\rangle$, dostaneme hodnotu +1, a na stav $|-\rangle$ dostaneme -1, takže kdybychom měli rozdělení 50-50, získali bychom střední hodnotu 0.

Gate $Z_\text{OR}$ je méně běžná a je definována jako

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

A konečně Gate $Z_f$ je definována jako

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

Všimni si, že efektem je, že $Z_f$ překlopí znaménko cílového stavu, pro který $f(x) = 1$, a ostatní stavy nechá nedotčeny.

Na velmi vysoké, abstraktní úrovni si lze kroky v Circuitu představit následovně:

• První vrstva Hadamard: uvede Qubity do superpozice všech možných stavů.
• $Z_f$: označí cílový stav (stavy) přidáním znaménka „-" před ně. To okamžitě nezmění pravděpodobnosti měření, ale změní chování cílového stavu v následujících krocích.
• Další vrstva Hadamard: znaménko „-" zavedené v předchozím kroku změní relativní znaménko mezi některými členy. Protože Hadamardovy Gate přeměňují jednu směs výpočetních stavů $(|0\rangle+|1\rangle)/\sqrt{2}$ na jeden výpočetní stav $|0\rangle,$ a přeměňují $(|0\rangle-|1\rangle)/\sqrt{2}$ na $|1\rangle,$ tento rozdíl relativního znaménka nyní může začít hrát roli v tom, které stavy jsou naměřeny.
• Aplikuje se jedna závěrečná vrstva Hadamardových Gate a poté jsou provedena měření. V příští části uvidíme podrobněji, jak to funguje.

Příklad

Abychom lépe pochopili, jak Groverův algoritmus funguje, projdeme si malý dvouqubitový příklad. Ti, kdo se nezaměřují na kvantovou mechaniku a Diracovu notaci, tuto část mohou přeskočit. Pro ty, kdo hodlají s kvantovými počítači pracovat do hloubky, ji však vřele doporučujeme.

Níže je schéma kvantového Circuit s popisem kvantových stavů v různých místech průběhu výpočtu. Všimni si, že při dvou Qubitech existují pouze čtyři možné stavy, které lze za jakýchkoli okolností naměřit: $|00\rangle$, $|01\rangle$, $|10\rangle$ a $|11\rangle$.

Předpokládejme, že oracle ($Z_f$, pro nás neznámý) označí stav $|01\rangle$. Projdeme si působení každé skupiny kvantových Gate, včetně oracle, a uvidíme, jaké rozdělení možných stavů se objeví v okamžiku měření.

Na úplném začátku máme

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

Pomocí definice Hadamardových Gate dostaneme

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

Nyní oracle označí cílový stav:

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

Povšimni si, že v tomto stavu mají všechny čtyři možné výsledky stejnou pravděpodobnost naměření. Všechny mají váhu o velikosti $1/2$, což znamená, že každý z nich má $|1/2|^2=1/4$ šanci být naměřen. Přestože je stav $|01\rangle$ označen fází „-", nezpůsobilo to zatím žádné zvýšení pravděpodobnosti jeho naměření. Pokračujeme aplikací další vrstvy Hadamardových Gate.

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

Po sloučení podobných členů dostaneme

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

Nyní $Z_{\text{OR}}$ převrátí znaménko všech stavů kromě $|00\rangle$:

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

A nakonec aplikujeme poslední vrstvu Hadamardových Gate:

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

Doporučujeme si sami projít slučování těchto členů a přesvědčit se, že výsledek je skutečně:

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

Jinými slovy, pravděpodobnost naměření $|01\rangle$ je 100 % (bez šumu a chyb) a pravděpodobnost naměření jakéhokoli jiného stavu je nulová.

Tento dvouqubitový příklad byl obzvláště čistý případ; Groverův algoritmus ne vždy vyjde tak, že cílový stav bude naměřen se 100% pravděpodobností. Spíše amplifikuje pravděpodobnost naměření cílového stavu. Groverův operátor také může být potřeba opakovat více než jednou.

V další části tento algoritmus uvedeme do praxe na skutečných kvantových počítačích IBM®.

Zjevná výhrada

Abychom mohli aplikovat Groverův algoritmus, museli jsme sestavit Groverův operátor, což znamená, že musíme být schopni převrátit fázi stavů splňujících naše kritéria řešení. Tím vyvstává otázka: pokud svou množinu řešení známe tak dobře, že jsme schopni navrhnout kvantový Circuit, který každé řešení označí, co vlastně hledáme?! Odpověď je trojí a budeme se k ní vracet po celém tutoriálu:

(1) Tyto typy dotazovacích algoritmů často zahrnují dvě strany: jednu, která má oracle stanovující kritéria řešení, a druhou, která se snaží řešení uhodnout nebo najít. Fakt, že jedna strana umí oracle sestavit, nepopírá potřebu hledání.

(2) Existují problémy, u nichž je snazší specifikovat kritérium řešení, než řešení samotné najít. Nejznámějším příkladem je pravděpodobně rozklad velkých čísel na prvočinitele. Groverův algoritmus není pro řešení tohoto konkrétního problému obzvláště efektivní; pro prvočíselný rozklad bychom použili Shorův algoritmus. Tento příklad pouze ukazuje, že znát kritérium chování stavu není vždy totéž, co znát stav samotný.

(3) Groverův algoritmus nevrací jen klasická data. Pokud sice po $t$ opakováních Groverova operátoru provedeme měření výsledného stavu, pravděpodobně získáme klasické informace identifikující řešení. Co ale kdybychom klasické informace nechtěli – co kdybychom chtěli stav řešení připravený na kvantovém počítači pro další využití v jiném algoritmu? Groverův algoritmus ve skutečnosti produkuje kvantový stav, v němž jsou řešení silně zvýhodněna. Proto ho lze očekávat jako podrutinu ve složitějších kvantových algoritmech.

S tímto na paměti si projdeme několik příkladů. Začneme příkladem, kde je stav řešení jasně specifikován, abychom mohli sledovat logiku algoritmu, a poté přejdeme k příkladům, v nichž se užitečnost Groverova algoritmu ukáže zřetelněji.

Obecné importy a přístup

Začneme importem několika nezbytných balíčků.

# 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

V tomto i dalších tutoriálech budeme používat framework pro kvantové výpočty označovaný jako „Qiskit patterns", který rozděluje pracovní postupy do těchto kroků:

• Krok 1: Namapuj klasické vstupy na kvantový problém
• Krok 2: Optimalizuj problém pro kvantové spuštění
• Krok 3: Spusť pomocí Qiskit Runtime Primitives
• Krok 4: Postprocessing a klasická analýza

Tyto kroky budeme obecně dodržovat, i když je nemusíme vždy explicitně označovat.

Aktivita 1: Najdi jediný zadaný cílový stav

Krok 1: Mapování klasických vstupů na kvantový problém

Potřebujeme fázovou dotazovací bránu, která přiřadí celkovou fázi (-1) řešením a ostatní stavy ponechá beze změny. Jinak řečeno, Groverův algoritmus vyžaduje orákulum, které určuje jeden nebo více označených stavů výpočetní báze, přičemž „označený" znamená stav s fází -1. K tomu slouží brána controlled-Z nebo její víceřízená zobecnění pro $N$ Qubitů. Podívejme se, jak to funguje, na konkrétním příkladu bitového řetězce {110}. Chceme Circuit, který působí na stav $|\psi\rangle = |q_2,q_1,q_0\rangle$ a aplikuje fázi, pokud $|\psi\rangle = |011\rangle$ (přičemž jsme obrátili pořadí binárního řetězce kvůli notaci v Qiskitu, kde je nejméně významný Qubit, (obvykle 0), umístěn vpravo).

Chceme tedy Circuit $Z_f$, který provede

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

Můžeme použít bránu s více řízeními a více cíli (MCMTGate) a aplikovat bránu Z řízenou všemi Qubity (přepnout fázi, pokud jsou všechny Qubity ve stavu $|1\rangle$). Samozřejmě některé Qubity v požadovaném stavu mohou být $|0\rangle$. Proto musíme pro tyto Qubity nejprve aplikovat bránu X, poté provést víceřízenou bránu Z a nakonec znovu aplikovat bránu X, abychom změnu vrátili. MCMTGate vypadá takto:

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

Všimni si, že do procesu řízení může být zapojeno mnoho Qubitů (zde tři), ale žádný jediný Qubit není označen jako cíl. Je to proto, že celý stav získá celkové znaménko „-" (přepnutí fáze); brána působí na všechny Qubity rovnocenně. To se liší od mnoha jiných vícequbitových bran, jako je brána CX, která má jeden řídicí a jeden cílový Qubit.

V následujícím kódu definujeme fázovou dotazovací bránu (orákulum), která dělá přesně to, co jsme popsali výše: označuje jeden nebo více vstupních stavů báze definovaných prostřednictvím jejich bitového řetězce. K implementaci víceřízené brány Z se používá brána MCMT.

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

Nyní zvolíme konkrétní „označený" stav jako náš cíl a aplikujeme funkci, kterou jsme právě definovali. Pojďme se podívat, jaký Circuit byl vytvořen.

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

Pokud jsou Qubity 1–3 ve stavu $|1\rangle$ a Qubit 0 je původně ve stavu $|0\rangle$, první brána X přepne Qubit 0 na $|1\rangle$ a všechny Qubity budou ve stavu $|1\rangle.$ To znamená, že brána MCMT aplikuje celkovou změnu znaménka neboli přepnutí fáze, jak bylo požadováno. V jakémkoli jiném případě jsou buď Qubity 1–3 ve stavu $|0\rangle$, nebo je Qubit 0 přepnut do stavu $|0\rangle$ a přepnutí fáze nebude aplikováno. Vidíme, že tento Circuit skutečně označuje náš požadovaný stav $|0111\rangle$, tedy bitový řetězec {1110}. Úplný Groverův operátor se skládá z fázové dotazovací brány (orákulum), vrstev Hadamardových bran a operátoru $Z_\text{OR}$. Ke konstrukci z výše definovaného orákula můžeme použít vestavěnou funkci grover_operator.

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

Jak jsme uvedli výše, může být nutné Groverův operátor aplikovat vícekrát. Optimální počet iterací $t$ pro maximalizaci amplitudy cílového stavu v nepřítomnosti šumu lze získat z tohoto výrazu:

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

Zde $A_1$ je počet řešení neboli cílových stavů. Na moderních zašuměných kvantových počítačích může být experimentálně optimální počet iterací jiný – zde však počítáme a používáme tento teoretický optimální počet s $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

Nyní sestavíme Circuit, který zahrnuje počáteční Hadamardovy brány pro vytvoření superpozice všech možných stavů, a aplikujeme Groverův operátor optimální počet opakování.

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")

Náš Groverův Circuit je hotový!

Krok 2: Optimalizace problému pro spuštění na kvantovém hardwaru

Definovali jsme náš abstraktní kvantový Circuit, ale musíme ho přepsat pomocí bran, které jsou nativní pro kvantový počítač, který chceme skutečně použít. Také musíme určit, které Qubity na kvantovém počítači mají být použity. Z těchto a dalších důvodů musíme náš Circuit nyní transpilovat. Nejprve určíme kvantový počítač, který chceme použít.

Níže je kód pro uložení přihlašovacích údajů při prvním použití. Po uložení do svého prostředí nezapomeň tyto informace z notebooku smazat, aby ses vyhnul(a) náhodnému sdílení přihlašovacích údajů spolu s notebookem. Další pokyny najdeš v Nastavení účtu IBM Cloud a Inicializace služby v nedůvěryhodném prostředí.

# 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'

Nyní použijeme přednastavený správce průchodů k optimalizaci našeho kvantového Circuitu pro vybraný 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")

Stojí za zmínku, že hloubka transpilovaného kvantového Circuitu je značná.

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 jsou ve skutečnosti poměrně velká čísla, a to i pro tento jednoduchý případ. Protože všechny kvantové brány (a zejména dvoQubitové brány) podléhají chybám a šumu, série více než 100 dvoQubitových bran by bez extrémně výkonných Qubitů vedla pouze k šumu. Podívejme se, jak si vedou.

Spuštění pomocí primitiv Qiskit

Chceme provést mnoho měření a zjistit, který stav je nejpravděpodobnější. Taková amplitudová amplifikace je vzorkovací problém vhodný pro spuštění s primitivem Qiskit Runtime Sampler.

Všimni si, že metoda run() Qiskit Runtime SamplerV2 přijímá iterovatelnou sadu primitivních unifikovaných bloků (PUBs). Pro Sampler je každý PUB iterovatelný objekt ve formátu (circuit, parameter_values). Minimálně však přijímá seznam kvantových Circuitů.

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

Abys z tohoto zážitku vytěžil(a) maximum, důrazně doporučujeme spouštět experimenty na skutečných kvantových počítačích dostupných přes IBM Quantum. Pokud ti však došel čas na QPU, můžeš odkomentovat níže uvedené řádky a dokončit tuto aktivitu pomocí simulátoru.

# 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: Následné zpracování a vrácení výsledku v požadovaném klasickém formátu

Teď můžeme zobrazit výsledky našeho vzorkování v histogramu.

plot_distribution(dist)

Vidíme, že Groverův algoritmus vrátil požadovaný stav se zdaleka nejvyšší pravděpodobností – alespoň o řád vyšší než ostatní možnosti. V další aktivitě použijeme algoritmus způsobem, který lépe odpovídá dvoustranné pracovní metodice dotazovacího algoritmu.

Otestuj své znalosti

Přečti si otázky níže, zamysli se nad odpovědí a pak klikni na trojúhelník pro zobrazení řešení.

Právě jsme hledali jedno řešení v množině $2^4=16$ možných stavů. Určili jsme optimální počet opakování Groverova operátoru jako $t=3$. Byl by tento optimální počet vyšší nebo nižší, kdybychom hledali (a) libovolné z několika řešení, nebo (b) jedno řešení v prostoru s větším počtem možných stavů?

Odpověď:

Připomeňme, že pokud je počet řešení malý ve srovnání s celým prostorem řešení, můžeme rozvinout funkci sinus kolem malých úhlů a použít

$$(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 výše uvedeného výrazu vidíme, že zvýšení počtu stavů řešení by snížilo počet iterací. Za předpokladu, že zlomek $\frac{|\mathcal{A}_1|}{N}$ je stále malý, můžeme popsat, jak by se $t$ snížilo: $t~\frac{1}{\sqrt{|\mathcal{A}_1|}}.$

(b) S tím, jak roste prostor možných řešení ($N$), roste i počet požadovaných iterací, ale jen jako $t~\sqrt{N}$.

Předpokládejme, že bychom mohli libovolně prodlužovat cílový bitový řetězec a přitom stále dosáhli toho, že amplituda pravděpodobnosti cílového stavu je alespoň o řád vyšší než u jakéhokoli jiného stavu. Znamená to, že bychom mohli spolehlivě najít cílový stav pomocí Groverova algoritmu?

Odpověď:

Ne. Předpokládejme, že bychom první aktivitu opakovali s 20 Qubity a spustili kvantový Circuit num_shots = 10 000 krát. Rovnoměrné rozdělení pravděpodobnosti by znamenalo, že každý stav má pravděpodobnost $10{,}000/2^{20}=0{,}00954$, že bude naměřen byť jen jednou. Pokud by pravděpodobnost naměření cílového stavu byla 10krát vyšší než u nestavu řešení (a pravděpodobnost každého ne-řešení by byla odpovídajícím způsobem mírně snížena), existovala by pouze přibližně 10% šance, že cílový stav naměříme vůbec jednou. Bylo by velmi nepravděpodobné, že bychom cílový stav naměřili vícekrát, což by ho učinilo nerozeznatelným od mnoha náhodně získaných stavů ne-řešení. Dobrou zprávou je, že výsledky s vyšší věrností můžeme získat pomocí potlačení a zmírňování chyb.

Aktivita 2: Přesný pracovní postup dotazovacího algoritmu

Tuto aktivitu zahájíme přesně jako první, s tím rozdílem, že teď se spárujete s jiným nadšencem do Qisku. Vyber si tajný bitový řetězec a tvůj partner si vybere (obecně) jiný. Každý z vás vygeneruje kvantový Circuit fungující jako orákulum a navzájem si je vyměníte. Poté použiješ Groverův algoritmus s tímto orákulem, abys určil partnerův tajný bitový řetězec.

Krok 1: Mapování klasických vstupů na kvantový problém

Pomocí funkce grover_oracle definované výše sestav orákulový Circuit pro jeden nebo více označených stavů. Ujisti se, že sdělíš partnerovi, kolik stavů jsi označil, aby mohl Groverův operátor aplikovat optimální počet opakování. Nepoužívej příliš dlouhý bitový řetězec. 3–5 bitů by mělo fungovat bez větších potíží. Delší bitové řetězce by vedly k hlubokým Circuitům, jež vyžadují pokročilejší techniky, jako je zmírňování chyb.

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

Nyní jsi vytvořil kvantový Circuit, který přehodí fázi tvého cílového stavu. Tento Circuit můžeš uložit jako my_circuit.qpy pomocí níže uvedené syntaxe.

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)

Teď tento soubor pošli partnerovi (e-mailem, přes komunikační aplikaci, sdílené úložiště apod.). Nech partnera, ať ti pošle jeho Circuit také. Ujisti se, že soubor uložíš na místo, kde ho snadno najdeš. Jakmile budeš mít partnerův Circuit, mohl bys ho vizualizovat – to by ale porušilo model dotazovacího algoritmu. Modelujeme totiž situaci, v níž můžeš orákulum dotazovat (použít orákulový Circuit), ale nemůžeš ho zkoumat, abys zjistil, jaký stav cílí.

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")

Zeptej se partnera, kolik cílových stavů zakódoval, a zadej to níže.

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

Toto se použije v dalším výrazu k určení optimálního počtu Groverových iterací.

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: Optimalizace problému pro spuštění na kvantovém hardwaru

Postup je přesně stejný jako dříve.

# 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: Spuštění pomocí primitiv Qisku

Tento krok je také totožný s postupem v první aktivitě.

# 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: Následné zpracování a vrácení výsledku v požadovaném klasickém formátu

Teď zobraz histogram výsledků vzorkování. Jeden nebo více stavů by měl mít výrazně vyšší pravděpodobnost měření než ostatní. Tyto výsledky sdělte partnerovi a ověřte, zda jsi správně určil cílové stavy. Ve výchozím nastavení se zobrazuje histogram stejného Circuitu jako v první aktivitě. Od partnerova Circuitu by ses měl odlišnými výsledky.

plot_distribution(dist)

Ověř si porozumění

Přečti si níže uvedené otázky nebo výzvy, zamysli se nad odpovědí nebo proberte postup se svým partnerem. Klikni na trojúhelník pro nápovědu nebo návrhy.

Měl(a) jsi správně získat cílový stav (nebo stavy) svého partnera. Pokud se ti to nepodařilo, spolupracuj se svým partnerem na tom, co se pokazilo. Kliknutím níže získáš několik nápadů.

Nápovědy:

• Vizualizuj nebo nakresli Circuit svého partnera a ujisti se, že se správně načetl.
• Porovnejte použité Circuits a srovnejte očekávaný výsledek s tím, který jsi získal(a).
• Zkontroluj hloubku použitých Circuits, aby bitový řetězec nebyl příliš dlouhý nebo počet Groverových iterací nepřijatelně vysoký.

Pokud jsi to ještě neudělal(a), nakresli oracle Circuit, který ti partner poslal. Zkus probrat vliv každého Gate a argumentovat, jaký musel být cílový stav. To bude mnohem snazší v případě jediného označeného stavu než pro více stavů.

Nápovědy:

• Vzpomeň si, že úkolem oracle je překlopit znaménko u cílového stavu.
• Vzpomeň si, že MCMTGate překlopí znaménko stavu tehdy a jen tehdy, když jsou všechny Qubity zapojené do řízení ve stavu $|1\rangle$.
• Pokud bude mít tvůj cílový stav na konkrétním Qubitu již $|1\rangle$, není třeba s tímto Qubitem nic dělat. Pokud má tvůj cíl na konkrétním Qubitu $|0\rangle$ a chceš, aby MCMTGate překlopil znaménko, musíš na tento Qubit ve svém oracle aplikovat Gate X (a poté Gate X po MCMTGate vrátit zpět).

Zopakuj experiment s o jednu iterací méně Groverova operátoru. Stále získáš správnou odpověď? Proč ano, nebo proč ne?

Pokyny:

Pravděpodobně ano, i když to může záviset na počtu zakódovaných řešení. To poukazuje na jemný detail: „optimální" počet Groverových iterací je takový, který maximalizuje pravděpodobnost naměření označeného stavu. Ale i méně iterací, než je tento počet, může označený stav učinit výrazně pravděpodobnějším než ostatní stavy. Proto se možná obejdeš s méně iteracemi, než je optimální počet. Tím se snižuje hloubka Circuit, a tedy i míra chyb.

Proč by někdo mohl chtít použít méně Groverových iterací, než je zde zjištěný „optimální počet"?

Odpověď:

„Optimální" počet Groverových iterací je takový, který maximalizuje pravděpodobnost naměření označeného stavu při absenci šumu. Ale i méně iterací, než je tento počet, může označený stav učinit výrazně pravděpodobnějším než ostatní stavy. Proto se možná obejdeš s méně iteracemi, než je optimální počet. Tím se snižuje hloubka Circuit, a tedy i míra chyb.

Aktivita 3: Kritérium jiné než konkrétní bitový řetězec

Jako poslední ukázku toho, jak může být Groverův algoritmus užitečný v kontextu podprogramu, si představme, že potřebujeme kvantové stavy s určitým počtem jedniček 1 v jejich bitovém řetězci. To je běžné v situacích, kde platí zachovávací zákony. Například v kontextu kvantové chemie se stav 1 Qubitu často zobrazuje na obsazení elektronového orbitalu. Aby byl zachován náboj, musí zůstat konstantní i celkový počet jedniček 1. Taková omezení jsou natolik běžná, že mají zvláštní název: omezení Hammingovy váhy a počet jedniček 1 ve stavu se nazývá Hammingova váha.

Krok 1:

Nejprve napišme funkci, která označí stavy s požadovanou Hammingovou váhou. Napíšeme ji obecně pro nespecifikovaný počet qubitů num_qubits a cílovou Hammingovu váhu 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']

Odtud je celý postup totožný s předchozími dvěma aktivitami. Pro stručnost jsou kroky Qiskit Patterns ukázány pouze v komentářích kódu.

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)

Groverův algoritmus zde skutečně připravil stavy s Hammingovou váhou 2 tak, aby byla jejich pravděpodobnost naměření výrazně vyšší než u ostatních stavů – přibližně o řád.

Klíčové pojmy:

V tomto modulu jsme se naučili některé klíčové vlastnosti Groverova algoritmu:

• Zatímco klasické algoritmy pro nestrukturované prohledávání vyžadují počet dotazů, který roste lineárně s velikostí prostoru $N,$ Groverův algoritmus vyžaduje počet dotazů, který roste jako $\sqrt{N}.$
• Groverův algoritmus spočívá v opakování série operací (běžně nazývané „Groverův operátor") $t$-krát, přičemž $t$ je zvoleno tak, aby byla pravděpodobnost naměření cílových stavů co nejvyšší.
• Groverův algoritmus lze spustit s menším počtem iterací než $t$ a přesto zesiluje cílové stavy.
• Groverův algoritmus zapadá do dotazovacího modelu výpočtu a dává největší smysl tehdy, když jedna osoba řídí prohledávání a jiná kontroluje/sestavuje oracle. Může být také užitečný jako podprogram v jiných kvantových výpočtech.

Otázky

Otázky pravda/nepravda:

1. P/N: Groverův algoritmus poskytuje exponenciální zlepšení oproti klasickým algoritmům v počtu dotazů potřebných k nalezení jednoho označeného stavu při nestrukturovaném prohledávání.

2. P/N: Groverův algoritmus funguje tak, že postupně zvyšuje pravděpodobnost, že bude naměřen stavový řešení.

3. P/N: Čím víckrát zopakuješ Groverův operátor, tím vyšší je pravděpodobnost naměření řešení.

Otázky s výběrem odpovědi:

1. Vyber nejlepší možnost pro dokončení věty. Nejlepší strategie pro úspěšné použití Groverova algoritmu na moderních kvantových počítačích je iterovat Groverův operátor...

• a. Pouze jednou.
• b. Vždy $t$-krát, abychom maximalizovali amplitudu pravděpodobnosti stavů řešení.
• c. Až $t$-krát, i když méně iterací může stačit k tomu, aby se stavy řešení výrazně odlišily.
• d. Ne méně než 10-krát.

2. Zde je zobrazen fázový dotazovací Circuit, který funguje jako oracle pro označení určitého stavu překlopením fáze. Které z následujících stavů jsou tímto Circuitem označeny?

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

3. Předpokládej, že chceš hledat tři označené stavy v množině 128 stavů. Jaký je optimální počet iterací Groverova operátoru pro maximalizaci amplitud označených stavů?

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

Diskusní otázky:

1. Jaké jiné podmínky bys mohl/a použít v kvantovém oracle? Zamysli se nad podmínkami, které je snadné vyjádřit nebo uplatnit na bitový řetězec, ale nejsou pouhým výpisem označených bitových řetězců.

2. Vidíš nějaké problémy se škálováním Groverova algoritmu na moderních kvantových počítačích?