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 obvodu. 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 jednoqubitovou 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ý obvod pro operaci $U$. Popis tohoto obvodu můžeme použít k vytvoření obvodu pro řízenou-$U$ operaci, kterou si můžeš představit podle tohoto obrázku (s operací $U$ zobrazenou jako kvantové hradlo vlevo a řízenou-$U$ operací vpravo).

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

Nyní se podívej na následující obvod, 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 obvod závisí na vlastním čísle $U$ odpovídajícím vlastnímu vektoru $\vert\psi\rangle$. Pojďme si obvod podrobně zanalyzovat a zjistit přesně jak.

Počáteční stav obvodu je

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

a první Hadamardovo hradlo 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 hradlem -- ale myšlenka je podobná.

Nakonec se provede druhé Hadamardovo hradlo. 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 obvodu bez chyby zjistit, která z hodnot je správná.

Intuitivně si můžeš výsledek měření obvodu 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 dvě Hadamardova hradla:

• První Hadamardovo hradlo 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é Hadamardovo hradlo nám umožňuje zjistit něco o čísle $\theta$ prostřednictvím jevu interference. Před druhým Hadamardovým hradlem 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 hradla však způsobíme, že číslo $\theta$ ovlivní výstupní pravděpodobnosti.

Zdvojení fáze

Výše uvedený obvod 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 obvodu dvěma kopiemi této operace, jako v tomto obvodu:

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 obvodu, 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 qubity

Místo toho, abychom uvažovali dvě výše popsané možnosti samostatně, spojme je do jediného Circuit takto.

Hadamardovy Gate za řízenými operacemi byly odstraněny a zatím zde nejsou žádná měření. Do Circuit přidáme víc, jakmile budeme uvažovat naše možnosti pro to, co nejvíc se dozvědět o $\theta$.

Pokud spustíme tento Circuit, když $\vert\psi\rangle$ je vlastní vektor $U$, stav spodních Qubit zůstane po celou dobu Circuit $\vert\psi\rangle$, a fáze budou "nakopnuty" (kicked) do stavu horních dvou Qubit. Pojďme Circuit pečlivě analyzovat 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ž je provedena první řízená operace-$U$, vlastní číslo $\lambda = e^{2\pi i\theta}$ se nakopne do fáze, když $a_0$ (horní Qubit) se rovná $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á-$U$ Gate dělají něco podobného, kromě toho, že se to týká $a_1$ místo $a_0$, a $\theta$ je nahrazeno $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 uvažujeme binární řetězec $a_1 a_0$ jako reprezentaci celého čísla $x \in \{0,1,2,3\}$ v binárním zápisu, což je $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ískat z tohoto stavu co nejvíc informací o $\theta$.

V tomto bodě uvažme speciální případ, kdy je nám slíbeno, ž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 pomocí dvou bitů 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 přijít na to, jak nejúčinněji získat informace o $\theta$ obecně.

Nejprve definujeme dvouqubitový vektor stavu 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 kteroukoli dvojici z nich a spočítáme jejich vnitřní 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 dokonale rozlišit — což znamená, že pokud nám je dán jeden z nich, ale nevíme který, dokážeme bezchybně zjistit, o který jde.

Abychom takovou diskriminaci provedli pomocí kvantového obvodu, 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}$$

Abychom zapsali $V$ jako matici $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 už setkali: je to matice spojená se $4$-rozměrnou diskrétní Fourierovou transformací. Vzhledem k této skutečnosti ji nazvěme $\mathrm{QFT}_4$ místo $V$. Název $\mathrm{QFT}$ je zkratka pro quantum Fourier transform — což je v podstatě jen diskrétní Fourierova transformace, chápaná jako unitární operace. O kvantové Fourierově transformaci budeme brzy hovořit podrobněji a obecněji.

$$\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 inverzi této operace, abychom šli opačným směrem, tedy transformovat 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 pak měřením zjistit, jaká hodnota $y\in\{0,1,2,3\}$ popisuje $\theta$ jako $\theta = y/4$. Zde je diagram kvantového Circuit, který to dělá.

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

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

Toto je jasné zlepšení oproti jednoqubitové variantě popsané dříve v lekci. Není dokonalé — může nám dát nesprávnou odpověď — ale odpověď je silně vychýlena směrem k hodnotám $y$, pro které je $y/4$ blízko $\theta$. Konkrétně nejpravděpodobnější výsledek vždy odpovídá nejbližší hodnotě $y/4$ k $\theta$ (rovnajíc $\theta = 0$ a $\theta = 1$ jako předtím), a z grafu vypadá, že tato nejbližší hodnota pro $x$ se vždy objevuje 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$, obě 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 obvodu.

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 obvodu 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á hradla

Pro implementaci kvantové Fourierovy transformace pomocí kvantového obvodu budeme potřebovat řízená fázová hradla. 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 hradla 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 hradla 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 hradla v diagramech kvantových obvodů 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 hradel 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á hradla $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$. Tato řízená fázová hradla vzájemně komutují a mohou být provedeny v libovolném pořadí.

Implementace QFT pomocí obvodu

Nyní se podíváme, jak můžeme implementovat kvantovou Fourierovu transformaci pomocí obvodu, 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 obvodu, je přímočaré implementovat její inverzi: můžeme nahradit každé hradlo jeho inverzí (nebo ekvivalentně hermitovským sdružením) a aplikovat hradla v opačném pořadí. Každý kvantový obvod složený pouze z unitárních hradel 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$ qubitech, čí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ď Hadamardovo hradlo 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 obvod, 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ý obvod 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 obvodu.

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

Označme $s_m$ počet hradel, 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}$ hradel pro kvantovou Fourierovu transformaci na $m-1$ qubitech, plus $m-1$ řízených fázových hradel, plus jedno Hadamardovo hradlo, plus $m-1$ swapových hradel, 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 hradel, kolik metoda popisuje. Pokud hradla trochu přeuspořádáme, můžeme všechna swapová hradla přesunout doprava a snížit počet potřebných swapových hradel 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í hradel z naší standardní sady, musíme každé z řízených fázových hradel buď sestavit, nebo aproximovat hradly 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 hradel 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 hradel 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.)