Procedura odhadu fáze

Dále si probereme proceduru odhadu fáze, což je kvantový algoritmus pro řešení problému odhadu fáze.

Začneme zahřívacím cvičením s nízkou přesností, které vysvětluje základní intuici za touto metodou. Poté si povíme o kvantové Fourierově transformaci, což je důležitá kvantová operace používaná v proceduře odhadu fáze, a také o její implementaci pomocí kvantového Circuit. Jakmile budeme mít kvantovou Fourierovu transformaci k dispozici, popíšeme proceduru odhadu fáze v plné obecnosti a zanalyzujeme její výkonnost.

Zahřívání: aproximace fází s nízkou přesností

Začneme několika jednoduchými verzemi procedury odhadu fáze, které poskytují řešení problému odhadu fáze s nízkou přesností. To je užitečné pro vysvětlení intuice za obecnou procedurou, kterou uvidíme o něco později v této lekci.

Využití phase kickbacku

Jednoduchý přístup k problému odhadu fáze, který nám umožňuje zjistit něco o hodnotě $\theta$, kterou hledáme, je založen na jevu phase kick-back. Jak uvidíme, jedná se v podstatě o jedno-Qubitovou verzi obecné procedury odhadu fáze, o které budeme hovořit později v této lekci.

Jako součást vstupu do problému odhadu fáze máme unitární kvantový Circuit pro operaci $U.$ Popis tohoto Circuit můžeme použít k vytvoření Circuit pro řízenou-$U$ operaci, kterou si můžeš představit podle tohoto obrázku (s operací $U$ zobrazenou jako kvantový Gate vlevo a řízenou-$U$ operací vpravo).

Kvantový Circuit pro řízenou-$U$ operaci můžeme vytvořit tak, že nejprve přidáme řídicí Qubit do Circuit pro $U$ a poté nahradíme každý Gate v Circuit pro $U$ řízenou verzí tohoto Gate -- takže náš jeden nový řídicí Qubit efektivně řídí každý jednotlivý Gate v Circuit pro $U.$ To vyžaduje, abychom měli řízenou verzi každého Gate v našem Circuit, ale vždy můžeme sestavit Circuit pro tyto řízené operace, pokud nejsou součástí naší sady Gate.

Nyní se podívej na následující Circuit, kde vstupní stav $\vert\psi\rangle$ všech Qubitů kromě horního je kvantový stavový vlastní vektor $U.$

Pravděpodobnosti výsledků měření pro tento Circuit závisí na vlastním čísle $U$ odpovídajícím vlastnímu vektoru $\vert\psi\rangle.$ Pojďme si Circuit podrobně zanalyzovat a zjistit přesně jak.

Počáteční stav Circuit je

$$\vert\pi_0\rangle = \vert\psi\rangle \vert 0\rangle$$

a první Hadamardův Gate transformuje tento stav na

$$\vert\pi_1\rangle = \vert\psi\rangle \vert +\rangle = \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 0\rangle + \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 1\rangle.$$

Dále se provede řízená-$U$ operace, která vede ke stavu

$$\vert\pi_2\rangle = \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 0\rangle + \frac{1}{\sqrt{2}} \bigl(U \vert\psi\rangle\bigr) \vert 1\rangle.$$

S využitím předpokladu, že $\vert\psi\rangle$ je vlastní vektor $U$ s vlastním číslem $\lambda = e^{2\pi i\theta},$ můžeme tento stav alternativně vyjádřit následovně.

$$\vert\pi_2\rangle = \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 0\rangle + \frac{e^{2\pi i \theta}}{\sqrt{2}} \vert\psi\rangle \vert 1\rangle = \vert\psi\rangle \otimes \left( \frac{1}{\sqrt{2}} \vert 0\rangle + \frac{e^{2\pi i \theta}}{\sqrt{2}} \vert 1\rangle\right)$$

Zde pozorujeme jev phase kickback. Tentokrát je to mírně odlišné od Deutschova algoritmu a Deutsch-Jozsova algoritmu, protože nepracujeme s dotazovacím Gate -- ale myšlenka je podobná.

Nakonec se provede druhý Hadamardův Gate. Po troše zjednodušení získáme tento výraz pro daný stav.

$$\vert\pi_3\rangle = \vert\psi\rangle \otimes \left( \frac{1+ e^{2\pi i \theta}}{2} \vert 0\rangle + \frac{1 - e^{2\pi i \theta}}{2} \vert 1\rangle\right)$$

Měření proto dává výsledky $0$ a $1$ s těmito pravděpodobnostmi:

$$\begin{aligned} p_0 &= \left\vert \frac{1+ e^{2\pi i \theta}}{2} \right\vert^2 = \cos^2(\pi\theta)\\[1mm] p_1 &= \left\vert \frac{1- e^{2\pi i \theta}}{2} \right\vert^2 = \sin^2(\pi\theta). \end{aligned}$$

Zde je graf pravděpodobností pro dva možné výsledky, $0$ a $1,$ jako funkcí $\theta.$

Přirozeně, obě pravděpodobnosti se vždy sčítají na $1.$ Všimni si, že když $\theta = 0,$ výsledek měření je vždy $0,$ a když $\theta = 1/2,$ výsledek měření je vždy $1.$ Takže i když nám výsledek měření neprozradí přesnou hodnotu $\theta$, poskytne nám o ní určitou informaci -- a kdybychom měli příslib, že buď $\theta = 0$ nebo $\theta = 1/2,$ mohli bychom z Circuit bez chyby zjistit, která z hodnot je správná.

Intuitivně si můžeš výsledek měření Circuit představit jako odhad $\theta$ s "přesností na jeden bit". Jinými slovy, kdybychom zapsali $\theta$ v binární notaci a zaokrouhlili ho na jeden bit, dostali bychom číslo jako toto:

$$0.a = \begin{cases} 0 & a = 0\\ \frac{1}{2} & a = 1. \end{cases}$$

Výsledek měření lze chápat jako odhad bitu $a.$ Když $\theta$ není ani $0$ ani $1/2,$ existuje nenulová pravděpodobnost, že odhad bude chybný -- ale pravděpodobnost chyby se stává menší a menší, čím blíže se dostáváme k $0$ nebo $1/2.$

Je přirozené ptát se, jakou roli hrají v této proceduře dva Hadamardovy Gate:

