Mierzenie kosztu obliczeniowego

Następnie omówimy matematyczny sposób ujmowania kosztu obliczeniowego, w wąskim zakresie dostosowanym do potrzeb tego kursu. Analiza algorytmów i złożoność obliczeniowa same w sobie są odrębnymi dziedzinami i mają znacznie więcej do powiedzenia na temat tych pojęć.

Na początek rozważmy następujący rysunek z poprzedniej lekcji, który przedstawia bardzo wysoki poziom abstrakcji obliczenia.

Samo obliczenie może być modelowane lub opisywane na różne sposoby, na przykład jako program komputerowy napisany w języku Python, maszyna Turinga, obwód boolean lub obwód kwantowy. Skupimy się na obwodach (zarówno boolean, jak i kwantowych).

Kodowania i długość wejścia

Zacznijmy od wejścia i wyjścia problemu obliczeniowego, które przyjmiemy jako ciągi binarne. Można użyć różnych symboli, ale na potrzeby tej dyskusji uprościmy rozważania, ograniczając naszą uwagę do wejść i wyjść w postaci ciągów binarnych. Za pomocą ciągów binarnych możemy zakodować różnorodne interesujące obiekty, których mogą dotyczyć rozwiązywane przez nas problemy, takie jak liczby, wektory, macierze i grafy, a także listy tych i innych obiektów.

Na przykład, do zakodowania nieujemnych liczb całkowitych możemy użyć notacji binarnej. Poniższa tabela przedstawia binarne kodowanie pierwszych dziewięciu nieujemnych liczb całkowitych wraz z długością (czyli całkowitą liczbą bitów) każdego kodowania.

Liczba	Kodowanie binarne	Długość
0	0	1
1	1	1
2	10	2
3	11	2
4	100	3
5	101	3
6	110	3
7	111	3
8	1000	4

Możemy łatwo rozszerzyć to kodowanie, aby obsługiwało zarówno dodatnie, jak i ujemne liczby całkowite, dodając do reprezentacji bit znaku, jeśli tak zdecydujemy. Czasem wygodne jest również dopuszczenie binarnych reprezentacji nieujemnych liczb całkowitych z wiodącymi zerami, które nie zmieniają kodowanej wartości, ale pozwalają reprezentacjom wypełnić ciąg lub słowo o ustalonym rozmiarze.

Użycie notacji binarnej do reprezentowania nieujemnych liczb całkowitych jest zarówno powszechne, jak i wydajne, ale gdybyśmy chcieli, moglibyśmy wybrać inny sposób reprezentowania nieujemnych liczb całkowitych za pomocą ciągów binarnych, takie jak te zaproponowane w poniższej tabeli. Szczegóły tych alternatyw nie są istotne dla tej dyskusji — chodzi jedynie o wyjaśnienie, że mamy wybór co do stosowanych kodowań.

Liczba	Kodowanie unarne	Kodowanie leksykograficzne
0	$\varepsilon$	$\varepsilon$
1	0	0
2	00	1
3	000	00
4	0000	01
5	00000	10
6	000000	11
7	0000000	000
8	00000000	001

(W tej tabeli symbol $\varepsilon$ reprezentuje pusty ciąg, który nie zawiera żadnych symboli i ma długość równą zero. Naturalnie, aby uniknąć oczywistego źródła nieporozumień, do reprezentowania pustego ciągu używamy specjalnego symbolu takiego jak $\varepsilon$, zamiast dosłownie nie pisać niczego.)

Inne typy wejść, takie jak wektory i macierze lub bardziej skomplikowane obiekty, takie jak opisy cząsteczek, również mogą być kodowane jako ciągi binarne. Podobnie jak w przypadku nieujemnych liczb całkowitych, można wybrać lub wymyślić różne schematy kodowania. Niezależnie od tego, jaki schemat wymyślimy do kodowania wejść dla danego problemu, interpretujemy długość ciągu wejściowego jako reprezentującą rozmiar rozwiązywanej instancji problemu.

Na przykład liczba bitów wymagana do wyrażenia nieujemnej liczby całkowitej $N$ w notacji binarnej, oznaczana czasem przez $\operatorname{lg}(N),$ dana jest następującym wzorem.

$$\operatorname{lg}(N) = \begin{cases} 1 & N = 0\\ 1 + \lfloor \log_2 (N) \rfloor & N \geq 1 \end{cases}$$

Zakładając, że używamy notacji binarnej do kodowania wejścia w problemie faktoryzacji liczb całkowitych, długość wejścia dla liczby $N$ wynosi zatem $\operatorname{lg}(N).$ Zauważmy w szczególności, że długość (lub rozmiar) wejścia $N$ nie jest równa samemu $N$; gdy $N$ jest duże, nie potrzebujemy ani w przybliżeniu tylu bitów do wyrażenia $N$ w notacji binarnej.

