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í obvod, 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 obvodů.

Teorie

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 obvodů 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 obvodu, 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 hradel na všechny qubity)
• „Označení" cílového stavu (stavů) překlopením fáze
• Fáze „difúze", ve které jsou Hadamardova hradla 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í hradlo $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.

Hadamardova hradla $H$ jsou dobře známá a hojně používaná v celém kvantovém výpočetnictví. Hadamardovo hradlo vytváří superpozice stavů. Konkrétně je definováno 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 hradel 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í Hadamardova hradla 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 Hadamardova hradla, dokaž, že druhá aplikace Hadamardova hradla 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.

Hradlo $Z_\text{OR}$ je méně běžné a je definováno 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ě hradlo $Z_f$ je definováno 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 obvodu 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 Hadamardova hradla 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 hradel 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 obvodu 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 orákulum ($Z_f$, pro nás neznámé) označí stav $|01\rangle$. Projdeme si působení každé skupiny kvantových hradel, včetně orákula, 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 hradel 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í orákulum 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 hradel.

$$\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 hradel:

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

Geometrická interpretace

Dvouqubitový příklad výše ukázal, jak algebra funguje pro malý případ, ale Groverův algoritmus lze pochopit mnohem intuitivněji: jako posloupnost geometrických reflexí ve dvourozměrné rovině. Níže tento obraz popisujeme. Podrobnosti najdeš také v kurzu Johna Watrouse Základy kvantových algoritmů.

Nastavení roviny. Počáteční stav superpozice $|\psi\rangle$ lze rozložit do dvou složek. Správný stav — ten, který hledáme — nazýváme $|A_1\rangle$. Všechny ostatní stavy dohromady nazýváme $|A_0\rangle$. $|A_1\rangle$ a $|A_0\rangle$ jsou vzájemně kolmé, takže je lze zakreslit jako kolmé osy v abstraktním dvourozměrném prostoru. Protože $|\psi\rangle$ je lineární kombinací těchto dvou složek, leží pod malým úhlem $\theta$ od osy $|A_0\rangle$ — blízko $|A_0\rangle$, protože na začátku tvoří správná složka $|A_1\rangle$ jen nepatrný zlomek stavu.

Reflexe. Klíčový matematický fakt, který potřebujeme, je, že operátor ve tvaru

$$2|v\rangle\langle v| - I$$

odráží jakýkoli stav kolem osy dané $|v\rangle.$ Přesvědčíme se o tom ve dvou případech: stav podél $|v\rangle$ zůstane nezměněn a stav kolmý na $|v\rangle$ dostane přehodnocené znaménko. Libovolný jiný stav lze rozložit do těchto dvou složek a operátor na každou z nich působí odpovídajícím způsobem — to je právě reflexe kolem $|v\rangle$.

Ukazuje se, že jak orákulum, tak krok difúze v Groverově algoritmu lze v tomto geometrickém obrazu vyjádřit jako reflexe.

Orákulum jako reflexe. Orákulum překlopí znaménko stavu $|A_1\rangle$ a ostatní stavy ponechá beze změny. To je totéž jako reflexe kolem osy $|A_0\rangle$.

Difúze jako reflexe. Trochu složitější je pochopit, proč je i difúzní operátor reflexí. Difúzní operátor je

$$H^{\otimes n}\, Z_{\text{OR}}\, H^{\otimes n}$$

Samotný $Z_{\text{OR}}$ je reflexí kolem stavu se samými nulami, protože překlopí znaménko každého stavu, který není $|0\rangle^{\otimes n}$. To lze zapsat jako $2|0\rangle\langle 0| - I$. Obklopující Hadamardovy vrstvy efektivně provádějí změnu báze a transformují osu reflexe. Připomeňme, že $H^{\otimes n}$ zobrazí $|0\rangle^{\otimes n}$ na uniformní superpozici $|u\rangle = \frac{1}{\sqrt{N}}\sum_{x}|x\rangle$. Protože Hadamardova hradla jsou svým vlastním inverzem, celý výraz se stane

$$H^{\otimes n}\left(2|0\rangle\langle 0| - I\right)H^{\otimes n} = 2|u\rangle\langle u| - I$$