• První Hadamardův Gate nastaví řídicí Qubit do uniformní superpozice $\vert 0\rangle$ a $\vert 1\rangle,$ takže když nastane phase kickback, stane se pro stav $\vert 1\rangle$ a ne pro stav $\vert 0\rangle,$ čímž se vytvoří relativní fázový rozdíl, který ovlivní výsledky měření. Kdybychom to neudělali a phase kickback by vytvořil globální fázi, nemělo by to žádný vliv na pravděpodobnosti získání různých výsledků měření.

• Druhý Hadamardův Gate nám umožňuje zjistit něco o čísle $\theta$ prostřednictvím jevu interference. Před druhým Hadamardovým Gate je stav horního Qubitu

  $$\frac{1}{\sqrt{2}} \vert 0\rangle + \frac{e^{2\pi i \theta}}{\sqrt{2}} \vert 1\rangle,$$

  a kdybychom tento stav měřili, získali bychom $0$ a $1$ každý s pravděpodobností $1/2,$ což nám o $\theta$ neřekne nic. Provedením druhého Hadamardova Gate však způsobíme, že číslo $\theta$ ovlivní výstupní pravděpodobnosti.

Zdvojení fáze

Výše uvedený Circuit využívá jev phase kickback k aproximaci $\theta$ s přesností na jeden bit. Přesnost na jeden bit může být v některých situacích vše, co potřebujeme -- ale pro faktorizaci budeme potřebovat mnohem větší přesnost. Přirozenou otázkou je, jak se můžeme o $\theta$ dozvědět více?

Jedna velmi jednoduchá věc, kterou můžeme udělat, je nahradit řízenou-$U$ operaci v našem Circuit dvěma kopiemi této operace, jako v tomto Circuit:

Dvě kopie řízené-$U$ operace jsou ekvivalentní řízené-$U^2$ operaci. Pokud je $\vert\psi\rangle$ vlastní vektor $U$ s vlastním číslem $\lambda = e^{2\pi i \theta},$ pak je tento stav také vlastním vektorem $U^2,$ tentokrát s vlastním číslem $\lambda^2 = e^{2\pi i (2\theta)}.$

Takže pokud spustíme tuto verzi Circuit, efektivně provádíme stejný výpočet jako předtím, s tím rozdílem, že číslo $\theta$ je nahrazeno $2\theta.$ Zde je graf znázorňující výstupní pravděpodobnosti, jak se $\theta$ pohybuje od $0$ do $1.$

Toto nám skutečně může poskytnout další informace o $\theta.$ Pokud je binární reprezentace $\theta$

$$\theta = 0.a_1 a_2 a_3\cdots$$

pak zdvojení $\theta$ efektivně posune binární tečku o jednu pozici doprava:

$$2\theta = a_1. a_2 a_3\cdots$$

A protože ztotožňujeme $\theta = 1$ s $\theta = 0$ při pohybu po jednotkové kružnici, vidíme, že bit $a_1$ nemá žádný vliv na naše pravděpodobnosti, a efektivně získáváme odhad druhého bitu za binární tečkou, pokud zaokrouhlíme $\theta$ na dva bity. Například pokud bychom předem věděli, že $\theta$ je buď $0$, nebo $1/4$, mohli bychom plně důvěřovat výsledku měření, že nám řekne, která z těchto hodnot to je.

Není však hned jasné, jak by se tento odhad měl skloubit s tím, co jsme se naučili z původního (nezdvojeného) obvodu s fázovým zpětným rázem, abychom získali co nejpřesnější informaci o $\theta.$ Tak se vraťme o krok zpět a zamysleme se, jak postupovat.

Odhad fáze se dvěma Qubit

Místo abychom uvažovali dvě výše popsané možnosti odděleně, pojďme je zkombinovat do jednoho Circuit takto.

Hadamardovy Gate po řízených operacích byly odstraněny a zatím zde nejsou žádná měření. K Circuit přidáme další prvky, jak budeme zvažovat naše možnosti, abychom se o $\theta$ dozvěděli co nejvíce.

Pokud tento Circuit spustíme, když $\vert\psi\rangle$ je vlastní vektor $U,$ stav spodních Qubit zůstane po celou dobu obvodu $\vert\psi\rangle$ a fáze budou „nakopnuty" do stavu horních dvou Qubit. Rozeberme si Circuit pečlivě pomocí následujícího obrázku.

Stav $\vert\pi_1\rangle$ můžeme zapsat takto:

$$\vert\pi_1\rangle = \vert \psi\rangle \otimes \frac{1}{2} \sum_{a_0 = 0}^1 \sum_{a_1 = 0}^1 \vert a_1 a_0 \rangle.$$

Když se provede první řízená operace $U$, vlastní hodnota $\lambda = e^{2\pi i\theta}$ se nakopne do fáze, když je $a_0$ (horní Qubit) roven $1,$ ale ne když je $0.$ Výsledný stav tedy můžeme vyjádřit takto:

$$\vert\pi_2\rangle = \vert\psi\rangle \otimes \frac{1}{2} \sum_{a_0=0}^1 \sum_{a_1=0}^1 e^{2 \pi i a_0 \theta} \vert a_1 a_0 \rangle.$$

Druhá a třetí řízená Gate $U$ dělají něco podobného, ale pro $a_1$ místo $a_0,$ a s $\theta$ nahrazeným $2\theta.$ Výsledný stav můžeme vyjádřit takto:

$$\vert\pi_3\rangle = \vert\psi\rangle\otimes\frac{1}{2}\sum_{a_0 = 0}^1 \sum_{a_1 = 0}^1 e^{2\pi i (2 a_1 + a_0)\theta} \vert a_1 a_0 \rangle.$$

Pokud si binární řetězec $a_1 a_0$ představíme jako celé číslo $x \in \{0,1,2,3\}$ v binárním zápisu, tedy $x = 2 a_1 + a_0,$ můžeme tento stav alternativně vyjádřit následovně.

$$\vert\pi_3\rangle = \vert \psi\rangle \otimes \frac{1}{2} \sum_{x = 0}^3 e^{2\pi i x \theta} \vert x \rangle$$

Naším cílem je z tohoto stavu získat co nejvíce informací o $\theta$.