Ze ściśle formalnego punktu widzenia, ilekroć rozważamy problem lub zadanie obliczeniowe, należy rozumieć, że wybrano konkretny schemat do kodowania obiektów podawanych jako wejście lub produkowanych jako wyjście. Pozwala to postrzegać obliczenia rozwiązujące interesujące problemy w sposób abstrakcyjny, jako przekształcenia wejść w postaci ciągów binarnych na wyjścia w postaci ciągów binarnych.

Szczegóły dotyczące tego, jak obiekty są kodowane jako ciągi binarne, muszą na pewnym poziomie być ważne dla tych obliczeń. Zazwyczaj jednak nie przejmujemy się zanadto tymi szczegółami podczas analizy kosztu obliczeniowego, aby uniknąć wchodzenia w detale o drugorzędnym znaczeniu. Podstawowe rozumowanie jest takie, że oczekujemy, iż koszt obliczeniowy konwersji tam i z powrotem między "rozsądnymi" schematami kodowania będzie nieistotny w porównaniu z kosztem rozwiązania właściwego problemu. W sytuacjach, w których tak nie jest, szczegóły mogą (i powinny) zostać wyjaśnione.

Na przykład bardzo proste obliczenie dokonuje konwersji między binarną reprezentacją nieujemnej liczby całkowitej a jej kodowaniem leksykograficznym (którego nie wyjaśniliśmy szczegółowo, ale można je wywnioskować z powyższej tabeli). Z tego powodu koszt obliczeniowy faktoryzacji liczb całkowitych nie różniłby się znacząco, gdybyśmy zdecydowali się zmienić jedno z tych kodowań na drugie dla wejścia $N.$ Z drugiej strony kodowanie nieujemnych liczb całkowitych w notacji unarnej powoduje wykładniczy wzrost całkowitej liczby wymaganych symboli i z tego powodu nie uznalibyśmy go za "rozsądny" schemat kodowania.

Operacje elementarne

Rozważmy teraz samo obliczenie, reprezentowane przez niebieski prostokąt na powyższym rysunku. Sposób, w jaki będziemy mierzyć koszt obliczeniowy, polega na zliczaniu liczby operacji elementarnych, jakich wymaga każde obliczenie. Intuicyjnie mówiąc, operacja elementarna to taka, która obejmuje małą, ustaloną liczbę bitów lub kubitów i może być wykonana szybko i łatwo — na przykład obliczanie AND dwóch bitów. Natomiast uruchomienie funkcji factorint nie może być rozsądnie postrzegane jako operacja elementarna.

Formalnie rzecz biorąc, istnieją różne wybory co do tego, co stanowi operację elementarną, w zależności od używanego modelu obliczeń. Skupimy się na modelach obwodów, a konkretnie na obwodach kwantowych i obwodach logicznych.

Uniwersalne zbiory bramek

W modelach obliczeń opartych na obwodach typowe jest traktowanie każdej bramki jako operacji elementarnej. Prowadzi to do pytania, jakie dokładnie bramki dopuszczamy w naszych obwodach. Skupiając się na razie na obwodach kwantowych, do tej pory w tej serii widzieliśmy kilka bramek, w tym bramki $X,$ $Y,$ $Z,$ $H,$ $S$ i $T,$ bramki swap, kontrolowane wersje bramek (w tym bramki controlled-NOT, Toffoli i Fredkina), a także bramki reprezentujące pomiary w bazie standardowej. W kontekście gry CHSH widzieliśmy również kilka dodatkowych bramek rotacji.

Omówiliśmy również bramki zapytań w kontekście modelu zapytań, a także widzieliśmy, że każda operacja unitary $U,$ działająca na dowolnej liczbie kubitów, może być postrzegana jako bramka, jeśli tak wybierzemy — ale pominiemy obie te opcje na potrzeby tej dyskusji. Nie będziemy pracować w modelu zapytań (choć implementacja bramek zapytań za pomocą operacji elementarnych jest omawiana później w lekcji), a postrzeganie dowolnych bramek unitary, potencjalnie działających na milionach kubitów, jako operacji elementarnych nie prowadzi do sensownych ani realistycznych pojęć kosztu obliczeniowego.

Pozostając przy bramkach kwantowych działających na małej liczbie kubitów, jednym podejściem do decydowania, które z nich uznać za elementarne, jest wypracowanie precyzyjnego kryterium — ale nie jest to standardowe podejście ani takie, które przyjmiemy. Zamiast tego po prostu dokonujemy wyboru.

Oto jeden standardowy wybór, który przyjmiemy jako domyślny zbiór bramek dla obwodów kwantowych:

• Jednokubitowe bramki unitary z tej listy: $X,$ $Y,$ $Z,$ $H,$ $S,$ $S^{\dagger},$ $T$ i $T^{\dagger}$
• Bramki Controlled-NOT
• Jednokubitowe pomiary w bazie standardowej

Powszechną alternatywą jest postrzeganie bramek Toffoli, Hadamard i $S$ jako elementarnych, oprócz pomiarów w bazie standardowej. Czasami wszystkie bramki jednokubitowe są postrzegane jako elementarne, choć prowadzi to do nierealistycznie potężnego modelu, gdy dokładność, z jaką bramki są wykonywane, nie jest odpowiednio uwzględniona.

