Procedura estymacji fazy

Następnie omówimy procedurę estymacji fazy, która jest algorytmem kwantowym służącym do rozwiązywania problemu estymacji fazy.

Zaczniemy od rozgrzewki o niskiej precyzji, która wyjaśnia podstawową intuicję stojącą za tą metodą. Następnie omówimy kwantową transformatę Fouriera, która jest ważną operacją kwantową wykorzystywaną w procedurze estymacji fazy, a także jej implementację w postaci obwodu kwantowego. Kiedy już będziemy dysponować kwantową transformatą Fouriera, opiszemy procedurę estymacji fazy w pełnej ogólności i przeanalizujemy jej wydajność.

Rozgrzewka: aproksymacja faz z niską precyzją

Zaczniemy od kilku prostych wersji procedury estymacji fazy, które dostarczają rozwiązań problemu estymacji fazy o niskiej precyzji. Pomaga to wyjaśnić intuicję stojącą za ogólną procedurą, którą zobaczymy nieco później w lekcji.

Wykorzystanie phase kickback

Proste podejście do problemu estymacji fazy, które pozwala nam dowiedzieć się czegoś o wartości $\theta,$ której szukamy, opiera się na zjawisku phase kick-back. Jak się przekonamy, jest to w zasadzie jednokubitowa wersja ogólnej procedury estymacji fazy, którą omówimy później w lekcji.

Jako część wejścia do problemu estymacji fazy mamy unitary obwód kwantowy realizujący operację $U$. Możemy użyć opisu tego obwodu, aby stworzyć obwód dla operacji controlled-$U$, co można zilustrować tak, jak sugeruje ten rysunek (z operacją $U$, postrzeganą jako bramka kwantowa, po lewej stronie i operacją controlled-$U$ po prawej).

Możemy stworzyć obwód kwantowy dla operacji controlled-$U$, dodając najpierw kontrolny kubit do obwodu dla $U$, a następnie zastępując każdą bramkę w obwodzie dla $U$ jej kontrolowaną wersją — tak więc nasz jeden nowy kontrolny kubit efektywnie kontroluje każdą pojedynczą bramkę w obwodzie dla $U$. Wymaga to, abyśmy dysponowali kontrolowaną wersją każdej bramki w naszym obwodzie, ale zawsze możemy zbudować obwody dla tych kontrolowanych operacji, jeśli nie są one zawarte w naszym zestawie bramek.

Rozważmy teraz następujący obwód, w którym stan wejściowy $\vert\psi\rangle$ wszystkich kubitów z wyjątkiem górnego jest eigenvectorem w postaci stanu kwantowego operacji $U$.

Prawdopodobieństwa wyników pomiaru dla tego obwodu zależą od eigenvalue operacji $U$ odpowiadającej eigenvectorowi $\vert\psi\rangle$. Przeanalizujmy obwód szczegółowo, aby określić dokładnie, jak.

Początkowy stan obwodu to

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

a pierwsza bramka Hadamard przekształca ten stan w

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

Następnie wykonywana jest operacja controlled-$U$, co prowadzi do stanu

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

Korzystając z założenia, że $\vert\psi\rangle$ jest eigenvectorem operacji $U$ z eigenvalue $\lambda = e^{2\pi i\theta}$, możemy alternatywnie wyrazić ten stan w następujący sposób.

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

Tutaj obserwujemy zjawisko phase kickback. Tym razem jest ono nieco inne niż w algorytmie Deutscha i algorytmie Deutscha-Jozsy, ponieważ nie pracujemy z bramką zapytania — ale idea jest podobna.

Na koniec wykonywana jest druga bramka Hadamard. Po niewielkim uproszczeniu otrzymujemy następujące wyrażenie dla tego stanu.

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

Pomiar daje zatem wyniki $0$ i $1$ z następującymi prawdopodobieństwami:

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

Oto wykres prawdopodobieństw dla dwóch możliwych wyników, $0$ i $1,$ jako funkcji $\theta.$

Oczywiście, obydwa prawdopodobieństwa zawsze sumują się do $1$. Zauważmy, że gdy $\theta = 0$, wynikiem pomiaru jest zawsze $0$, a gdy $\theta = 1/2$, wynikiem pomiaru jest zawsze $1$. Zatem, chociaż wynik pomiaru nie ujawnia dokładnej wartości $\theta$, dostarcza nam pewnych informacji na jej temat — a gdybyśmy mieli zapewnienie, że albo $\theta = 0$, albo $\theta = 1/2$, moglibyśmy dowiedzieć się z obwodu, która z tych wartości jest poprawna, bez popełnienia błędu.

Intuicyjnie możemy myśleć o wyniku pomiaru obwodu jako o zgadywaniu $\theta$ z „dokładnością do jednego bitu". Innymi słowy, gdybyśmy zapisali $\theta$ w notacji binarnej i zaokrąglili do jednego bitu, otrzymalibyśmy liczbę taką jak ta:

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