V tomto bodě budeme uvažovat speciální případ, kdy máme slib, že $\theta = \frac{y}{4}$ pro nějaké celé číslo $y\in\{0,1,2,3\}.$ Jinými slovy, máme $\theta\in \{0, 1/4, 1/2, 3/4\},$ takže toto číslo můžeme přesně vyjádřit v binárním zápisu se dvěma bity, jako .$00,$ .$01,$ .$10,$ nebo .$11.$ Obecně $\theta$ nemusí být jednou z těchto čtyř hodnot, ale zamyšlení nad tímto speciálním případem nám pomůže zjistit, jak nejefektivněji extrahovat informace o $\theta$ obecně.

Nejprve definujeme stavový vektor dvou Qubit pro každou možnou hodnotu $y \in \{0, 1, 2, 3\}.$

$$\vert \phi_y\rangle = \frac{1}{2} \sum_{x = 0}^3 e^{2\pi i x (\frac{y}{4})} \vert x \rangle = \frac{1}{2} \sum_{x = 0}^3 e^{2\pi i \frac{x y}{4}} \vert x \rangle$$

Po zjednodušení exponenciál můžeme tyto vektory zapsat následovně.

$$\begin{aligned} \vert\phi_0\rangle & = \frac{1}{2} \vert 0 \rangle + \frac{1}{2} \vert 1 \rangle + \frac{1}{2} \vert 2 \rangle + \frac{1}{2} \vert 3 \rangle \\[3mm] \vert\phi_1\rangle & = \frac{1}{2} \vert 0 \rangle + \frac{i}{2} \vert 1 \rangle - \frac{1}{2} \vert 2 \rangle - \frac{i}{2} \vert 3 \rangle \\[3mm] \vert\phi_2\rangle & = \frac{1}{2} \vert 0 \rangle - \frac{1}{2} \vert 1 \rangle + \frac{1}{2} \vert 2 \rangle - \frac{1}{2} \vert 3 \rangle \\[3mm] \vert\phi_3\rangle & = \frac{1}{2} \vert 0 \rangle - \frac{i}{2} \vert 1 \rangle - \frac{1}{2} \vert 2 \rangle + \frac{i}{2} \vert 3 \rangle \end{aligned}$$

Tyto vektory jsou ortogonální: pokud vybereme libovolnou dvojici z nich a spočítáme jejich skalární součin, dostaneme $0.$ Každý z nich je také jednotkový vektor, takže $\{\vert\phi_0\rangle, \vert\phi_1\rangle, \vert\phi_2\rangle, \vert\phi_3\rangle\}$ je ortonormální báze. Proto hned víme, že existuje měření, které je dokáže perfektně rozlišit — to znamená, že pokud dostaneme jeden z nich, ale nevíme který, můžeme bez chyby zjistit, o který se jedná.

Pro provedení takového rozlišení pomocí kvantového Circuit můžeme nejprve definovat unitární operaci $V$, která transformuje standardní bázové stavy na čtyři výše uvedené stavy.

$$\begin{aligned} V \vert 00 \rangle & = \vert\phi_0\rangle \\ V \vert 01 \rangle & = \vert\phi_1\rangle \\ V \vert 10 \rangle & = \vert\phi_2\rangle \\ V \vert 11 \rangle & = \vert\phi_3\rangle \end{aligned}$$

Pro zapsání $V$ jako matice $4\times 4$ stačí vzít sloupce $V$ jako stavy $\vert\phi_0\rangle,\ldots,\vert\phi_3\rangle.$

$$V = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1\\[1mm] 1 & i & -1 & -i\\[1mm] 1 & -1 & 1 & -1\\[1mm] 1 & -i & -1 & i \end{pmatrix}$$

Toto je speciální matice a je pravděpodobné, že se s ní někteří čtenáři již setkali: je to matice spojená se $4$-dimenzionální diskrétní Fourierovou transformací. S ohledem na tuto skutečnost ji nazvěme $\mathrm{QFT}_4$ místo $V.$ Název $\mathrm{QFT}$ je zkratka pro kvantovou Fourierovu transformaci — což je v podstatě jen diskrétní Fourierova transformace, chápaná jako unitární operace. Kvantovou Fourierovu transformaci probereme podrobněji a obecněji za chvíli.

$$\mathrm{QFT}_4 = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1\\[1mm] 1 & i & -1 & -i\\[1mm] 1 & -1 & 1 & -1\\[1mm] 1 & -i & -1 & i \end{pmatrix}$$

Můžeme provést inverzní operaci, abychom šli opačným směrem — transformovali stavy $\vert\phi_0\rangle,\ldots,\vert\phi_3\rangle$ na standardní bázové stavy $\vert 0\rangle,\ldots,\vert 3\rangle.$ Pokud to uděláme, můžeme měřením zjistit, která hodnota $y\in\{0,1,2,3\}$ popisuje $\theta$ jako $\theta = y/4.$ Zde je diagram kvantového Circuit, který to provádí.

Shrnutí: pokud tento Circuit spustíme, když $\theta = y/4$ pro $y\in\{0,1,2,3\},$ stav bezprostředně před měřením bude $\vert \psi\rangle \vert y\rangle$ (pro $y$ zakódované jako dvoubitový binární řetězec), takže měření odhalí hodnotu $y$ bez chyby.

Tento Circuit je motivován speciálním případem, kdy $\theta \in \{0,1/4,1/2,3/4\}$ — ale můžeme ho spustit pro libovolnou volbu $U$ a $\vert \psi\rangle,$ a tedy pro libovolnou hodnotu $\theta,$ kterou si přejeme. Zde je graf výstupních pravděpodobností, které Circuit produkuje pro libovolné volby $\theta.$

Toto je jasné zlepšení oproti variantě s jedním Qubit popsané dříve v lekci. Není to dokonalé — může nám dát špatnou odpověď — ale odpověď je silně vychýlena směrem k hodnotám $y$, pro které je $y/4$ blízko $\theta.$ Zejména nejpravděpodobnější výsledek vždy odpovídá nejbližší hodnotě $y/4$ k $\theta$ (opět ztotožňujeme $\theta = 0$ a $\theta = 1$), a z grafu to vypadá, že tato nejbližší hodnota pro $x$ se vždy objeví s pravděpodobností těsně nad $40\%.$ Když je $\theta$ přesně uprostřed mezi dvěma takovými hodnotami, jako například $\theta = 0.375$, dvě stejně blízké hodnoty $y$ jsou stejně pravděpodobné.

Příprava na zobecnění na mnoho Qubit