Bramki unitary w naszej domyślnej kolekcji tworzą tak zwany uniwersalny zbiór bramek. Oznacza to, że możemy przybliżać dowolną operację unitary na dowolnej liczbie kubitów z dowolną dokładnością, korzystając wyłącznie z obwodów złożonych z tych bramek. Dla jasności, definicja uniwersalności nie stawia żadnych wymagań co do kosztu takich przybliżeń, czyli liczby bramek z naszego zbioru, jakiej potrzebujemy. Rzeczywiście, dość prosty argument oparty na matematycznym pojęciu miary pokazuje, że większość operacji unitary musi mieć niezwykle wysoki koszt. Dowodzenie uniwersalności kwantowych zbiorów bramek nie jest sprawą prostą i nie będzie omawiane w tym kursie.

W przypadku obwodów logicznych za bramki reprezentujące operacje elementarne przyjmiemy bramki AND, OR, NOT i FANOUT. Tak naprawdę nie potrzebujemy zarówno bramek AND, jak i OR — możemy skorzystać z praw De Morgana, aby zamienić jedną na drugą, umieszczając bramki NOT na wszystkich trzech przewodach wejścia/wyjścia — niemniej jednak zarówno typowe, jak i wygodne jest dopuszczanie obu bramek AND i OR. Bramki AND, OR, NOT i FANOUT tworzą uniwersalny zbiór dla obliczeń deterministycznych, co oznacza, że każdą funkcję z dowolnej ustalonej liczby bitów wejściowych na dowolną ustaloną liczbę bitów wyjściowych można zaimplementować za pomocą tych bramek.

Zasada odroczonego pomiaru

Bramki pomiaru w bazie standardowej mogą pojawiać się w obwodach kwantowych, ale czasami wygodnie jest je odroczyć do końca. Pozwala nam to postrzegać obliczenia kwantowe jako składające się z części unitary (reprezentującej samo obliczenie), po której następuje prosta faza odczytu, w której kubity są mierzone, a wyniki są zwracane. Można to zrobić zawsze, pod warunkiem że jesteśmy skłonni dodać dodatkowy kubit dla każdego pomiaru w bazie standardowej. Na poniższym rysunku obwód po prawej stronie ilustruje, jak można to zrobić dla bramki po lewej stronie.

Konkretnie, klasyczny bit w obwodzie po lewej stronie jest zastąpiony kubitem po prawej stronie (zainicjalizowanym do stanu $\vert 0\rangle$), a pomiar w bazie standardowej jest zastąpiony bramką controlled-NOT, po której następuje pomiar w bazie standardowej na dolnym kubicie. Chodzi o to, że pomiar w bazie standardowej w obwodzie po prawej stronie można przesunąć aż do końca obwodu. Jeśli klasyczny bit w obwodzie po lewej stronie jest później używany jako bit kontrolny, możemy zamiast tego użyć dolnego kubitu w obwodzie po prawej stronie jako kontroli, a ogólny efekt będzie ten sam. (Zakładamy, że klasyczny bit w obwodzie po lewej stronie nie jest nadpisywany po dokonaniu pomiaru przez kolejny pomiar — ale gdyby tak było, zawsze moglibyśmy po prostu użyć nowego klasycznego bitu zamiast nadpisywać ten, który był użyty do poprzedniego pomiaru.)

Rozmiar i głębokość obwodu

Rozmiar obwodu

Całkowita liczba bramek w obwodzie jest nazywana rozmiarem tego obwodu. Zatem, zakładając, że bramki w naszych obwodach reprezentują operacje elementarne, rozmiar obwodu reprezentuje liczbę operacji elementarnych, jakich wymaga — lub, innymi słowy, jego koszt obliczeniowy. Piszemy $\operatorname{size}(C),$ aby odnieść się do rozmiaru danego obwodu $C.$

Na przykład rozważmy następujący obwód logiczny obliczający XOR dwóch bitów.

Rozmiar tego obwodu wynosi 7, ponieważ w sumie jest 7 bramek. (Operacje fanout nie zawsze są liczone jako bramki, ale na potrzeby tej lekcji będziemy je liczyć jako bramki.)

Czas, koszt i głębokość obwodu

Czas jest niezwykle ważnym zasobem lub ograniczającym warunkiem dla obliczeń. Powyższe przykłady, takie jak zadanie faktoryzacji RSA1024, wzmacniają ten pogląd. Funkcja factorint nie zawodzi przy faktoryzacji RSA1024 per se, po prostu nie mamy wystarczająco dużo czasu, aby pozwolić jej zakończyć pracę.

Pojęcie kosztu obliczeniowego, jako liczby operacji elementarnych wymaganych do wykonania obliczenia, ma być abstrakcyjnym odpowiednikiem czasu potrzebnego do implementacji obliczenia. Każda operacja elementarna wymaga pewnej ilości czasu do wykonania, a im więcej ich obliczenie potrzebuje, tym dłużej będzie trwać, przynajmniej ogólnie rzecz biorąc. W imię prostoty będziemy nadal dokonywać tego powiązania między kosztem obliczeniowym a czasem wymaganym do uruchomienia algorytmów.