Wynik pomiaru można postrzegać jako zgadywanie bitu $a$. Gdy $\theta$ nie jest ani $0$, ani $1/2$, istnieje niezerowe prawdopodobieństwo, że zgadywanie będzie błędne — ale prawdopodobieństwo popełnienia błędu staje się coraz mniejsze w miarę zbliżania się do $0$ lub $1/2$.

Naturalne jest pytanie, jaką rolę odgrywają dwie bramki Hadamard w tej procedurze:

• Pierwsza bramka Hadamard ustawia kontrolny kubit w jednorodnej superpozycji stanów $\vert 0\rangle$ i $\vert 1\rangle$, tak że gdy zachodzi phase kickback, dzieje się to dla stanu $\vert 1\rangle$, a nie dla stanu $\vert 0\rangle$, tworząc względną różnicę faz, która wpływa na wyniki pomiaru. Gdybyśmy tego nie zrobili, a phase kickback wytworzyłby fazę globalną, nie miałoby to wpływu na prawdopodobieństwa uzyskania różnych wyników pomiaru.

• Druga bramka Hadamard pozwala nam dowiedzieć się czegoś o liczbie $\theta$ poprzez zjawisko interferencji. Przed drugą bramką Hadamard stan górnego kubitu to

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

  i gdybyśmy zmierzyli ten stan, otrzymalibyśmy $0$ i $1$ każde z prawdopodobieństwem $1/2$, nie mówiąc nam nic o $\theta$. Wykonując drugą bramkę Hadamard, sprawiamy jednak, że liczba $\theta$ wpływa na prawdopodobieństwa wyjściowe.

Podwajanie fazy

Powyższy obwód wykorzystuje zjawisko phase kickback do aproksymacji $\theta$ z dokładnością do pojedynczego bitu. Jeden bit dokładności może być wszystkim, czego potrzebujemy w niektórych sytuacjach — ale do faktoryzacji będziemy potrzebować znacznie większej dokładności. Naturalne pytanie brzmi: jak możemy dowiedzieć się więcej o $\theta?$

Jedną z bardzo prostych rzeczy, które możemy zrobić, jest zastąpienie operacji controlled-$U$ w naszym obwodzie dwoma kopiami tej operacji, jak w tym obwodzie:

Dwie kopie operacji controlled-$U$ są równoważne operacji controlled-$U^2$. Jeśli $\vert\psi\rangle$ jest eigenvectorem operacji $U$ z eigenvalue $\lambda = e^{2\pi i \theta}$, to stan ten jest również eigenvectorem operacji $U^2$, tym razem z eigenvalue $\lambda^2 = e^{2\pi i (2\theta)}$.

Zatem, jeśli uruchomimy tę wersję obwodu, efektywnie wykonujemy te same obliczenia co wcześniej, z tą różnicą, że liczba $\theta$ jest zastąpiona przez $2\theta$. Oto wykres ilustrujący prawdopodobieństwa wyjściowe, gdy $\theta$ zmienia się od $0$ do $1$.

Zrobienie tego może rzeczywiście dostarczyć nam dodatkowych informacji o $\theta$. Jeśli binarna reprezentacja $\theta$ to

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

to podwojenie $\theta$ efektywnie przesuwa punkt binarny o jedno miejsce w prawo:

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

A ponieważ utożsamiamy $\theta = 1$ z $\theta = 0$ podczas poruszania się po okręgu jednostkowym, widzimy, że bit $a_1$ nie ma wpływu na nasze prawdopodobieństwa, i efektywnie otrzymujemy zgadywanie drugiego bitu po punkcie binarnym, jeśli zaokrąglimy $\theta$ do dwóch bitów. Na przykład, gdybyśmy wiedzieli z góry, że $\theta$ wynosi $0$ lub $1/4$, moglibyśmy w pełni zaufać wynikowi pomiaru, aby dowiedzieć się, która to wartość.

Nie jest jednak od razu jasne, jak tę estymację należy pogodzić z tym, czego nauczyliśmy się z oryginalnego (niepodwojonego) obwodu phase kickback, aby uzyskać jak najdokładniejsze informacje o $\theta$. Zróbmy więc krok wstecz i zastanówmy się, jak postępować dalej.

Dwukubitowa estymacja fazy

Zamiast rozważać oddzielnie dwie opcje opisane powyżej, połączmy je w jeden obwód w następujący sposób.

Bramki Hadamarda po operacjach kontrolowanych zostały usunięte i nie ma tu jeszcze żadnych pomiarów. Dodamy więcej elementów do obwodu, gdy będziemy rozważać nasze możliwości dowiedzenia się jak najwięcej o $\theta$.

Jeśli uruchomimy ten obwód, gdy $\vert\psi\rangle$ jest eigenvectorem $U$, stan dolnych kubitów pozostanie $\vert\psi\rangle$ przez cały obwód, a fazy zostaną "wkopnięte" do stanu dwóch górnych kubitów. Przeanalizujmy ten obwód starannie, korzystając z poniższego rysunku.

Stan $\vert\pi_1\rangle$ możemy zapisać tak:

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