což je reflexe kolem $|u\rangle$. Protože $|u\rangle$ je velmi blízko $|\psi\rangle$ (oba leží téměř podél $|A_0\rangle$), tato druhá reflexe posune stav o úhel $2\theta$ od výchozí polohy.

Rotace o $2\theta$. Kombinovaný efekt těchto dvou reflexí je rotace o $2\theta$ směrem k $|A_1\rangle$. Každá další iterace Groverova operátoru otočí stav o dalších $2\theta$.

Optimální počet iterací. Naším cílem je otočit stav co nejblíže k $|A_1\rangle$, což znamená celkovou rotaci přibližně o $\pi/2$ radiánů (čtvrtotočení). Pokud každá iterace přispěje $2\theta$, optimální počet iterací $t$ splňuje

$$(2t + 1)\theta \approx \frac{\pi}{2}$$

Pro jediné řešení mezi $N$ stavy je počáteční úhel $\theta \approx \sin^{-1}(1/\sqrt{N}) \approx 1/\sqrt{N}$ (pro velké $N$). Po dosazení

$$t \approx \frac{\pi}{4}\sqrt{N} - \frac{1}{2}$$

Odtud pochází slavné zrychlení $\sqrt{N}$: k dosažení cíle potřebujeme pouze $O(\sqrt{N})$ iterací, místo $O(N)$ kontrol, které by vyžadovalo klasické vyhledávání.

Obecněji, pokud existuje $|A_1|$ stavů řešení z celkového počtu $N$ stavů, je optimální počet iterací

$$t \approx \frac{\pi}{4}\sqrt{\frac{N}{|A_1|}} - \frac{1}{2}$$

Poznámka: pokud provedeme příliš mnoho iterací, otočíme se za $|A_1\rangle$ a pravděpodobnost nalezení cílového stavu začne opět klesat. Nalezení správného počtu iterací je důležité; na zašuměném kvantovém hardwaru se může experimentálně optimální počet od tohoto ideálního vzorce lišit.

Proč je Groverův algoritmus užitečný?

V tuto chvíli si možná říkáš: právě jsme sestavili orákulum, které označí cílový stav — ale k jeho sestavení jsme museli cílový stav znát. Co tedy vlastně hledáme?

To je oprávněná otázka a existuje na ni několik dobrých odpovědí.

• Model dotazování je teoretický nástroj. Model výpočtu pomocí dotazů nebyl nikdy navržen jako přímo praktický. Jeho účelem je poskytnout nám čistý způsob analýzy algoritmické složitosti rozdělením problému na dvě části: orákulum a vše ostatní. Jak náročné je hledání, pokud je ověření zdarma? Jak se počet dotazů škáluje s velikostí vstupu? Tyto otázky jsou užitečné, i když žádný reálný systém přesně takto nefunguje.

• Můžeš to chápat také jako aktivitu dvou stran: jedna osoba zná cílový stav a sestavuje orákulum; úkolem druhé osoby je najít odpověď pomocí orákula jako černé skříňky, bez nahlížení dovnitř. V Aktivitě 2 níže uděláš přesně toto s partnerem.

• Amplitudová amplifikace je obecně použitelný podprogram. Přestože se tato první ukázka může zdát kruhová, základní mechanismus — nazývaný amplitudová amplifikace — se znovu a znovu objevuje v kvantovém výpočetnictví. Tím, co zde skutečně budujeme, je intuice pro nástroj, který se vyskytuje jako podprogram v mnoha složitějších kvantových algoritmech.

• Existují problémy, kde lze orákulum sestavit bez znalosti odpovědi. Klíčový poznatek spočívá v tom, že existuje celá třída problémů, pro které je velmi obtížné najít řešení, ale velmi snadné ověřit, že dané řešení je správné. Faktorizace je jedním příkladem: součin dvou velkých prvočísel je nesmírně obtížné rozložit na činitele, ale jakmile je máš, snadno je vynásobíš a ověříš. (Pro faktorizaci konkrétně máme lepší algoritmus než Groverův — viz Shorův algoritmus — ale toto zdaleka není jediný problém s touto vlastností.) Sudoku, splňování omezujících podmínek a dokonce i klasická hra Minesweeper jsou problémy, které je obtížné vyřešit, ale snadné ověřit.