Vzhledem ke zlepšení, které jsme právě získali použitím dvou řídicích Qubit místo jednoho ve spojení s inverzí $4$-dimenzionální kvantové Fourierovy transformace, je přirozené uvažovat o dalším zobecnění — přidáním více řídicích Qubit. Když to uděláme, získáme obecný postup odhadu fáze. Za chvíli uvidíme, jak to funguje, ale abychom to mohli přesně popsat, budeme muset probrat kvantovou Fourierovu transformaci obecněji, abychom viděli, jak je definována pro jiné dimenze a jak ji (nebo její inverzi) můžeme implementovat pomocí kvantového Circuit.

Kvantová Fourierova transformace

Kvantová Fourierova transformace je unitární operace, kterou lze definovat pro libovolnou kladnou celočíselnou dimenzi $N.$ V této sekci uvidíme, jak je tato operace definována a jak ji lze implementovat pomocí kvantového Circuit na $m$ Qubit s náklady $O(m^2)$, když $N = 2^m.$

Matice popisující kvantovou Fourierovu transformaci jsou odvozeny z analogické operace na $N$-dimenzionálních vektorech známé jako diskrétní Fourierova transformace. Tuto operaci si lze představit různými způsoby. Například si diskrétní Fourierovu transformaci můžeme představit v čistě abstraktních, matematických pojmech jako lineární zobrazení. Nebo si o ní můžeme uvažovat ve výpočetních pojmech, kdy dostaneme $N$-dimenzionální vektor komplexních čísel (předpokládejme, že reálné a imaginární části záznamů jsou zakódovány v binárním zápisu) a cílem je vypočítat $N$-dimenzionální vektor získaný aplikací diskrétní Fourierovy transformace. My se zaměříme na třetí způsob, kterým je chápání této transformace jako unitární operace, kterou lze provést na kvantovém systému.

Existuje efektivní algoritmus pro výpočet diskrétní Fourierovy transformace na daném vstupním vektoru známý jako rychlá Fourierova transformace. Má aplikace ve zpracování signálů a mnoha dalších oblastech a mnozí ho považují za jeden z nejdůležitějších algoritmů, jaké byly kdy objeveny. Jak se ukazuje, implementace kvantové Fourierovy transformace pro případ, kdy je $N$ mocninou 2, kterou budeme studovat, je založena na přesně stejné podkladové struktuře, která umožňuje rychlou Fourierovu transformaci.

Definice kvantové Fourierovy transformace

Pro definici kvantové Fourierovy transformace nejprve definujeme komplexní číslo $\omega_N$ pro každé kladné celé číslo $N$ takto:

$$\omega_N = e^{\frac{2\pi i}{N}} = \cos\left(\frac{2\pi}{N}\right) + i \sin\left(\frac{2\pi}{N}\right).$$

Toto je číslo na komplexní jednotkové kružnici, které získáme, pokud začneme v bodě $1$ a posuneme se proti směru hodinových ručiček o úhel $2\pi/N$ radiánů, neboli o zlomek $1/N$ obvodu kružnice. Zde je několik příkladů:

$$\begin{gathered} \omega_1 = 1\\[1mm] \omega_2 = -1\\[1mm] \omega_3 = -\frac{1}{2} + \frac{\sqrt{3}}{2} i\\[2mm] \omega_4 = i\\[1mm] \omega_8 = \frac{1+i}{\sqrt{2}}\\[3mm] \omega_{16} = \frac{\sqrt{2 + \sqrt{2}}}{2} + \frac{\sqrt{2 - \sqrt{2}}}{2} i\\[2mm] \omega_{100} \approx 0.998 + 0.063 i \end{gathered}$$

Nyní můžeme definovat $N$-dimenzionální kvantovou Fourierovu transformaci, která je popsána maticí $N\times N$, jejíž řádky a sloupce jsou přiřazeny ke standardním bázovým stavům $\vert 0\rangle,\ldots,\vert N-1\rangle.$ Pro odhad fáze budeme tuto operaci potřebovat pouze tehdy, když $N = 2^m$ je mocnina $2$, ale operaci lze definovat pro libovolné kladné celé číslo $N.$

$$\mathrm{QFT}_N = \frac{1}{\sqrt{N}} \sum_{x = 0}^{N-1} \sum_{y = 0}^{N-1} \omega_N^{xy} \vert x \rangle\langle y\vert$$

Jak již bylo řečeno, toto je matice spojená s $N$-dimenzionální diskrétní Fourierovou transformací. Často se úvodní faktor $1/\sqrt{N}$ do definice této matice nezahrnuje, ale my ho musíme zahrnout, abychom získali unitární matici.

Zde je kvantová Fourierova transformace zapsaná jako matice pro několik malých hodnot $N.$

$$\mathrm{QFT}_1 = \begin{pmatrix} 1 \end{pmatrix}$$ $$\mathrm{QFT}_2 = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1\\[1mm] 1 & -1 \end{pmatrix}$$ $$\mathrm{QFT}_3 = \frac{1}{\sqrt{3}} \begin{pmatrix} 1 & 1 & 1\\[2mm] 1 & \frac{-1 + i\sqrt{3}}{2} & \frac{-1 - i\sqrt{3}}{2}\\[2mm] 1 & \frac{-1 - i\sqrt{3}}{2} & \frac{-1 + i\sqrt{3}}{2} \end{pmatrix}$$ $$\mathrm{QFT}_4 = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1\\[1mm] 1 & i & -1 & -i\\[1mm] 1 & -1 & 1 & -1\\[1mm] 1 & -i & -1 & i \end{pmatrix}$$ $$\mathrm{QFT}_8 = \frac{1}{2\sqrt{2}} \begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\[2mm] 1 & \frac{1+i}{\sqrt{2}} & i & \frac{-1+i}{\sqrt{2}} & -1 & \frac{-1-i}{\sqrt{2}} & -i & \frac{1-i}{\sqrt{2}}\\[2mm] 1 & i & -1 & -i & 1 & i & -1 & -i\\[2mm] 1 & \frac{-1+i}{\sqrt{2}} & -i & \frac{1+i}{\sqrt{2}} & -1 & \frac{1-i}{\sqrt{2}} & i & \frac{-1-i}{\sqrt{2}}\\[2mm] 1 & -1 & 1 & -1 & 1 & -1 & 1 & -1\\[2mm] 1 & \frac{-1-i}{\sqrt{2}} & i & \frac{1-i}{\sqrt{2}} & -1 & \frac{1+i}{\sqrt{2}} & -i & \frac{-1+i}{\sqrt{2}}\\[2mm] 1 & -i & -1 & i & 1 & -i & -1 & i\\[2mm] 1 & \frac{1-i}{\sqrt{2}} & -i & \frac{-1-i}{\sqrt{2}} & -1 & \frac{-1+i}{\sqrt{2}} & i & \frac{1+i}{\sqrt{2}}\\[2mm] \end{pmatrix}$$