Gdy wykonywana jest pierwsza operacja kontrolowanego-$U$, eigenvalue $\lambda = e^{2\pi i\theta}$ zostaje wkopnięta do fazy, gdy $a_0$ (górny kubit) jest równe $1$, ale nie gdy jest równe $0$. Możemy więc wyrazić wynikowy stan w następujący sposób:

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

Druga i trzecia bramka kontrolowanego-$U$ robią coś podobnego, z tym że dla $a_1$ zamiast $a_0$, oraz z $\theta$ zastąpionym przez $2\theta$. Możemy wyrazić wynikowy stan w następujący sposób:

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

Jeśli pomyślimy o ciągu binarnym $a_1 a_0$ jako reprezentującym liczbę całkowitą $x \in \{0,1,2,3\}$ w zapisie binarnym, czyli $x = 2 a_1 + a_0$, możemy alternatywnie wyrazić ten stan następująco.

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

Naszym celem jest wydobycie z tego stanu jak największej ilości informacji o $\theta.$

W tym momencie rozważymy szczególny przypadek, w którym mamy zapewnione, że $\theta = \frac{y}{4}$ dla pewnej liczby całkowitej $y\in\{0,1,2,3\}.$ Innymi słowy, mamy $\theta\in \{0, 1/4, 1/2, 3/4\},$ więc możemy wyrazić tę liczbę dokładnie w zapisie binarnym za pomocą dwóch bitów, jako .$00,$ .$01,$ .$10,$ lub .$11.$ Ogólnie $\theta$ może nie być jedną z tych czterech wartości, ale rozważenie tego szczególnego przypadku pomoże nam rozpracować, jak najskuteczniej wydobywać informacje o $\theta$ w ogólnym przypadku.

Najpierw zdefiniujemy dwukubitowy wektor stanu dla każdej możliwej wartości $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 uproszczeniu wykładników możemy zapisać te wektory następująco.

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

Te wektory są ortogonalne: jeśli wybierzemy dowolną ich parę i obliczymy ich iloczyn skalarny, otrzymamy $0$. Każdy z nich jest również wektorem jednostkowym, więc $\{\vert\phi_0\rangle, \vert\phi_1\rangle, \vert\phi_2\rangle, \vert\phi_3\rangle\}$ jest bazą ortonormalną. Wiemy zatem od razu, że istnieje pomiar, który może je doskonale rozróżnić — co oznacza, że jeśli otrzymamy jeden z nich, ale nie wiemy który, to możemy bezbłędnie ustalić, który to jest.

Aby wykonać takie rozróżnienie za pomocą obwodu kwantowego, możemy najpierw zdefiniować operację unitary $V,$ która przekształca stany bazy standardowej w cztery wymienione powyżej stany.

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

Aby zapisać $V$ jako macierz $4\times 4$, wystarczy wziąć kolumny $V$ jako stany $\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}$$

To jest szczególna macierz i prawdopodobnie niektórzy czytelnicy już się z nią spotkali: jest to macierz związana z $4$-wymiarową dyskretną transformatą Fouriera. W świetle tego faktu nazwijmy ją $\mathrm{QFT}_4$ zamiast $V$. Nazwa $\mathrm{QFT}$ to skrót od quantum Fourier transform (kwantowa transformata Fouriera) — która jest w istocie po prostu dyskretną transformatą Fouriera rozpatrywaną jako operacja unitary. Wkrótce omówimy QFT bardziej szczegółowo i ogólnie.

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

Możemy wykonać odwrotność tej operacji, aby przejść w drugą stronę, czyli przekształcić stany $\vert\phi_0\rangle,\ldots,\vert\phi_3\rangle$ w stany bazy standardowej $\vert 0\rangle,\ldots,\vert 3\rangle$. Jeśli to zrobimy, to możemy wykonać pomiar, aby dowiedzieć się, która wartość $y\in\{0,1,2,3\}$ opisuje $\theta$ jako $\theta = y/4$. Oto schemat obwodu kwantowego, który to realizuje.

Podsumowując, jeśli uruchomimy ten obwód, gdy $\theta = y/4$ dla $y\in\{0,1,2,3\}$, stan bezpośrednio przed wykonaniem pomiarów będzie $\vert \psi\rangle \vert y\rangle$ (dla $y$ zakodowanego jako dwubitowy ciąg binarny), więc pomiary ujawnią wartość $y$ bez błędu.

Ten obwód jest motywowany szczególnym przypadkiem $\theta \in \{0,1/4,1/2,3/4\}$ — ale możemy go uruchomić dla dowolnego wyboru $U$ i $\vert \psi\rangle$, a zatem dla dowolnej wartości $\theta$, jaką chcemy. Oto wykres prawdopodobieństw wyjściowych, które obwód produkuje dla dowolnych wyborów $\theta$.