Proč je to relevantní? Znamená to, že můžeme znát všechny podmínky a požadavky, které musí řešení splňovat, a zakódovat tyto požadavky do kvantového obvodu sloužícího jako orákulum — aniž bychom znali samotné řešení. Groverův algoritmus ho za nás najde.

S těmito myšlenkami v mysli si projdeme několik příkladů. Začneme příkladem, kde je stav řešení jasně specifikován, abychom mohli sledovat logiku algoritmu. Poté přejdeme na aktivitu dvou stran a nakonec na příklad, kde je orákulum sestaveno z omezujících podmínek problému, nikoli ze znalosti odpovědi.

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, QuantumRegister, ClassicalRegister
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 obvod, 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 obvod $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ý obvod 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 obvod 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 popsali v geometrickém obrazu 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 je

$$t\approx \frac{\pi}{4} \sqrt{\frac{N}{|A_1|}}-\frac{1}{2}$$

kde $|A_1|$ je počet stavů řešení a $N=2^n$ je celkový počet 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 obvod, který zahrnuje počáteční Hadamardova hradla 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 obvod je hotový!

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

Definovali jsme náš abstraktní kvantový obvod, 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áš obvod 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 obvodu 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 obvodu 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 dvouqubitová hradla) podléhají chybám a šumu, série více než 100 dvouqubitových hradel by bez extrémně výkonných qubitů vedla pouze k šumu. Podívejme se, jak si vedou.

Krok 3: 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 obvodů.