Ale zauważmy, że rozmiar obwodu niekoniecznie odpowiada bezpośrednio temu, jak długo trwa jego wykonanie. Na przykład w naszym obwodzie logicznym obliczającym XOR dwóch bitów dwie bramki FANOUT mogłyby być wykonywane jednocześnie, podobnie jak dwie bramki NOT, a także dwie bramki AND. Innym sposobem pomiaru wydajności obwodów, który uwzględnia tę możliwość zrównoleglania, jest ich głębokość. Jest to minimalna liczba warstw bramek potrzebnych w obwodzie, gdzie bramki w każdej warstwie działają na różnych przewodach. Równoważnie, głębokość obwodu to maksymalna liczba bramek napotkanych na dowolnej ścieżce od przewodu wejściowego do przewodu wyjściowego. Na przykład dla powyższego obwodu głębokość wynosi 4.

Głębokość obwodu jest jednym ze sposobów sformalizowania czasu wykonania obliczeń równoległych. Jest to zaawansowany temat i istnieją bardzo wyrafinowane konstrukcje obwodów znane z minimalizacji głębokości wymaganej dla określonych obliczeń. Istnieją również fascynujące pytania bez odpowiedzi dotyczące głębokości obwodu. (Na przykład wiele pozostaje nieznanego na temat głębokości obwodu wymaganej do obliczania NWD.) Nie będziemy mieli zbyt wiele więcej do powiedzenia o głębokości obwodu w tej serii, poza uwzględnieniem kilku interesujących faktów dotyczących głębokości obwodu w miarę postępów, ale należy jasno przyznać, że zrównoleglanie jest potencjalnym źródłem przewagi obliczeniowej.

Przypisywanie kosztów różnym bramkom

Jedna ostatnia uwaga dotycząca rozmiaru obwodu i kosztu obliczeniowego jest taka, że można przypisywać różne koszty bramkom, zamiast postrzegać każdą bramkę jako wnoszącą równy wkład w całkowity koszt.

Na przykład, jak już wspomniano, bramki FANOUT są często postrzegane jako bezpłatne dla obwodów logicznych — co oznacza, że moglibyśmy zdecydować, że bramki FANOUT mają zerowy koszt. Jako kolejny przykład, gdy pracujemy w modelu zapytań i liczymy liczbę zapytań, jakie obwód wykonuje do funkcji wejściowej (w postaci czarnej skrzynki), faktycznie przypisujemy jednostkowy koszt bramkom zapytań i zerowy koszt innym bramkom, takim jak bramki Hadamard. Ostatnim przykładem jest to, że czasami przypisujemy różne koszty bramkom w zależności od tego, jak trudne są do zaimplementowania, co może się różnić w zależności od rozważanego sprzętu.

Chociaż wszystkie te opcje są rozsądne w różnych kontekstach, w tej lekcji dla uproszczenia pozostaniemy przy rozmiarze obwodu jako reprezentacji kosztu obliczeniowego.

Koszt jako funkcja długości wejścia

Interesuje nas przede wszystkim to, jak koszt obliczeniowy skaluje się wraz ze wzrostem rozmiaru danych wejściowych. Prowadzi nas to do reprezentowania kosztów algorytmów jako funkcji długości wejścia.

Rodziny obwodów

Dane wejściowe danego problemu obliczeniowego mogą mieć różną długość, potencjalnie stając się dowolnie duże. Z drugiej strony każdy obwód ma ustaloną liczbę bramek i przewodów. Z tego powodu, gdy myślimy o algorytmach w kategoriach obwodów, zazwyczaj potrzebujemy nieskończenie dużych rodzin obwodów, aby reprezentować algorytmy. Przez rodzinę obwodów rozumiemy sekwencję obwodów, które rosną pod względem rozmiaru, umożliwiając obsługę coraz większych danych wejściowych.

Wyobraźmy sobie na przykład, że mamy klasyczny algorytm faktoryzacji liczb całkowitych, taki jak ten używany przez factorint. Jak wszystkie klasyczne algorytmy, ten algorytm można zaimplementować przy użyciu obwodów Boole'a — ale aby to zrobić, będziemy potrzebować osobnego obwodu dla każdej możliwej długości wejścia. Gdybyśmy spojrzeli na wynikowe obwody dla różnych długości wejścia, zobaczylibyśmy, że ich rozmiary naturalnie rosną wraz ze wzrostem długości wejścia — odzwierciedlając fakt, że faktoryzacja 4-bitowych liczb całkowitych jest znacznie łatwiejsza i wymaga znacznie mniejszej liczby elementarnych operacji niż faktoryzacja na przykład 1024-bitowych liczb całkowitych.

