Jak zbudować operację Uf w algorytmie Shora za pomocą bramek kwantowych?

Zaczniemy od przypomnienia, że |x⟩ oraz |y⟩ reprezentują górne i dolne cyfry systemu bazowego w przestrzeni b2L, a operacja ⊕ oznacza dodawanie w modulo 2. Działanie to jest wykonywane bit po bicie, przy czym dodawanie nie uwzględnia przeniesienia, co oznacza, że 1 + 1 = 0. To kończy potwierdzenie, ponieważ operator Uf jest oczywiście unitarne. Zauważmy, że unitarność Uf wynika z parowania x, f(x), a więc bez „wymazywania” jakichkolwiek informacji.

Warto podkreślić, że konstrukcja operatora Uf nie powinna polegać na obliczeniu wartości funkcji f(x) dla każdego x osobno. Funkcja f powinna być taka, aby operator Uf był rzeczywiście programowalny za pomocą uniwersalnych bramek kwantowych, podobnie jak obliczenia na komputerach klasycznych są ograniczone do tych, które można zrealizować za pomocą uniwersalnych bramek logicznych klasycznych. Więcej informacji na ten temat można znaleźć w notach [47.3]–[47.7].

Teraz przejdźmy do istoty teorii Shora. Rozpoczynamy od założenia, że L spełnia nierówność 2L−1 ≤ q2 < 2L, gdzie q to moduł w naszym pierwotnym problemie. Wartość L jest dobierana w taki sposób, aby stało się to jasne w kontekście dalszych obliczeń w kolejnych sekcjach. Przygotowujemy dwie tablice rejestrów kwantowych L, z których każda zawiera ortonormalną bazę przestrzeni q2L. Ponadto, funkcja g(x) jest dodatnia i mniejsza od q, a g(x) ≡ ax mod q. Rozważamy teraz mapowanie Ug w przestrzeni q2L.

Aby to osiągnąć, inicjujemy komputer r2L w stanie |0⟩ |0⟩, gdzie |0⟩ ∈ bL, czyli stan początkowy wynosi |ξin⟩ = |0⟩ |0⟩. Następnie każdemu z górnych L kubitów stosujemy operator Hadamarda, który przekształca stan |0⟩ w (1/√2)(|0⟩ + |1⟩), a stan |1⟩ w (1/√2)(|0⟩ − |1⟩). Jest to równoważne przekształceniu |x⟩ ∈ bL do 2^(-1/2) Σ y=0,1 e^(-ixy/2) |y⟩, gdzie e(η) = exp(2πiη). W wyniku tego procesu stan r2L przyjmuje postać 2^(-L/2) Σ (x=0 to 2L−1) |x⟩ |0⟩.

Następnie stosujemy operator Ug, którego działanie na stan r2L, zgodnie z równaniem (47.10), prowadzi do stanu |x⟩ |g(ρ)⟩. W tym miejscu ρ to okres funkcji a mod q, czyli λ. Zdefiniowanie Ug w kategoriach bramek kwantowych jest szczegółowo opisane w nocie [47.6].

Po tym wszystkim dokonujemy pomiaru wektora wynikowego. Na podstawie aksjomatu (47.3), wyjściowe wartości {ξ, g(ρ)} mają pojawić się z prawdopodobieństwem P(ξ, ρ) = | Σ e^(-ixξ/2L) |², przy czym sumowanie odbywa się po wszystkich x, które są równe ρ modulo λ. Dzięki zastosowaniu transformacji Fouriera, rozkład prawdopodobieństwa wyjściowych wartości zyskuje wyraźnie zauważalną tendencję, co pozwala na uzyskanie pożądanego wyniku.

Warto zaznaczyć, że jeśli pomiar zostałby dokonany na etapie (47.10), wyniki byłyby rozłożone równomiernie, a w celu znalezienia okresu λ należałoby powtarzać operację wielokrotnie, co byłoby absurdalne. Dlatego transformacja Fouriera została zastosowana, aby wzmocnić wyjściowy rozkład, co pozwala na łatwiejsze odczytanie okresu λ. Efekt wzmocnienia, indukowany przez transformację Fouriera, zostanie potwierdzony w kolejnej części dowodu twierdzenia Shora.