# 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ý obvod 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 ne-ř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ý obvod 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ý obvod 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 obvodů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ý obvod, který přehodí fázi tvého cílového stavu. Tento obvod 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 obvod také. Ujisti se, že soubor uložíš na místo, kde ho snadno najdeš. Jakmile budeš mít partnerův obvod, 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ý obvod), 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 Qiskit

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 obvodu jako v první aktivitě. Od partnerova obvodu bys měl získat odlišné 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 obvod svého partnera a ujisti se, že se správně načetl.
• Porovnejte použité obvody a srovnejte očekávaný výsledek s tím, který jsi získal(a).
• Zkontroluj hloubku použitých obvodů, 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 orákulový obvod, který ti partner poslal. Zkus probrat vliv každého hradla 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 orákula 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 orákulu aplikovat hradlo X (a poté hradlo 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 obvodu, 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 obvodu, a tedy i míra chyb.

Aktivita 3: Řeš mřížku Minesweeper Groverovým algoritmem

V předchozí části jsme poznamenali, že Groverův algoritmus se stává skutečně užitečným, když lze orákulum sestavit z omezujících podmínek problému, nikoli ze znalosti odpovědi. Minesweeper je skvělý příklad: očíslované buňky nám říkají, kolik min je v sousedství, a tyto podmínky plně určují, kde se miny musí nacházet — ale nalezení konfigurace vyžaduje prohledávání.

Minesweeper byl prokázán jako NP-úplný: je těžké ho vyřešit, ale snadné ověřit. To z něj dělá přirozeného kandidáta pro Groverův algoritmus. Samozřejmě, na zašuměném kvantovém počítači nemůžeme zatím vyřešit celou mřížku 9$\times$9 — obvody by byly příliš hluboké. Místo toho použijeme malou mřížku jako hračkovou ukázku toho, jak by se na větší desce přistupovalo na budoucím stroji odolném proti chybám.

Několik důležitých upozornění. Groverův algoritmus poskytuje pouze kvadratické zrychlení oproti nestrukturovanému klasickému prohledávání. Minesweeper téměř jistě má využitelnou strukturu, které by chytrý klasický algoritmus mohl využít. A pro exponenciálně rostoucí prostor stavů ani zlepšení $\sqrt{N}$ nestačí donekonečna. Ale odkládejme tyto obavy stranou a použijme tento hračkový problém, abychom ukázali, jak se omezující podmínky problému zakódují do kvantového orákula.

Mřížka

Zde je naše malá mřížka Minesweeper:

Každou prázdnou buňku lze reprezentovat binární proměnnou označující, zda obsahuje minu. Označíme je $x_0$, $x_1$ a $x_2$, kde $x_i = 1$ znamená, že buňka obsahuje minu, a $x_i = 0$ znamená, že neobsahuje:

Toto bychom mohli vyřešit v hlavě za půl sekundy, ale používáme tento hračkový problém k ilustraci toho, jak by bylo možné přistoupit k mnohem těžší desce pomocí kvantového počítače.

Zakódování podmínek

Každá očíslovaná buňka klade podmínku na přilehlé prázdné buňky. Tyto podmínky musíme vyjádřit jako booleovské výrazy, které lze zakódovat do kvantového obvodu.

Buňka „1" sousedící s $x_0$ a $x_1$ říká, že přesně jedna z nich obsahuje minu. To je přesně operace exclusive-OR (XOR), $\oplus$, která vrátí true tehdy a jen tehdy, když je přesně jeden z jejích vstupů true:

$$(x_0 \oplus x_1)$$

Podobně nám druhá buňka „1" (sousedící s $x_1$ a $x_2$) dá:

$$(x_1 \oplus x_2)$$

Buňka „2" říká, že dvě ze tří prázdných buněk musí obsahovat miny. Protože XOR je operace parity, $x_0 \oplus x_1 \oplus x_2$ vrátí true tehdy, když je liché číslo proměnných true. Chceme, aby bylo sudé číslo (konkrétně dvě) true, takže negujeme pomocí $\lnot$:

$$\lnot(x_0 \oplus x_1 \oplus x_2)$$

Sám o sobě by byl tento výraz splněn buď nulou, nebo dvěma qubity ve stavu $|1\rangle$, protože jde o výrok o paritě. Ale v kombinaci s ostatními dvěma klauzulemi, z nichž každá vyžaduje alespoň jednu minu, je jediné splňující přiřazení s přesně dvěma minami.

Všechny tři podmínky musí být splněny současně, takže je spojíme symboly AND $\land$:

$$(x_0 \oplus x_1) \;\land\; (x_1 \oplus x_2) \;\land\; \lnot(x_0 \oplus x_1 \oplus x_2)$$

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

Nyní potřebujeme zakódovat tento booleovský výraz do kvantového obvodu, který bude sloužit jako orákulum. Kvantovou verzi XOR lze provést pomocí bran CX (CNOT): aplikace dvou bran CX z datových qubitů na pracovní (ancilla) qubit efektivně vypočítá jejich XOR a uloží výsledek do ancilly.

Zavádíme tři pracovní qubity — jeden pro každou klauzuli. Výsledek každého booleovského výrazu uložíme do odpovídajícího pracovního qubitu, a poté použijeme víceřízené hradlo Z k překlápění fáze trojqubitového stavu, který způsobí, že všechny tři pracovní qubity jsou v $|1\rangle$ (tedy všechny klauzule jsou splněny současně).

V první buňce kódu níže sestavíme „výpočetní" polovinu orákula — část, která vyhodnotí každou klauzuli a zapíše výsledek do pracovních qubitů.

x = QuantumRegister(3, "x")
a = QuantumRegister(3, "a")
qc = QuantumCircuit(x, a)

# Clause 1: x0 XOR x1 -> stored in a[0]
qc.cx(x[0], a[0])
qc.cx(x[1], a[0])

# Clause 2: x1 XOR x2 -> stored in a[1]
qc.cx(x[1], a[1])
qc.cx(x[2], a[1])

# Clause 3: NOT(x0 XOR x1 XOR x2) -> stored in a[2]
qc.cx(x[0], a[2])
qc.cx(x[1], a[2])
qc.cx(x[2], a[2])
qc.x(a[2])  # The NOT

qc.draw("mpl", style="iqp")

V tuto chvíli je výsledek každé klauzule uložen v odpovídajícím pracovním qubitu. Nyní potřebujeme, aby trojqubitový datový stav, který způsobí, že všechny tři pracovní qubity jsou v $|1\rangle$, obdržel znaménko mínus. Dosáhneme toho víceřízeným hradlem Z (implementovaným jako hradlo MCX obalené Hadamardovými hradly na cíli).

Po aplikaci překlopení fáze musíme provést výpočet zpět — vrátit všechny kroky vyhodnocení klauzulí v opačném pořadí — abychom resetovali pracovní qubity zpět na $|0\rangle$. To je nezbytné, aby pracovní qubity byly čisté pro následné iterace Groverova operátoru.

# Multi-controlled Z: flip phase if all workspace qubits are |1>
qc.h(a[2])
qc.mcx([a[0], a[1]], a[2])
qc.h(a[2])

# Uncompute clause 3: NOT(x0 XOR x1 XOR x2)
qc.x(a[2])
qc.cx(x[2], a[2])
qc.cx(x[1], a[2])
qc.cx(x[0], a[2])

# Uncompute clause 2: x1 XOR x2
qc.cx(x[2], a[1])
qc.cx(x[1], a[1])

# Uncompute clause 1: x0 XOR x1
qc.cx(x[1], a[0])
qc.cx(x[0], a[0])

qc.draw("mpl", style="iqp")

Tento obvod je naše orákulum: překlopí fázi stavu datových qubitů, který splňuje všechny tři podmínky Minesweeperu, a pracovní qubity ponechá zpět v $|0\rangle$.

Nyní sestavíme úplný Groverův operátor z tohoto orákula. Všimni si argumentu reflection_qubits: předáváme pouze datové qubity x, protože pracovní qubity nejsou součástí prohledávaného prostoru. Jejich úkol je splněn, jakmile bylo orákulum aplikováno.

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

Při třech datových qubitech a jednom stavu řešení je optimální počet Groverových iterací $t \approx \frac{\pi}{4}\sqrt{8} - \frac{1}{2} \approx 1{,}7$, takže použijeme dvě iterace. Aplikujeme Hadamardova hradla na datové qubity, abychom vytvořili počáteční superpozici, složíme Groverův operátor dvakrát a změříme pouze datové qubity.

x = QuantumRegister(3, "x")
a = QuantumRegister(4, "a")
meas = ClassicalRegister(3, "meas")

qc = QuantumCircuit(x, a, meas)
# Create superposition over the data qubits only
qc.h(x)
# Apply 2 iterations of the Grover operator
qc.compose(grover_op.power(2), inplace=True)
# Measure only the data qubits
qc.measure(x, meas)
qc.decompose().draw(output="mpl", style="iqp")

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

Stejně jako dříve transpilujeme obvod pro cílový backend.

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)