Prowadzi nas to do reprezentowania kosztu obliczeniowego algorytmu za pomocą funkcji $t,$ zdefiniowanej tak, że $t(n)$ jest liczbą bramek w obwodzie implementującym algorytm dla $n$-bitowych danych wejściowych. W bardziej formalnych słowach, algorytm w modelu obwodów Boole'a jest opisany sekwencją obwodów $\{C_1, C_2, C_3,\ldots\},$ gdzie $C_n$ rozwiązuje dany problem dla $n$-bitowych danych wejściowych (lub, bardziej ogólnie, dla danych wejściowych, których rozmiar jest w jakiś sposób sparametryzowany przez $n$), a funkcja $t$ reprezentująca koszt tego algorytmu jest zdefiniowana jako

$$t(n) = \operatorname{size}(C_n).$$

W przypadku obwodów kwantowych sytuacja jest podobna — potrzebne są coraz większe obwody, aby obsłużyć coraz dłuższe ciągi wejściowe.

Przykład: dodawanie liczb całkowitych

Aby wyjaśnić to dalej, poświęćmy chwilę na rozważenie problemu dodawania liczb całkowitych, który jest znacznie prostszy niż faktoryzacja liczb całkowitych, a nawet obliczanie NWD.

Integer addition

Wejście: liczby całkowite $N$ i $M$
Wyjście: $N+M$

Jak moglibyśmy zaprojektować obwody Boole'a do rozwiązania tego problemu?

Dla uproszczenia ograniczmy naszą uwagę do przypadku, w którym zarówno $N,$ jak i $M$ są nieujemnymi liczbami całkowitymi reprezentowanymi przez $n$-bitowe ciągi w notacji binarnej. Dopuścimy dowolną liczbę wiodących zer w tych kodowaniach, tak aby

$$0\leq N,M\leq 2^n - 1.$$

Wyjście będzie $(n+1)$-bitowym ciągiem binarnym reprezentującym sumę, co jest maksymalną liczbą bitów potrzebnych do wyrażenia wyniku.

Zaczynamy od algorytmu — standardowego algorytmu dodawania reprezentacji binarnych — który jest analogiem w systemie o podstawie $2$ do sposobu, w jaki dodawania uczy się w szkołach podstawowych na całym świecie. Algorytm ten można zaimplementować za pomocą obwodów Boole'a w następujący sposób.

Zaczynając od najmniej znaczących bitów, możemy obliczyć ich XOR, aby wyznaczyć najmniej znaczący bit sumy. Następnie obliczamy carry bit, który jest AND dwóch najmniej znaczących bitów $N$ i $M.$ Czasami te dwie operacje razem są znane jako półsumator (half adder).

Używając obwodu XOR, który widzieliśmy już kilka razy, wraz z bramką AND i dwiema bramkami FANOUT, możemy zbudować półsumator z 10 bramek. Gdybyśmy z jakiegoś powodu zmienili zdanie i zdecydowali się włączyć bramki XOR do naszego zestawu elementarnych operacji, potrzebowalibyśmy 1 bramki AND, 1 bramki XOR i 2 bramek FANOUT, aby zbudować półsumator.

Przechodząc do bardziej znaczących bitów, możemy zastosować podobną procedurę, ale tym razem uwzględniając w naszych obliczeniach carry bit z każdej poprzedniej pozycji. Kaskadując dwa półsumatory i biorąc OR wytwarzanych przez nie carry bitów, możemy stworzyć coś, co nazywa się pełnym sumatorem (full adder).

Wymaga to łącznie 21 bramek: 2 bramek AND, 2 bramek XOR (z których każda wymaga 7 bramek do implementacji), jednej bramki OR i 4 bramek FANOUT.

Wreszcie, kaskadując pełne sumatory, otrzymujemy obwód Boole'a do dodawania nieujemnych liczb całkowitych. Na przykład następujący obwód oblicza sumę dwóch 4-bitowych liczb całkowitych.

Ogólnie wymaga to

$$21 (n-1) + 10 = 21 n - 11$$

bramek. Gdybyśmy zdecydowali się włączyć bramki XOR do naszego zestawu elementarnych operacji, potrzebowalibyśmy $2n-1$ bramek AND, $2n-1$ bramek XOR, $n-1$ bramek OR i $4n-2$ bramek FANOUT, co daje łącznie $9n-5$ bramek. Jeśli dodatkowo zdecydujemy się nie liczyć bramek FANOUT, daje to $5n-3$ bramek.

Notacja asymptotyczna

Z jednej strony dobrze jest dokładnie wiedzieć, ile bramek jest potrzebnych do wykonania różnych obliczeń, jak w powyższym przykładzie dodawania liczb całkowitych. Te szczegóły są ważne przy faktycznym budowaniu obwodów.

Z drugiej strony, jeśli przeprowadzimy analizy na tym poziomie szczegółowości dla wszystkich obliczeń, którymi jesteśmy zainteresowani, w tym dla zadań znacznie bardziej skomplikowanych niż dodawanie, bardzo szybko zostaniemy pogrzebani pod szczegółami. Aby zachować umiarkowanie i celowo pominąć szczegóły drugorzędnej wagi, zazwyczaj stosujemy notację O-duże (Big-O) przy analizie algorytmów. Dzięki tej notacji możemy wyrazić rząd, w jakim rosną funkcje.