Všimni si zejména, že $\mathrm{QFT}_2$ je jiný název pro Hadamardovu operaci.

Unitarita

Ověřme, že $\mathrm{QFT}_N$ je unitární pro libovolnou volbu $N.$ Jedním ze způsobů, jak to udělat, je ukázat, že jeho sloupce tvoří ortonormální bázi. Můžeme definovat vektor odpovídající sloupci číslo $y,$ počínaje od $y = 0$ až po $y = N-1,$ takto:

$$\vert\phi_y\rangle = \frac{1}{\sqrt{N}} \sum_{x = 0}^{N-1} \omega_N^{xy} \vert x \rangle.$$

Výpočet skalárního součinu mezi libovolnými dvěma z těchto vektorů nám dává tento výraz:

$$\langle \phi_z \vert \phi_y \rangle = \frac{1}{N} \sum_{x = 0}^{N-1} \omega_N^{x (y - z)}$$

Součty tohoto typu můžeme vyhodnotit pomocí následujícího vzorce pro součet prvních $N$ členů geometrické řady.

$$1 + \alpha + \alpha^2 + \cdots + \alpha^{N-1} = \begin{cases} \frac{\alpha^N - 1}{\alpha - 1} & \text{if } \alpha\neq 1\\[2mm] N & \text{if } \alpha=1 \end{cases}$$

Konkrétně tento vzorec můžeme použít, když $\alpha = \omega_N^{y-z}.$ Když $y = z,$ máme $\alpha = 1,$ takže použitím vzorce a vydělením $N$ dostaneme

$$\langle \phi_y \vert \phi_y \rangle = 1.$$

Když $y\neq z,$ máme $\alpha \neq 1,$ takže vzorec ukazuje toto:

$$\langle \phi_z \vert \phi_y \rangle = \frac{1}{N} \frac{\omega_N^{N(y-z)} - 1}{\omega_N^{y-z} - 1} = \frac{1}{N} \frac{1 - 1}{\omega_N^{y-z} - 1} = 0.$$

Toto nastává, protože $\omega_N^N = e^{2\pi i} = 1,$ takže $\omega_N^{N(y-z)} = 1^{y-z} = 1,$ čímž je čitatel nulový, zatímco jmenovatel je nenulový, protože $\omega_N^{y-z} \neq 1.$ Intuitivně řečeno, sčítáme sadu bodů rozmístěných po jednotkové kružnici, a ty se při sečtení vzájemně vyruší a dají $0.$

Tím jsme ukázali, že $\{\vert\phi_0\rangle,\ldots,\vert\phi_{N-1}\rangle\}$ je ortonormální množina,

$$\langle \phi_z \vert \phi_y \rangle = \begin{cases} 1 & y=z\\ 0 & y\neq z, \end{cases}$$

což ukazuje, že $\mathrm{QFT}_N$ je unitární.

Řízené fázové Gate

Pro implementaci kvantové Fourierovy transformace pomocí kvantového Circuit budeme potřebovat řízené fázové Gate. Připomeň si, že fázová operace je jednoqubitová unitární operace tvaru

$$P_{\alpha} = \begin{pmatrix} 1 & 0\\[1mm] 0 & e^{i\alpha} \end{pmatrix}$$

pro libovolné reálné číslo $\alpha.$ Řízená verze tohoto Gate má následující matici:

$$CP_{\alpha} = \begin{pmatrix} 1 & 0 & 0 & 0\\[1mm] 0 & 1 & 0 & 0\\[1mm] 0 & 0 & 1 & 0\\[1mm] 0 & 0 & 0 & e^{i\alpha} \end{pmatrix}$$

U tohoto řízeného Gate ve skutečnosti nezáleží na tom, který Qubit je řídicí a který je cílový, protože obě možnosti jsou ekvivalentní. Pro znázornění tohoto Gate v diagramech kvantových Circuit můžeš použít kterýkoli z následujících symbolů.

U třetí formy se popisek $\alpha$ někdy umisťuje i na stranu řídicí čáry nebo pod dolní řídicí bod, pokud je to výhodné.

Pro provedení kvantové Fourierovy transformace, když $N = 2^m$ a $m\geq 2,$ budeme potřebovat provést operaci na $m$ Qubitech, jejíž akce na stavech standardní báze lze popsat jako

$$\vert y \rangle \vert a \rangle \mapsto \omega_{2^m}^{ay} \vert y \rangle \vert a \rangle,$$

kde $a$ je bit a $y \in \{0,\ldots,2^{m-1} - 1\}$ je číslo zakódované v binárním zápisu jako řetězec $m-1$ bitů. Toto lze provést pomocí řízených fázových Gate zobecněním následujícího příkladu, pro který $m=5.$

Obecně pro libovolnou volbu $m\geq 2$ lze horní Qubit odpovídající bitu $a$ považovat za řídicí, přičemž fázové Gate $P_{\alpha}$ se pohybují od $\alpha = \pi/2^{m-1}$ na Qubitu odpovídajícím nejméně významnému bitu $y$ až po $\alpha = \frac{\pi}{2}$ na Qubitu odpovídajícím nejvíce významnému bitu $y.$ Tyto řízené fázové Gate vzájemně komutují a mohou být provedeny v libovolném pořadí.

Implementace QFT pomocí Circuit

Nyní se podíváme, jak můžeme implementovat kvantovou Fourierovu transformaci pomocí Circuit, když je dimenze $N = 2^m$ mocninou $2.$ Ve skutečnosti existuje více způsobů, jak kvantovou Fourierovu transformaci implementovat, ale toto je pravděpodobně nejjednodušší známá metoda. Jakmile víme, jak kvantovou Fourierovu transformaci implementovat pomocí kvantového Circuit, je přímočaré implementovat její inverzi: můžeme nahradit každý Gate jeho inverzí (nebo ekvivalentně hermitovským sdružením) a aplikovat Gate v opačném pořadí. Každý kvantový Circuit složený pouze z unitárních Gate lze tímto způsobem invertovat.