Nyní můžeme zkontrolovat hloubku transpilovaného obvodu. Protože Minesweeper orákulum používá pracovní qubity a více bran CX, bude transpilovaný obvod hlubší než obvody z předchozích aktivit.

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

Krok 3: Spuštění pomocí primitiv Qiskit

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

# 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

plot_distribution(dist)

Stav 101 by měl mít výrazně vyšší pravděpodobnost než jakýkoli jiný, což naznačuje, že miny se nacházejí na $x_0$ a $x_2$. Použili jsme kvantový počítač k vyřešení malé hry Minesweeper!

Samozřejmě, nejlepší klasické algoritmy pro Minesweeper jsou lepší než hrubá síla prohledávání všech možných konfigurací min — využívají strukturu mřížky. Groverův algoritmus by nabízel výhodu pouze na extrémně obtížných deskách navržených tak, aby byly maximálně nejasné, a i pak kvadratické zrychlení znamená, že nemůže dohnat exponenciální růst donekonečna. Ale skutečný závěr je technika: zakódování omezujících podmínek problému do kvantového orákula je mocný vzor, který se rozšiřuje na splňování podmínek, kombinatorickou optimalizaci a mnoho dalších oblastí.

Otázky a klíčové pojmy:

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 orákulum. Může být také užitečný jako podprogram v jiných kvantových výpočtech.
• Orákulum lze sestavit z omezujících podmínek problému, nikoli ze znalosti řešení, jak bylo demonstrováno na příkladu Minesweeperu.

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 stav ř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í obvod, který funguje jako orákulum pro označení určitého stavu překlopením fáze. Které z následujících stavů jsou tímto obvodem 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é další problémy bys mohl/a formulovat jako Groverovo vyhledávání? Přemýšlej o problémech, kde je obtížné najít řešení, ale snadné ho ověřit.

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