Jest to wyraźne ulepszenie w stosunku do wariantu jednokubitowego opisanego wcześniej w lekcji. Nie jest doskonały — może dać nam błędną odpowiedź — ale odpowiedź jest silnie przesunięta w stronę wartości $y$, dla których $y/4$ jest bliskie $\theta$. W szczególności najbardziej prawdopodobny wynik zawsze odpowiada wartości $y/4$ najbliższej $\theta$ (utożsamiając $\theta = 0$ i $\theta = 1$ jak poprzednio), a z wykresu wynika, że ta najbliższa wartość dla $x$ zawsze pojawia się z prawdopodobieństwem tuż powyżej $40\%$. Gdy $\theta$ jest dokładnie w połowie drogi między dwiema takimi wartościami, jak na przykład $\theta = 0.375$, dwie równie bliskie wartości $y$ są jednakowo prawdopodobne.

Przygotowanie do uogólnienia na wiele kubitów

Biorąc pod uwagę poprawę, jaką właśnie uzyskaliśmy dzięki użyciu dwóch kubitów kontrolnych zamiast jednego, w połączeniu z odwrotnością $4$-wymiarowej QFT, naturalne jest rozważenie dalszego uogólnienia — poprzez dodanie większej liczby kubitów kontrolnych. Gdy to zrobimy, otrzymamy ogólną procedurę estymacji fazy. Wkrótce zobaczymy, jak to działa, ale aby opisać to precyzyjnie, musimy omówić QFT w większej ogólności, aby zobaczyć, jak jest ona zdefiniowana dla innych wymiarów i jak możemy ją (lub jej odwrotność) zaimplementować za pomocą obwodu kwantowego.

Kwantowa transformata Fouriera

Kwantowa transformata Fouriera jest operacją unitary, którą można zdefiniować dla dowolnego dodatniego wymiaru całkowitego $N$. W tej sekcji zobaczymy, jak ta operacja jest zdefiniowana i jak można ją zaimplementować za pomocą obwodu kwantowego na $m$ kubitach o koszcie $O(m^2)$, gdy $N = 2^m$.

Macierze opisujące kwantową transformatę Fouriera są wyprowadzane z analogicznej operacji na wektorach $N$-wymiarowych znanej jako dyskretna transformata Fouriera. O tej operacji można myśleć na różne sposoby. Na przykład możemy myśleć o dyskretnej transformacie Fouriera w czysto abstrakcyjnych, matematycznych kategoriach jako o odwzorowaniu liniowym. Albo możemy myśleć o niej w kategoriach obliczeniowych, gdzie mamy dany $N$-wymiarowy wektor liczb zespolonych (używając zapisu binarnego do zakodowania części rzeczywistych i urojonych wpisów, jak załóżmy), a celem jest obliczenie $N$-wymiarowego wektora otrzymanego przez zastosowanie dyskretnej transformaty Fouriera. Skupimy się na trzecim sposobie, którym jest postrzeganie tej transformacji jako operacji unitary, którą można wykonać na układzie kwantowym.

Istnieje efektywny algorytm obliczania dyskretnej transformaty Fouriera dla zadanego wektora wejściowego, znany jako szybka transformata Fouriera. Ma zastosowania w przetwarzaniu sygnałów i wielu innych dziedzinach i jest uważana przez wielu za jeden z najważniejszych algorytmów kiedykolwiek odkrytych. Jak się okazuje, implementacja kwantowej transformaty Fouriera, gdy $N$ jest potęgą 2, którą będziemy studiować, opiera się dokładnie na tej samej strukturze podstawowej, która umożliwia szybką transformatę Fouriera.

Definicja kwantowej transformaty Fouriera

Aby zdefiniować kwantową transformatę Fouriera, najpierw zdefiniujemy liczbę zespoloną $\omega_N$, dla każdej dodatniej liczby całkowitej $N$, w następujący sposób:

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

Jest to liczba na zespolonym okręgu jednostkowym, którą otrzymujemy, jeśli zaczynamy od $1$ i poruszamy się w kierunku przeciwnym do ruchu wskazówek zegara o kąt $2\pi/N$ radianów, czyli o ułamek $1/N$ obwodu okręgu. Oto kilka przykładów:

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

Teraz możemy zdefiniować $N$-wymiarową kwantową transformatę Fouriera, która jest opisana macierzą $N\times N$, której wiersze i kolumny są powiązane ze standardowymi stanami bazowymi $\vert 0\rangle,\ldots,\vert N-1\rangle$. Będziemy potrzebować tej operacji tylko wtedy, gdy $N = 2^m$ jest potęgą $2$ na potrzeby estymacji fazy, ale operację tę można zdefiniować dla dowolnej dodatniej liczby całkowitej $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 już stwierdzono, jest to macierz powiązana z $N$-wymiarową dyskretną transformatą Fouriera. Często wiodący czynnik $1/\sqrt{N}$ nie jest uwzględniany w definicji tej macierzy, ale musimy go uwzględnić, aby otrzymać macierz unitary.

Oto kwantowa transformata Fouriera, zapisana jako macierz, dla kilku małych wartości $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}$$