Formalnie rzecz biorąc, jeśli mamy dwie funkcje $g(n)$ i $h(n),$ piszemy, że $g(n) = O(h(n)),$ jeśli istnieje dodatnia liczba rzeczywista $c > 0$ i dodatnia liczba całkowita $n_0$ taka, że

$$g(n) \leq c\cdot h(n)$$

dla wszystkich $n \geq n_0.$ Zazwyczaj $h(n)$ jest wybierane jako możliwie najprostsze wyrażenie, tak aby notacja mogła ujawnić zachowanie graniczne funkcji w prostych kategoriach. Na przykład $17 n^3 - 257 n^2 + 65537 = O(n^3).$

Notację tę można dość prosto rozszerzyć na funkcje z wieloma argumentami. Na przykład, jeśli mamy dwie funkcje $g(n,m)$ i $h(n,m)$ zdefiniowane na dodatnich liczbach całkowitych $n$ i $m,$ piszemy, że $g(n,m) = O(h(n,m)),$ jeśli istnieje dodatnia liczba rzeczywista $c > 0$ i dodatnia liczba całkowita $k_0$ taka, że

$$g(n,m) \leq c\cdot h(n,m)$$

zawsze, gdy $n+m \geq k_0.$

Łącząc tę notację z przykładem dodawania nieujemnych liczb całkowitych, wnioskujemy, że istnieje rodzina obwodów Boole'a $\{C_1, C_2,\ldots,\},$ gdzie $C_n$ dodaje dwie $n$-bitowe nieujemne liczby całkowite, taka, że $\operatorname{size}(C_n) = O(n).$ Ujawnia to najbardziej istotną cechę tego, jak koszt dodawania skaluje się z rozmiarem wejścia: skaluje się liniowo.

Zauważmy również, że nie zależy to od konkretnego szczegółu, czy uznajemy bramki XOR za mające koszt jednostkowy, czy koszt $7.$ Ogólnie rzecz biorąc, użycie notacji O-duże pozwala nam formułować stwierdzenia dotyczące kosztów obliczeniowych, które nie są wrażliwe na tak niskopoziomowe szczegóły.

Więcej przykładów

Oto kilka kolejnych przykładów problemów z obliczeniowej teorii liczb, zaczynając od mnożenia.

Integer multiplication

Wejście: liczby całkowite $N$ i $M$
Wyjście: $NM$

Tworzenie obwodów boolowskich dla tego problemu jest trudniejsze niż tworzenie obwodów do dodawania — ale rozważając standardowy algorytm mnożenia, możemy skonstruować obwody o rozmiarze $O(n^2)$ dla tego problemu (zakładając, że zarówno $N$, jak i $M$ są reprezentowane przez $n$-bitowe reprezentacje binarne). Ogólniej, jeśli $N$ ma $n$ bitów, a $M$ ma $m$ bitów, istnieją obwody boolowskie o rozmiarze $O(nm)$ do mnożenia $N$ i $M.$

Istnieją w istocie inne sposoby mnożenia, które lepiej się skalują. Na przykład algorytm mnożenia Schönhagego-Strassena może zostać użyty do stworzenia obwodów boolowskich do mnożenia dwóch $n$-bitowych liczb całkowitych kosztem $O(n \operatorname{lg}(n) \operatorname{lg}(\operatorname{lg}(n))).$ Zawiłość tej metody powoduje jednak duży narzut, przez co jest ona praktyczna tylko dla liczb mających dziesiątki tysięcy bitów.

Innym podstawowym problemem jest dzielenie, które interpretujemy jako obliczenie zarówno ilorazu, jak i reszty z danego dzielnika oraz dzielnej będących liczbami całkowitymi.

Integer division

Wejście: liczby całkowite $N$ i $M\neq0$
Wyjście: liczby całkowite $q$ i $r$ spełniające $0\leq r < |M|$ oraz $N = q M + r$

Koszt dzielenia liczb całkowitych jest podobny do mnożenia: jeśli $N$ ma $n$ bitów, a $M$ ma $m$ bitów, istnieją obwody boolowskie o rozmiarze $O(nm)$ do rozwiązania tego problemu. I podobnie jak przy mnożeniu, znane są asymptotycznie lepsze metody.

Możemy teraz porównać znane algorytmy obliczania NWD z tymi dla dodawania i mnożenia. Algorytm Euklidesa do obliczania NWD $n$-bitowej liczby $N$ i $m$-bitowej liczby $M$ wymaga obwodów boolowskich o rozmiarze $O(nm),$ podobnie jak standardowe algorytmy mnożenia i dzielenia. Również podobnie jak dla mnożenia i dzielenia, istnieją asymptotycznie szybsze algorytmy NWD — w tym takie, które wymagają $O(n(\operatorname{lg}(n))^2 \operatorname{lg}(\operatorname{lg}(n)))$ elementarnych operacji do obliczenia NWD dwóch $n$-bitowych liczb.

Nieco kosztowniejszym obliczeniem pojawiającym się w teorii liczb jest potęgowanie modularne.

Integer modular exponentiation