Na zakończenie, podczas całego procesu obliczeniowego na komputerze kwantowym, obserwujemy, że wyniki są probabilistyczne i mogą się różnić przy kolejnych próbach. Istotą algorytmu kwantowego jest to, że mimo iż poszczególne uruchomienia mogą dawać różne wyniki, ogólny rozkład wyników umożliwia wyciągnięcie odpowiedzi na zadane pytanie. Wynika to z faktu, że operacje na komputerze kwantowym są zasadniczo oparte na superpozycjach stanów, a sam proces obliczeniowy nie wymaga jawnego śledzenia stanu komputera w trakcie jego działania.

Jak rozumieć teorię form kwadratowych i ideali macierzy?

Teoria form kwadratowych jest fundamentalnym elementem algebry, który w znaczący sposób wpływa na rozwój matematyki w kontekście struktur algebraicznych, takich jak pierścienie i moduły. Jednym z podstawowych zagadnień, które można analizować w ramach tej teorii, jest pojęcie form kwadratowych w przestrzeni macierzy. W tym kontekście kluczowym jest zrozumienie nie tylko ich struktury, ale i relacji z takimi obiektami algebraicznymi, jak idealne pierścienie macierzy czy moduły.

Rozważając formy kwadratowe, zaczynamy od pojęcia macierzy jako pary uporządkowanej, której elementy są samymi macierzami. To wprowadza ważny aspekt algebry: mnożenie macierzy w tym przypadku jest przemienne, pod warunkiem odpowiedniego doboru parametrów. Takie operacje mogą być przedstawiane przy użyciu specjalnych form, takich jak $Q = \left[ \begin{matrix} a & b \\ c & d \end{matrix} \right] \in Q(D)$, gdzie $a, b, c, d$ są odpowiednimi współczynnikami, a $D$ reprezentuje dyskryminantę tej formy kwadratowej.

Kiedy rozważamy taki obiekt jak $Q$, możemy go zinterpretować jako idealny moduł w pierścieniu, gdzie pierścień ten jest zbudowany z elementów postaci $eZ + \frac{1}{2} (be+d)Z$. Ta struktura jest głębsza niż sama forma $Q$, ponieważ obejmuje dodatkowe warstwy algebraiczne, które umożliwiają bardziej zaawansowaną analizę matematyczną.

Jednym z głównych założeń w tej teorii jest to, że $Q$ stanowi idealny podzbiór pierścienia $ID$, a operacje takie jak mnożenie elementów pierścienia $ID$ na formy kwadratowe zachowują strukturę samego $Q$, tworząc nowe elementy w obrębie tego samego pierścienia. Można tu zastosować podejście podobne do teorii liczb kwadratowych, gdzie przekształcenia związane z danymi parametrami prowadzą do nowych macierzy i nowych form kwadratowych.

Ważne jest zatem, aby zrozumieć, że teoria form kwadratowych i związane z nią obiekty algebraiczne nie są tylko abstrakcyjnymi konstrukcjami matematycznymi. Stanowią one fundament dla zrozumienia bardziej zaawansowanych tematów w matematyce, takich jak teoria liczb, algebra czy geometria algebraiczna. W szczególności, zrozumienie struktury tych form w ramach modułów i ideali pozwala na głębsze zrozumienie wielu algorytmów, które były rozwijane przez takie postacie jak Lagrange czy Gauss, a także stanowi podstawę do badań nad rozmaitymi problemami w teorii liczb.

Z praktycznego punktu widzenia, istotnym aspektem jest umiejętność manipulowania tymi strukturami algebraicznymi w kontekście równań diophantycznych, gdzie odpowiednie reprezentacje liczb jako formy kwadratowe mają kluczowe znaczenie w rozwiązywaniu problemów liczbowych. W tym sensie, opanowanie tych narzędzi pozwala na zastosowanie ich w szerokim zakresie dziedzin matematycznych, w tym w analizie algorytmów numerycznych oraz w badaniach nad własnościami pierścieni liczb algebraicznych.

Należy również pamiętać, że przekształcenia w ramach tych struktur mogą prowadzić do sytuacji, w których reprezentowanie liczb przez formy kwadratowe może nie zawsze być możliwe w sposób jednoznaczny. Stąd konieczność zastosowania bardziej zaawansowanych algorytmów i metod, które pozwalają na kontrolowanie tych zjawisk i umożliwiają skuteczne rozwiązywanie problemów matematycznych związanych z takimi formami.