Zwróć uwagę w szczególności, że $\mathrm{QFT}_2$ to inna nazwa operacji Hadamard.

Unitarność

Sprawdźmy, że $\mathrm{QFT}_N$ jest unitary, dla dowolnego wyboru $N$. Jednym ze sposobów na to jest pokazanie, że jej kolumny tworzą bazę ortonormalną. Możemy zdefiniować wektor odpowiadający kolumnie numer $y$, zaczynając od $y = 0$ i dochodząc do $y = N-1$, w następujący sposób:

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

Obliczenie iloczynu skalarnego między dowolnymi dwoma z tych wektorów daje nam następujące wyrażenie:

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

Takie sumy możemy obliczyć, stosując poniższy wzór na sumę pierwszych $N$ wyrazów szeregu geometrycznego.

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

W szczególności możemy użyć tego wzoru, gdy $\alpha = \omega_N^{y-z}$. Gdy $y = z$, mamy $\alpha = 1$, więc użycie wzoru i podzielenie przez $N$ daje

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

Gdy $y\neq z$, mamy $\alpha \neq 1$, więc wzór ujawnia, że:

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

Dzieje się tak, ponieważ $\omega_N^N = e^{2\pi i} = 1$, więc $\omega_N^{N(y-z)} = 1^{y-z} = 1$, co sprawia, że licznik jest zerem, podczas gdy mianownik jest niezerowy, ponieważ $\omega_N^{y-z} \neq 1$. Intuicyjnie rzecz biorąc, to, co robimy, to sumowanie wielu punktów rozmieszczonych wokół okręgu jednostkowego, które przy sumowaniu znoszą się i pozostawiają $0$.

Ustaliliśmy zatem, że $\{\vert\phi_0\rangle,\ldots,\vert\phi_{N-1}\rangle\}$ jest zbiorem ortonormalnym,

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

co ujawnia, że $\mathrm{QFT}_N$ jest unitary.

Bramki kontrolowanej fazy

Aby zaimplementować kwantową transformatę Fouriera za pomocą obwodu kwantowego, będziemy musieli skorzystać z bramek kontrolowanej fazy. Przypomnijmy, że operacja fazy jest jednokubitową operacją unitary postaci

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

dla dowolnej liczby rzeczywistej $\alpha$. Kontrolowana wersja tej bramki ma następującą macierz:

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

W przypadku tej kontrolowanej bramki w rzeczywistości nie ma znaczenia, który kubit jest kontrolny, a który docelowy, ponieważ obie możliwości są równoważne. Do przedstawienia tej bramki na schematach obwodów kwantowych możemy użyć dowolnego z poniższych symboli.

W przypadku trzeciej formy etykieta $\alpha$ jest czasem umieszczana również z boku linii kontrolnej lub pod dolną kontrolą, gdy jest to wygodne.

Aby wykonać kwantową transformatę Fouriera, gdy $N = 2^m$ i $m\geq 2$, będziemy musieli wykonać operację na $m$ kubitach, której działanie na stanach bazy standardowej można opisać jako

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

gdzie $a$ to bit, a $y \in \{0,\ldots,2^{m-1} - 1\}$ to liczba zakodowana w notacji binarnej jako ciąg $m-1$ bitów. Można to wykonać za pomocą bramek kontrolowanej fazy, uogólniając poniższy przykład, dla którego $m=5$.

Ogólnie dla dowolnego wyboru $m\geq 2$, górny kubit odpowiadający bitowi $a$ można traktować jako kontrolę, przy czym bramki fazowe $P_{\alpha}$ sięgają od $\alpha = \pi/2^{m-1}$ na kubicie odpowiadającym najmniej znaczącemu bitowi $y$ do $\alpha = \frac{\pi}{2}$ na kubicie odpowiadającym najbardziej znaczącemu bitowi $y$. Wszystkie te bramki kontrolowanej fazy są przemienne względem siebie i mogą być wykonywane w dowolnej kolejności.

Implementacja obwodowa QFT

Teraz zobaczymy, jak zaimplementować kwantową transformatę Fouriera za pomocą obwodu, gdy wymiar $N = 2^m$ jest potęgą $2$. W rzeczywistości istnieje wiele sposobów implementacji kwantowej transformaty Fouriera, ale ten jest prawdopodobnie najprostszą znaną metodą. Gdy już wiemy, jak zaimplementować kwantową transformatę Fouriera za pomocą obwodu kwantowego, bezpośrednio wynika z tego sposób implementacji jej odwrotności: możemy zastąpić każdą bramkę jej odwrotnością (lub równoważnie sprzężeniem hermitowskim) i zastosować bramki w odwrotnej kolejności. Każdy obwód kwantowy złożony wyłącznie z bramek unitary można odwrócić w ten sposób.

Implementacja ma charakter rekurencyjny, więc tak jest najbardziej naturalnie opisana. Przypadkiem bazowym jest $m=1$, w którym kwantowa transformata Fouriera jest operacją Hadamarda.