Wejście: liczby całkowite $N,$ $K$ i $M$ z $K\geq 0$ i $M\geq 1$
Wyjście: $N^K \hspace{1mm} (\text{mod }M)$

Przez $N^K\hspace{1mm} (\text{mod }M)$ rozumiemy resztę z dzielenia $N^K$ przez $M$, czyli jednoznaczną liczbę całkowitą $r$ spełniającą $0\leq r < M$ oraz $N^K = q M + r$ dla pewnej liczby całkowitej $q.$

Jeśli $N$ ma $n$ bitów, $M$ ma $m$ bitów, a $K$ ma $k$ bitów, problem ten można rozwiązać za pomocą obwodów boolowskich o rozmiarze $O(k m^2 + nm).$ Nie jest to wcale oczywiste. Rozwiązanie nie polega na pierwszym obliczeniu $N^K$, a następnie wzięciu reszty, co wymagałoby użycia wykładniczo wielu bitów tylko do przechowania liczby $N^K.$ Zamiast tego możemy użyć algorytmu potęgowania (znanego również jako metoda binarna i wielokrotne kwadraty), który wykorzystuje binarną reprezentację $K$ do wykonania całego obliczenia modulo $M.$ Zakładając, że $N,$ $M$ i $K$ są wszystkie liczbami $n$-bitowymi, otrzymujemy algorytm $O(n^3)$ — czyli algorytm czasu sześciennego. I po raz kolejny, istnieją znane algorytmy, które są bardziej skomplikowane, ale asymptotycznie szybsze.

Koszt faktoryzacji liczb całkowitych

W przeciwieństwie do omówionych właśnie algorytmów, znane algorytmy faktoryzacji liczb całkowitych są znacznie kosztowniejsze — czego możemy się spodziewać po wcześniejszej dyskusji w tej lekcji.

Jednym z prostych podejść do faktoryzacji jest dzielenie próbne, gdzie algorytm przeszukuje listę $2,\ldots,\sqrt{N}$, aby znaleźć dzielnik pierwszy liczby wejściowej $N.$ Wymaga to $O(2^{n/2})$ iteracji w najgorszym przypadku, gdy $N$ jest liczbą $n$-bitową. Każda iteracja wymaga dzielenia próbnego, co oznacza $O(n^2)$ elementarnych operacji na każdą iterację (przy użyciu standardowego algorytmu dzielenia liczb całkowitych). Otrzymujemy obwody o rozmiarze $O(n^2 2^{n/2}),$ co jest wykładnicze względem rozmiaru wejścia $n.$

Istnieją algorytmy faktoryzacji liczb całkowitych o lepszym skalowaniu. Na przykład wspomniane wcześniej sito ciał liczbowych, które jest algorytmem wykorzystującym losowość, wedle powszechnego przekonania (ale nie rygorystycznego dowodu) wymaga

$$2^{O(n^{1/3} (\operatorname{lg}(n))^{2/3})}$$

elementarnych operacji do sfaktoryzowania $n$-bitowych liczb całkowitych z wysokim prawdopodobieństwem. Choć jest bardzo istotne, że $n$ jest podniesione do potęgi $1/3$ w wykładniku tego wyrażenia, sam fakt, że pojawia się ono w wykładniku, jest nadal problemem powodującym słabe skalowanie — i częściowo wyjaśnia, dlaczego RSA1024 pozostaje poza zakresem stosowalności tej metody.

Koszt wielomianowy a wykładniczy

Klasyczne algorytmy dodawania, mnożenia, dzielenia liczb całkowitych oraz obliczania największych wspólnych dzielników pozwalają nam rozwiązać te problemy w mgnieniu oka dla wejść o tysiącach bitów. Dodawanie ma koszt liniowy, podczas gdy pozostałe trzy problemy mają koszt kwadratowy (lub podkwadratowy przy użyciu asymptotycznie szybkich algorytmów). Potęgowanie modularne jest droższe, ale nadal można je wykonać dość efektywnie, z kosztem sześciennym (lub podsześciennym przy użyciu asymptotycznie szybkich algorytmów).

Są to wszystko przykłady algorytmów o koszcie wielomianowym, co oznacza, że mają koszt $O(n^c)$ dla pewnego ustalonego stałego $c > 0.$ W przybliżeniu, jako pierwsze oszacowanie, algorytmy o koszcie wielomianowym są abstrakcyjnie postrzegane jako reprezentujące algorytmy efektywne.

W przeciwieństwie do tego, znane klasyczne algorytmy faktoryzacji liczb całkowitych mają koszt wykładniczy. Czasami koszt sita ciał liczbowych określa się jako subwykładniczy, ponieważ $n$ jest podniesione do potęgi $1/3$ w wykładniku, ale w teorii złożoności bardziej typowe jest zarezerwowanie tego terminu dla algorytmów, których koszt wynosi

$$O\bigl(2^{n^{\varepsilon}}\bigr)$$