Implementace je svou povahou rekurzivní, takže je nejpřirozenější ji takto popsat. Základní případ je $m=1,$ v tom případě je kvantová Fourierova transformace Hadamardova operace.

Pro provedení kvantové Fourierovy transformace na $m$ Qubitech, když $m \geq 2,$ můžeme provést následující kroky, jejichž akce popíšeme pro stavy standardní báze tvaru $\vert x \rangle \vert a\rangle,$ kde $x\in\{0,\ldots,2^{m-1} - 1\}$ je celé číslo zakódované jako $m-1$ bitů v binárním zápisu a $a$ je jeden bit.

1. Nejprve aplikuj $2^{m-1}$-rozměrnou kvantovou Fourierovu transformaci na spodních/nejlevějších $m-1$ Qubitů, čímž získáš tento stav:

   $$\Bigl(\mathrm{QFT}_{2^{m-1}} \vert x \rangle\Bigr) \vert a\rangle = \frac{1}{\sqrt{2^{m-1}}} \sum_{y = 0}^{2^{m-1} - 1} \omega_{2^{m-1}}^{xy} \vert y \rangle \vert a \rangle.$$

   Toto se provede rekurzivní aplikací právě popisované metody pro o jeden Qubit méně, přičemž jako základní případ slouží Hadamardova operace na jednom Qubitu.

2. Použij horní/nejpravější Qubit jako řídicí pro vložení fáze $\omega_{2^m}^y$ pro každý stav standardní báze $\vert y\rangle$ zbývajících $m-1$ Qubitů (jak je popsáno výše), čímž získáš tento stav:

   $$\frac{1}{\sqrt{2^{m-1}}} \sum_{y = 0}^{2^{m-1} - 1} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert y \rangle \vert a \rangle.$$

3. Proveď Hadamardův Gate na horním/nejpravějším Qubitu, čímž získáš tento stav:

   $$\frac{1}{\sqrt{2^{m}}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert y \rangle \vert b \rangle.$$

4. Permutuj pořadí Qubitů tak, aby se nejméně významný bit stal nejvíce významným bitem, přičemž všechny ostatní se posunou nahoru/doprava:

   $$\frac{1}{\sqrt{2^{m}}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert b \rangle \vert y \rangle.$$

Například zde je Circuit, který získáme pro $N = 32 = 2^5.$ V tomto diagramu mají Qubity názvy odpovídající stavovým vektorům standardní báze $\vert x\rangle \vert a\rangle$ (pro vstup) a $\vert b\rangle \vert y\rangle$ (pro výstup) pro přehlednost.

Analýza

Klíčový vzorec, který potřebujeme k ověření, že právě popsaný Circuit implementuje $2^m$-rozměrnou kvantovou Fourierovu transformaci, je tento:

$$(-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} = \omega_{2^m}^{(2x+ a)(2^{m-1}b + y)}.$$

Tento vzorec platí pro libovolnou volbu celých čísel $a,$ $b,$ $x$ a $y,$ ale budeme ho potřebovat pouze pro $a,b\in\{0,1\}$ a $x,y\in\{0,\ldots,2^{m-1}-1\}.$ Lze ho ověřit rozepsáním součinu v exponentu na pravé straně,

$$\omega_{2^m}^{(2x+ a)(2^{m-1}b + y)} = \omega_{2^m}^{2^m xb} \omega_{2^m}^{2xy} \omega_{2^m}^{2^{m-1}ab} \omega_{2^m}^{ay} = (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay},$$

kde druhá rovnost využívá pozorování, že

$$\omega_{2^m}^{2^m xb} = \bigl(\omega_{2^m}^{2^m}\bigr)^{xb} = 1^{xb} = 1.$$

$2^m$-dimenzionální kvantová Fourierova transformace je definována následovně pro každé $u\in\{0,\ldots,2^m - 1\}.$

$$\mathrm{QFT}_{2^m} \vert u\rangle = \frac{1}{\sqrt{2^m}} \sum_{v = 0}^{2^m - 1} \omega_{2^m}^{uv} \vert v\rangle$$

Pokud zapíšeme $u$ a $v$ jako

$$\begin{aligned} u & = 2x + a\\ v & = 2^{m-1}b + y \end{aligned}$$

pro $a,b\in\{0,1\}$ a $x,y\in\{0,\ldots,2^{m-1} - 1\},$ dostaneme

$$\begin{aligned} \mathrm{QFT}_{2^m} \vert 2x + a\rangle & = \frac{1}{\sqrt{2^m}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 \omega_{2^m}^{(2x+ a)(2^{m-1}b + y)} \vert b 2^{m-1} + y\rangle\\[2mm] & = \frac{1}{\sqrt{2^m}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert b 2^{m-1} + y\rangle. \end{aligned}$$

Nakonec, když si představíme standardní bázové stavy $\vert x \rangle \vert a\rangle$ a $\vert b \rangle \vert y \rangle$ jako binární kódování celých čísel v rozsahu $\{0,\ldots,2^m-1\},$

$$\begin{aligned} \vert x \rangle \vert a\rangle & = \vert 2x + a \rangle\\ \vert b \rangle \vert y \rangle & = \vert 2^{m-1}b + y\rangle, \end{aligned}$$

vidíme, že výše uvedený obvod implementuje požadovanou operaci. Pokud se ti tato metoda provádění kvantové Fourierovy transformace zdá pozoruhodná, je to proto, že pozoruhodná skutečně je: jde v podstatě o rychlou Fourierovu transformaci ve formě kvantového Circuit.

Nakonec spočítejme, kolik Gate se v právě popsaném obvodu používá. Řízené fázové Gate nejsou ve standardní sadě Gate, kterou jsme probírali v předchozí lekci, ale pro začátek to budeme ignorovat a každou z nich budeme počítat jako jednu Gate.

Označme $s_m$ počet Gate, které potřebujeme pro každou možnou volbu $m.$ Pokud $m=1,$ kvantová Fourierova transformace je jen Hadamardova operace, takže

$$s_1 = 1.$$

Pokud $m\geq 2,$ pak ve výše uvedeném obvodu potřebujeme $s_{m-1}$ Gate pro kvantovou Fourierovu transformaci na $m-1$ Qubitech, plus $m-1$ řízených fázových Gate, plus jednu Hadamardovu Gate, plus $m-1$ swapových Gate, takže

$$s_m = s_{m-1} + (2m - 1).$$

Uzavřený výraz můžeme získat sečtením:

$$s_m = \sum_{k = 1}^m (2k - 1) = m^2.$$

Ve skutečnosti nepotřebujeme tolik swapových Gate, kolik metoda popisuje. Pokud Gate trochu přeuspořádáme, můžeme všechny swapové Gate přesunout doprava a snížit počet potřebných swapových Gate na $\lfloor m/2\rfloor.$ Asymptoticky vzato to není zásadní zlepšení: stále dostáváme obvody o velikosti $O(m^2)$ pro provedení $\mathrm{QFT}_{2^m}.$

Pokud chceme implementovat kvantovou Fourierovu transformaci pouze pomocí Gate z naší standardní sady, musíme každou z řízených fázových Gate buď sestavit, nebo aproximovat Gate z naší sady. Potřebný počet závisí na tom, jakou přesnost požadujeme, ale jako funkce $m$ zůstávají celkové náklady kvadratické.

Ve skutečnosti je možné aproximovat kvantovou Fourierovu transformaci poměrně přesně s podkvadratickým počtem Gate využitím faktu, že $P_{\alpha}$ je velmi blízko identické operaci, když je $\alpha$ velmi malé — což znamená, že můžeme většinu řízených fázových Gate jednoduše vynechat, aniž bychom příliš ztratili na přesnosti.

Obecný postup a analýza

Nyní prozkoumáme postup odhadu fáze obecně. Myšlenka spočívá v rozšíření dvou-qubitové verze odhadu fáze, kterou jsme uvažovali výše, přirozeným způsobem naznačeným následujícím diagramem.

Všimni si, že pro každý nový řídicí Qubit přidaný nahoře zdvojnásobujeme počet provedení unitární operace $U.$ To je v diagramu naznačeno mocninami $U$ u každé z řízených unitárních operací.

Nejpřímočařejší způsob implementace řízené operace $U^k$ pro nějakou volbu $k$ je jednoduše opakovat řízenou operaci $U$ celkem $k$-krát. Pokud se skutečně použije tato metodologie, je třeba si uvědomit, že přidávání řídicích Qubitů významně přispívá k velikosti obvodu: pokud máme $m$ řídicích Qubitů, jak ukazuje diagram, je potřeba celkem $2^m - 1$ kopií řízené operace $U.$ To znamená, že s rostoucím $m$ narůstají významné výpočetní náklady — ale jak uvidíme, vede to také k výrazně přesnější aproximaci $\theta.$

Je důležité poznamenat, že pro některé volby $U$ může být možné vytvořit obvod implementující operaci $U^k$ pro velké hodnoty $k$ efektivnějším způsobem než pouhým opakováním obvodu pro $U$ celkem $k$-krát. Konkrétní příklad uvidíme v kontextu faktorizace celých čísel později v této lekci, kde nám přijde na pomoc efektivní algoritmus pro modulární umocňování probíraný v předchozí lekci.

Nyní analyzujme právě popsaný obvod. Stav bezprostředně před inverzní kvantovou Fourierovou transformací vypadá takto:

$$\frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} \bigl( U^x \vert\psi\rangle \bigr) \vert x\rangle = \vert\psi\rangle \otimes \frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} e^{2\pi i x\theta} \vert x\rangle.$$

Speciální případ

Podobně jako v případě $m=2$ nejprve uvažujme speciální případ, kdy $\theta = y/2^m$ pro $y\in\{0,\ldots,2^m-1\}.$ V tomto případě lze stav před inverzní kvantovou Fourierovou transformací alternativně zapsat takto:

$$\vert\psi\rangle \otimes \frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} e^{2\pi i \frac{xy}{2^m}} \vert x\rangle = \vert\psi\rangle \otimes \frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} \omega_{2^m}^{xy} \vert x\rangle = \vert\psi\rangle \otimes \mathrm{QFT}_{2^m} \vert y\rangle.$$