Aby wykonać kwantową transformatę Fouriera na $m$ kubitach, gdy $m \geq 2$, możemy wykonać następujące kroki, których działania opiszemy dla stanów bazy standardowej postaci $\vert x \rangle \vert a\rangle$, gdzie $x\in\{0,\ldots,2^{m-1} - 1\}$ jest liczbą całkowitą zakodowaną jako $m-1$ bitów w notacji binarnej, a $a$ jest pojedynczym bitem.

1. Najpierw zastosuj $2^{m-1}$-wymiarową kwantową transformatę Fouriera do dolnych/najbardziej lewych $m-1$ kubitów, aby uzyskać ten stan:

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

   Odbywa się to poprzez rekurencyjne zastosowanie opisywanej metody dla jednego kubitu mniej, przy użyciu operacji Hadamarda na pojedynczym kubicie jako przypadku bazowego.

2. Użyj górnego/najbardziej prawego kubitu jako kontroli do wstrzyknięcia fazy $\omega_{2^m}^y$ dla każdego stanu bazy standardowej $\vert y\rangle$ pozostałych $m-1$ kubitów (jak opisano powyżej), aby uzyskać ten stan:

   $$\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. Wykonaj bramkę Hadamarda na górnym/najbardziej prawym kubicie, aby uzyskać ten stan:

   $$\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. Dokonaj permutacji kolejności kubitów tak, aby najmniej znaczący bit stał się najbardziej znaczącym bitem, z wszystkimi pozostałymi przesuniętymi w górę/w prawo:

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

Na przykład oto obwód, który otrzymujemy dla $N = 32 = 2^5$. Na tym schemacie kubitom nadano nazwy odpowiadające standardowym wektorom bazowym $\vert x\rangle \vert a\rangle$ (dla wejścia) i $\vert b\rangle \vert y\rangle$ (dla wyjścia) dla jasności.

Analiza

Kluczowym wzorem, którego potrzebujemy do zweryfikowania, że opisany powyżej obwód implementuje $2^m$-wymiarową kwantową transformatę Fouriera, jest ten:

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

Wzór ten działa dla dowolnego wyboru liczb całkowitych $a,$ $b,$ $x$ i $y,$ ale będziemy go potrzebować jedynie dla $a,b\in\{0,1\}$ oraz $x,y\in\{0,\ldots,2^{m-1}-1\}.$ Można go sprawdzić, rozwijając iloczyn w wykładniku po prawej stronie,

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

gdzie druga równość wykorzystuje spostrzeżenie, że

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

$2^m$-wymiarowa kwantowa transformata Fouriera jest zdefiniowana następująco dla każdego $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$$

Jeśli zapiszemy $u$ i $v$ jako

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

dla $a,b\in\{0,1\}$ oraz $x,y\in\{0,\ldots,2^{m-1} - 1\}$, otrzymujemy

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

Wreszcie, myśląc o stanach bazy standardowej $\vert x \rangle \vert a\rangle$ i $\vert b \rangle \vert y \rangle$ jako o binarnych zakodowaniach liczb całkowitych z zakresu $\{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}$$

widzimy, że powyższy obwód implementuje wymaganą operację. Jeśli ta metoda wykonywania kwantowej transformaty Fouriera wydaje się niezwykła, to dlatego, że taka jest: jest to zasadniczo szybka transformata Fouriera w formie obwodu kwantowego.

Na koniec policzmy, ile bramek jest używanych w opisanym powyżej obwodzie. Bramki kontrolowanej fazy nie należą do standardowego zestawu bramek, który omówiliśmy w poprzedniej lekcji, ale na początek zignorujemy to i policzymy każdą z nich jako pojedynczą bramkę.

Niech $s_m$ oznacza liczbę bramek, których potrzebujemy dla każdego możliwego wyboru $m$. Jeśli $m=1$, kwantowa transformata Fouriera jest po prostu operacją Hadamarda, zatem

$$s_1 = 1.$$

Jeśli $m\geq 2$, to w powyższym obwodzie potrzebujemy $s_{m-1}$ bramek dla kwantowej transformaty Fouriera na $m-1$ kubitach, plus $m-1$ bramek kontrolowanej fazy, plus jedną bramkę Hadamarda, plus $m-1$ bramek zamiany, zatem

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

Wyrażenie w formie zamkniętej możemy uzyskać poprzez zsumowanie:

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

W rzeczywistości nie potrzebujemy aż tylu bramek zamiany, ile opisuje metoda. Jeśli trochę przearanżujemy bramki, możemy przesunąć wszystkie bramki zamiany na prawo i zredukować liczbę potrzebnych bramek zamiany do $\lfloor m/2\rfloor$. Asymptotycznie nie jest to znacząca poprawa: nadal otrzymujemy obwody o rozmiarze $O(m^2)$ do wykonywania $\mathrm{QFT}_{2^m}$.