dla każdego $\varepsilon > 0.$ Tak zwane problemy NP-zupełne to klasa problemów, o których nie wiadomo (i powszechnie się przypuszcza, że nie mają) algorytmów o koszcie wielomianowym. Obwodowe sformułowanie hipotezy czasu wykładniczego postuluje coś jeszcze silniejszego, a mianowicie, że żaden problem NP-zupełny nie może mieć algorytmu o koszcie subwykładniczym.

Skojarzenie algorytmów o koszcie wielomianowym z algorytmami efektywnymi musi być rozumiane jako luźna abstrakcja. Oczywiście, jeśli koszt algorytmu skaluje się jak $n^{1000}$ lub $n^{1000000}$ dla wejść o rozmiarze $n,$ to nadużyciem byłoby opisanie takiego algorytmu jako efektywnego. Jednak nawet algorytm o koszcie skalującym się jak $n^{1000000}$ musi robić coś sprytnego, aby uniknąć kosztu wykładniczego, co jest zasadniczo tym, czego oczekujemy od algorytmów opartych w jakiś sposób na „brutalnej sile" lub „wyczerpującym przeszukiwaniu". Nawet wyrafinowane udoskonalenia sita ciał liczbowych nie potrafią, na przykład, uniknąć tego wykładniczego skalowania kosztu. Z drugiej strony, algorytmy o koszcie wielomianowym potrafią w jakiś sposób wykorzystać strukturę problemu, aby uniknąć skalowania wykładniczego.

W praktyce zidentyfikowanie algorytmu o koszcie wielomianowym dla danego problemu jest jedynie pierwszym krokiem w kierunku rzeczywistej efektywności. Dzięki algorytmicznym udoskonaleniom algorytmy o koszcie wielomianowym z dużymi wykładnikami mogą czasem zostać dramatycznie ulepszone, obniżając koszt do bardziej „rozsądnego" skalowania wielomianowego. Czasami rzeczy stają się łatwiejsze, gdy wiadomo, że są możliwe — zatem zidentyfikowanie algorytmu o koszcie wielomianowym dla problemu może również mieć efekt inspirujący do tworzenia nowych, jeszcze bardziej efektywnych algorytmów.

Rozważając przewagi obliczeń kwantowych nad klasycznymi, nasz wzrok zwykle kieruje się najpierw ku przewagom wykładniczym, lub przynajmniej superwielomianowym — w ideale do znalezienia kwantowych algorytmów o koszcie wielomianowym dla problemów, dla których nie są znane klasyczne algorytmy o koszcie wielomianowym. Teoretyczne przewagi tego rzędu mają największe szanse prowadzić do rzeczywistych przewag praktycznych — ale zidentyfikowanie takich przewag jest niezwykle trudnym wyzwaniem. Obecnie znanych jest tylko kilka przykładów, ale poszukiwania trwają.

Przewagi wielomianowe (ale nie superwielomianowe) w koszcie obliczeniowym kwantowym nad klasycznym są również interesujące i nie powinny być lekceważone — ale biorąc pod uwagę obecną przepaść między technologią obliczeń kwantowych i klasycznych, wydają się obecnie znacznie mniej przekonujące. Pewnego dnia mogą jednak stać się znaczące. Na przykład algorytm Grovera, omawiany w późniejszej lekcji, oferuje kwadratową przewagę kwantową nad klasyczną w tak zwanym przeszukiwaniu niestrukturalnym i ma potencjał do szerokich zastosowań.

Ukryty koszt obliczeń obwodowych

Jest jeszcze jedna kwestia warta wspomnienia, choć nie będziemy się nią dalej zajmować w tym kursie. Istnieje „ukryty" koszt obliczeniowy, gdy pracujemy z obwodami, i dotyczy on specyfikacji samych obwodów. Gdy wejścia stają się coraz dłuższe, wymagane są coraz większe obwody — ale musimy w jakiś sposób zdobyć opisy tych obwodów, jeśli mamy je zaimplementować.

W przypadku wszystkich przykładów, które omawialiśmy lub omówimy w kolejnych lekcjach, istnieje leżący u podstaw algorytm, z którego wyprowadzane są obwody. Zazwyczaj obwody w rodzinie podążają za pewnym podstawowym wzorcem, który łatwo ekstrapolować do coraz większych wejść, takim jak kaskadowanie pełnych sumatorów w celu utworzenia obwodów boolowskich do dodawania lub wykonywanie warstw bramek Hadamarda i innych bramek w pewnym łatwym do opisania wzorcu.

Ale co się dzieje, jeśli z samymi wzorcami obwodów związane są zaporowe koszty obliczeniowe? Na przykład opis każdego członka $C_n$ w rodzinie obwodów mógłby w zasadzie być wyznaczony przez pewną niezwykle trudną do obliczenia funkcję $n.$

Odpowiedź brzmi, że jest to rzeczywiście problem — i dlatego musimy nałożyć dodatkowe ograniczenia na rodziny obwodów poza posiadaniem kosztu wielomianowego, aby naprawdę reprezentowały efektywne algorytmy. Własność jednorodności dla obwodów czyni to, postulując, że w różnych precyzyjnych sformułowaniach uzyskanie opisu każdego obwodu w rodzinie musi być obliczeniowo łatwe.