Takže po aplikaci inverzní kvantové Fourierovy transformace se stav změní na

$$\vert\psi\rangle \vert y\rangle$$

a měření odhalí $y$ (zakódované v binární soustavě).

Ohraničení pravděpodobností

Pro jiné hodnoty $\theta,$ tedy ty, které nemají tvar $y/2^m$ pro celé číslo $y,$ výsledky měření nebudou deterministické, ale můžeme dokázat odhady pravděpodobností pro různé výsledky.Dále uvažujme libovolnou volbu $\theta$ splňující $0\leq \theta < 1.$

Po provedení inverzní kvantové Fourierovy transformace je stav obvodu následující:

$$\vert \psi \rangle \otimes \frac{1}{2^m} \sum_{y=0}^{2^m - 1} \sum_{x=0}^{2^m-1} e^{2\pi i x (\theta - y/2^m)} \vert y\rangle.$$

Takže když se provedou měření na horních $m$ Qubitech, vidíme každý výsledek $y$ s pravděpodobností

$$p_y = \left\vert \frac{1}{2^m} \sum_{x=0}^{2^m - 1} e^{2\pi i x (\theta - y/2^m)} \right\vert^2.$$

Abychom tyto pravděpodobnosti lépe pochopili, využijeme tentýž vzorec, který jsme viděli dříve, pro součet počáteční části geometrické řady.

$$1 + \alpha + \alpha^2 + \cdots + \alpha^{N-1} = \begin{cases} \frac{\alpha^N - 1}{\alpha - 1} & \text{if } \alpha\neq 1\\[2mm] N & \text{if } \alpha=1 \end{cases}$$

Součet vystupující ve vzorci pro $p_y$ můžeme zjednodušit dosazením $\alpha = e^{2\pi i (\theta - y/2^m)}.$ Zde je výsledek.

$$\sum_{x=0}^{2^m - 1} e^{2\pi i x (\theta - y/2^m)} = \begin{cases} 2^m & \theta = y/2^m\\[2mm] \frac{e^{2\pi i (2^m \theta - y)} - 1}{e^{2\pi i (\theta - y/2^m)} - 1} & \theta\neq y/2^m \end{cases}$$

V případě $\theta = y/2^m$ tedy zjistíme, že $p_y = 1$ (jak jsme již věděli z úvahy o tomto speciálním případě), a v případě $\theta \neq y/2^m$ zjistíme, že

$$p_y = \frac{1}{2^{2m}} \left\vert \frac{e^{2\pi i (2^m \theta - y)} - 1}{e^{2\pi i (\theta - y/2^m)} - 1}\right\vert^2.$$