Jeśli chcemy zaimplementować kwantową transformatę Fouriera przy użyciu wyłącznie bramek z naszego standardowego zestawu bramek, musimy albo zbudować, albo przybliżyć każdą z bramek kontrolowanej fazy bramkami z naszego zestawu. Wymagana liczba zależy od tego, jakiej dokładności wymagamy, ale jako funkcja $m$ całkowity koszt pozostaje kwadratowy.

W rzeczywistości możliwe jest dość dokładne przybliżenie kwantowej transformaty Fouriera przy użyciu subkwadratowej liczby bramek, wykorzystując fakt, że $P_{\alpha}$ jest bardzo bliskie operacji identyczności, gdy $\alpha$ jest bardzo małe — co oznacza, że możemy po prostu pominąć większość bramek kontrolowanej fazy bez zbyt dużej straty dokładności.

Ogólna procedura i analiza

Teraz przyjrzymy się procedurze estymacji fazy w ujęciu ogólnym. Pomysł polega na rozszerzeniu dwukubitowej wersji estymacji fazy, którą rozważaliśmy powyżej, w naturalny sposób sugerowany przez poniższy diagram.

Zauważ, że dla każdego nowego kubitu sterującego dodanego na górze podwajamy liczbę wykonań operacji unitary $U$. Jest to zaznaczone na diagramie przez potęgi $U$ dla każdej ze sterowanych operacji unitary.

Najbardziej bezpośredni sposób implementacji operacji sterowanej-$U^k$ dla pewnego wyboru $k$ polega po prostu na powtórzeniu operacji sterowanej-$U$ $k$ razy. Jeśli rzeczywiście stosuje się tę metodologię, trzeba zdać sobie sprawę, że dodawanie kubitów sterujących znacząco powiększa rozmiar obwodu: jeśli mamy $m$ kubitów sterujących, tak jak przedstawia to diagram, potrzeba łącznie $2^m - 1$ kopii operacji sterowanej-$U$. Oznacza to, że wraz ze zwiększaniem $m$ ponosimy istotny koszt obliczeniowy — ale jak zobaczymy, prowadzi to również do znacznie dokładniejszego przybliżenia $\theta$.

Ważne jest jednak, aby zauważyć, że dla niektórych wyborów $U$ może być możliwe zbudowanie obwodu, który implementuje operację $U^k$ dla dużych wartości $k$ w sposób bardziej efektywny niż zwykłe $k$-krotne powtarzanie obwodu dla $U$. Zobaczymy konkretny przykład tego w kontekście faktoryzacji liczb całkowitych w dalszej części lekcji, gdzie z pomocą przyjdzie efektywny algorytm potęgowania modularnego omówiony w poprzedniej lekcji.

Przeanalizujmy teraz właśnie opisany obwód. Stan bezpośrednio przed odwrotną kwantową transformatą Fouriera wygląda następująco:

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

Przypadek szczególny

Podobnie do tego, co zrobiliśmy w przypadku $m=2$, najpierw rozważymy szczególny przypadek, gdy $\theta = y/2^m$ dla $y\in\{0,\ldots,2^m-1\}$. W tym przypadku stan przed odwrotną kwantową transformatą Fouriera można alternatywnie zapisać tak:

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

Zatem po zastosowaniu odwrotnej kwantowej transformaty Fouriera stan staje się

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

a pomiary ujawniają $y$ (zakodowane binarnie).

Ograniczanie prawdopodobieństw

Dla innych wartości $\theta$, czyli takich, które nie mają postaci $y/2^m$ dla całkowitego $y$, wyniki pomiaru nie będą pewne, ale możemy udowodnić ograniczenia prawdopodobieństw dla różnych wyników. W dalszej części rozważmy dowolny wybór $\theta$ spełniający $0\leq \theta < 1$.

Po wykonaniu odwrotnej kwantowej transformaty Fouriera stan obwodu jest taki:

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

Zatem, gdy wykonywane są pomiary na górnych $m$ kubitach, widzimy każdy wynik $y$ z prawdopodobieństwem

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

Aby lepiej ogarnąć te prawdopodobieństwa, skorzystamy z tego samego wzoru, który widzieliśmy wcześniej, na sumę początkowej części szeregu geometrycznego.

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

Możemy uprościć sumę pojawiającą się we wzorze na $p_y$ biorąc $\alpha = e^{2\pi i (\theta - y/2^m)}$. Oto co otrzymujemy.

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

Zatem w przypadku, gdy $\theta = y/2^m$, znajdujemy $p_y = 1$ (jak już wiedzieliśmy z rozpatrywania tego szczególnego przypadku), a w przypadku, gdy $\theta \neq y/2^m$, znajdujemy

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

Możemy dowiedzieć się więcej o tych prawdopodobieństwach, myśląc o tym, jak długości łuków i długości cięciw na okręgu jednostkowym są powiązane. Oto rysunek, który ilustruje zależności potrzebne nam dla każdej liczby rzeczywistej $\delta\in \bigl[ -\frac{1}{2},\frac{1}{2}\bigr]$.

Po pierwsze, długość cięciwy (narysowana na niebiesko) nie może być większa niż długość łuku (narysowana na fioletowo):

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

Powiązując te długości w innym kierunku, widzimy, że stosunek długości łuku do długości cięciwy jest największy, gdy $\delta = \pm 1/2$, a w tym przypadku stosunek ten jest połową obwodu okręgu podzieloną przez średnicę, co daje $\pi/2$. Dlatego mamy

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

and so

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

Analiza oparta na tych relacjach ujawnia następujące dwa fakty.

1. Załóżmy, że $\theta$ jest liczbą rzeczywistą, a $y\in \{0,\ldots,2^m-1\}$ spełnia

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

   Oznacza to, że $y/2^m$ jest albo najlepszym $m$-bitowym przybliżeniem $\theta$, albo znajduje się dokładnie w połowie odległości między $y/2^m$ a $(y-1)/2^m$ lub $(y+1)/2^m$, jest więc jednym z dwóch najlepszych przybliżeń $\theta$.

   Udowodnimy, że $p_y$ musi być w tym przypadku dość duże. Z założenia, które rozważamy, wynika, że $\vert 2^m \theta - y \vert \leq 1/2$, więc możemy wykorzystać drugą powyższą obserwację dotyczącą długości łuków i cięciw, aby stwierdzić, ż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.$$

   Możemy również wykorzystać pierwszą obserwację dotyczącą długości łuków i cięciw, aby stwierdzić, ż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.$$

   Wykorzystanie tych dwóch nierówności w odniesieniu do $p_y$ ujawnia

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

   Wyjaśnia to naszą obserwację, że najlepszy wynik występuje z prawdopodobieństwem większym niż $40\%$ w wersji estymacji fazy dla $m=2$ omawianej wcześniej. To nie jest naprawdę 40%, tylko $4/\pi^2$, i w istocie ograniczenie to obowiązuje dla każdego wyboru $m$.

2. Załóżmy teraz, że $y\in \{0,\ldots,2^m-1\}$ spełnia

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

   Oznacza to, że istnieje lepsze przybliżenie $z/2^m$ liczby $\theta$ pomiędzy $\theta$ a $y/2^m$.

   Tym razem udowodnimy, że $p_y$ nie może być zbyt duże. Możemy zacząć od prostej obserwacji, że

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

   co wynika z faktu, że dowolne dwa punkty na okręgu jednostkowym mogą różnić się co do wartości bezwzględnej o co najwyżej $2$.

   Możemy również wykorzystać drugą powyższą obserwację dotyczącą długości łuków i cięciw, tym razem działając na mianowniku $p_y$ zamiast licznika, aby stwierdzić, że

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

   Złożenie tych dwóch nierówności razem ujawnia

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

   Zauważ, że chociaż to ograniczenie jest wystarczająco dobre dla naszych celów, jest dość zgrubne — prawdopodobieństwo jest zwykle znacznie niższe niż $1/4$.

Ważnym wnioskiem płynącym z tej analizy jest to, że bardzo bliskie przybliżenia $\theta$ są prawdopodobne — otrzymamy najlepsze $m$-bitowe przybliżenie z prawdopodobieństwem większym niż $40\%$ — podczas gdy przybliżenia odbiegające o więcej niż $2^{-m}$ są mniej prawdopodobne, z prawdopodobieństwem ograniczonym z góry przez $25\%$.

Mając te gwarancje, możemy zwiększyć naszą pewność, powtarzając procedurę estymacji fazy kilka razy, aby zebrać statystyczne dowody na temat $\theta$. Ważne jest, aby zauważyć, że stan $\vert\psi\rangle$ dolnego zbioru kubitów nie zmienia się w wyniku procedury estymacji fazy, więc można go używać do uruchamiania procedury tyle razy, ile chcemy. W szczególności, za każdym razem, gdy uruchamiamy obwód, otrzymujemy najlepsze $m$-bitowe przybliżenie $\theta$ z prawdopodobieństwem większym niż $40\%$, podczas gdy prawdopodobieństwo odchylenia o więcej niż $2^{-m}$ jest ograniczone przez $25\%$. Jeśli uruchomimy obwód kilka razy i weźmiemy najczęściej pojawiający się wynik uruchomień, to jest niezwykle prawdopodobne, że wynik, który pojawia się najczęściej, nie będzie tym, który występuje co najwyżej $25\%$ czasu. W rezultacie bardzo prawdopodobne jest, że otrzymamy przybliżenie $y/2^m$ znajdujące się w odległości mniejszej niż $1/2^m$ od wartości $\theta$. Istotnie, mało prawdopodobne ryzyko, że odchylimy się o więcej niż $1/2^m$, maleje wykładniczo wraz z liczbą uruchomień procedury.

Oto dwa wykresy przedstawiające prawdopodobieństwa dla trzech kolejnych wartości $y$, gdy $m = 3$ i $m=4$, jako funkcje $\theta$. (Dla przejrzystości pokazano tylko trzy wyniki. Prawdopodobieństwa dla innych wyników uzyskuje się przez cykliczne przesunięcie tej samej funkcji bazowej.)