O těchto pravděpodobnostech se můžeme dozvědět více, když se zamyslíme nad vztahem délky oblouku a délky tětivy na jednotkové kružnici. Zde je obrázek ilustrující vztahy, které potřebujeme, pro libovolné reálné číslo $\delta\in \bigl[ -\frac{1}{2},\frac{1}{2}\bigr].$

Zaprvé, délka tětivy (vykreslená modře) nemůže být větší než délka oblouku (vykreslená fialově):

$$\bigl\vert e^{2\pi i \delta} - 1\bigr\vert \leq 2\pi\vert\delta\vert.$$

Při porovnání těchto délek opačným směrem vidíme, že poměr délky oblouku k délce tětivy je největší, když $\delta = \pm 1/2,$ a v tomto případě je poměr roven polovině obvodu kružnice dělené průměrem, což je $\pi/2.$ Máme tedy

$$\frac{2\pi\vert\delta\vert}{\bigl\vert e^{2\pi i \delta} - 1\bigr\vert} \leq \frac{\pi}{2},$$

a proto

$$\bigl\vert e^{2\pi i \delta} - 1\bigr\vert \geq 4\vert\delta\vert.$$

Analýza založená na těchto vztazích odhaluje následující dva fakty.

1. Předpokládejme, že $\theta$ je reálné číslo a $y\in \{0,\ldots,2^m-1\}$ splňuje

   $$\Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert \leq 2^{-(m+1)}.$$

   To znamená, že $y/2^m$ je buď nejlepší $m$-bitová aproximace $\theta,$ nebo leží přesně uprostřed mezi $y/2^m$ a buď $(y-1)/2^m$ nebo $(y+1)/2^m,$ takže jde o jednu ze dvou nejlepších aproximací $\theta.$

   Dokážeme, že $p_y$ musí být v tomto případě poměrně velké. Z předpokladu, který uvažujeme, plyne, že $\vert 2^m \theta - y \vert \leq 1/2,$ takže můžeme využít druhé pozorování výše o vztahu délky oblouku a tětivy k závěru, že

   $$\left\vert e^{2\pi i (2^m \theta - y)} - 1\right\vert \geq 4 \vert 2^m \theta - y \vert = 4 \cdot 2^m \cdot \Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert.$$

   Rovněž můžeme využít první pozorování o délkách oblouku a tětivy k závěru, že

   $$\left\vert e^{2\pi i (\theta - y/2^m)} - 1\right\vert \leq 2\pi \Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert.$$

   Dosazením těchto dvou nerovností do výrazu pro $p_y$ dostaneme

   $$p_y \geq \frac{1}{2^{2m}} \frac{16 \cdot 2^{2m}}{4 \pi^2} = \frac{4}{\pi^2} \approx 0.405.$$

   To vysvětluje naše pozorování, že nejlepší výsledek nastává s pravděpodobností větší než $40\%$ ve verzi odhadu fáze s $m=2,$ kterou jsme probírali dříve. Ve skutečnosti to není přesně 40 %, ale $4/\pi^2,$ a tento odhad platí pro každou volbu $m.$

2. Nyní předpokládejme, že $y\in \{0,\ldots,2^m-1\}$ splňuje

   $$2^{-m} \leq \Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert \leq \frac{1}{2}.$$

   To znamená, že existuje lepší aproximace $z/2^m$ hodnoty $\theta$ ležící mezi $\theta$ a $y/2^m.$

   Tentokrát dokážeme, že $p_y$ nemůže být příliš velké. Můžeme začít jednoduchým pozorováním, že

   $$\left\vert e^{2\pi i (2^m \theta - y)} - 1\right\vert \leq 2,$$

   což plyne z faktu, že libovolné dva body na jednotkové kružnici se mohou v absolutní hodnotě lišit nejvýše o $2.$

   Rovněž můžeme využít druhé pozorování o délkách oblouku a tětivy z výše uvedeného, tentokrát aplikované na jmenovatel $p_y$ místo čitatele, k závěru

   $$\left\vert e^{2\pi i (\theta - y/2^m)} - 1\right\vert \geq 4\Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert \geq 4 \cdot 2^{-m}.$$

   Spojením obou nerovností dostaneme

   $$p_y \leq \frac{1}{2^{2m}} \frac{4}{16 \cdot 2^{-2m}} = \frac{1}{4}.$$

   Všimni si, že i když je tento odhad pro naše účely dostatečný, je poměrně hrubý — pravděpodobnost je obvykle mnohem nižší než $1/4.$

Důležitý závěr z této analýzy je, že velmi blízké aproximace $\theta$ se pravděpodobně vyskytnou — nejlepší $m$-bitovou aproximaci dostaneme s pravděpodobností větší než $40\%$ — zatímco aproximace vzdálené o více než $2^{-m}$ se vyskytnou méně pravděpodobně, s pravděpodobností shora ohraničenou $25\%.$

S ohledem na tyto záruky je možné zvýšit naši jistotu opakováním postupu odhadu fáze několikrát, abychom shromáždili statistické důkazy o $\theta.$ Je důležité si uvědomit, že stav $\vert\psi\rangle$ spodní skupiny Qubitů zůstává postupem odhadu fáze nezměněn, takže jej lze použít k opakovanému spuštění postupu, kolikrát chceme. Konkrétně pokaždé, když spustíme obvod, získáme nejlepší $m$-bitovou aproximaci $\theta$ s pravděpodobností větší než $40\%,$ zatímco pravděpodobnost odchylky větší než $2^{-m}$ je ohraničena $25\%.$ Pokud obvod spustíme několikrát a vezmeme nejčastěji se vyskytující výsledek, je proto mimořádně pravděpodobné, že nejčastěji se vyskytující výsledek nebude ten, který nastává s pravděpodobností nejvýše $25\%.$ V důsledku toho velmi pravděpodobně získáme aproximaci $y/2^m,$ která je vzdálena od hodnoty $\theta$ nejvýše o $1/2^m.$ Nepravděpodobná šance, že se odchýlíme o více než $1/2^m,$ skutečně klesá exponenciálně s počtem opakování postupu.

Zde jsou dva grafy zobrazující pravděpodobnosti pro tři po sobě jdoucí hodnoty $y$ při $m = 3$ a $m=4$ jako funkce $\theta.$ (Pro přehlednost jsou zobrazeny pouze tři výsledky. Pravděpodobnosti pro ostatní výsledky získáš cyklickým posunem téže základní funkce.)