Model obliczeniowy zapytań

Kiedy modelujemy obliczenia w kategoriach matematycznych, mamy zwykle na myśli rodzaj procesu przedstawionego na poniższym rysunku: informacja jest dostarczana jako wejście, odbywa się obliczenie i produkowane jest wyjście.

Choć prawdą jest, że komputery, których dziś używamy, nieustannie odbierają dane wejściowe i produkują wyjście – wchodząc w interakcję zarówno z nami, jak i z innymi komputerami w sposób nieodzwierciedlony przez rysunek – intencją nie jest tu przedstawienie ciągłego działania komputerów. Chodzi raczej o stworzenie prostej abstrakcji obliczeń, skupiającej się na izolowanych zadaniach obliczeniowych. Na przykład wejście może kodować liczbę, wektor, macierz, graf, opis cząsteczki lub coś bardziej złożonego, podczas gdy wyjście koduje rozwiązanie rozważanego zadania obliczeniowego.

Kluczową kwestią jest to, że wejście jest dostarczane do obliczenia – zwykle w postaci ciągu binarnego – i żadna jego część nie jest ukryta.

Opis modelu

W modelu obliczeniowym zapytań całe wejście nie jest dostarczane do obliczenia tak jak w bardziej standardowym modelu sugerowanym powyżej. Zamiast tego wejście jest udostępniane w postaci funkcji, do której obliczenie uzyskuje dostęp, wykonując zapytania. Alternatywnie możemy postrzegać obliczenia w modelu zapytań jako mające dostęp swobodny do bitów (lub segmentów bitów) wejścia.

W kontekście modelu zapytań często mówimy, że wejście jest dostarczane przez oracle lub czarną skrzynkę. Oba terminy sugerują, że pełny opis wejścia jest ukryty przed obliczeniem, a jedynym sposobem uzyskania do niego dostępu jest zadawanie pytań. To jakbyśmy konsultowali się z Wyrocznią w Delfach w sprawie wejścia: nie powie nam wszystkiego, co wie, odpowiada jedynie na konkretne pytania. Termin czarna skrzynka nabiera sensu zwłaszcza wtedy, gdy myślimy o wejściu jako reprezentowanym przez funkcję; nie możemy zajrzeć do środka funkcji i zrozumieć, jak działa – możemy ją jedynie obliczać dla argumentów, które sami wybieramy.

Będziemy w tej lekcji pracować wyłącznie z ciągami binarnymi, a nie z ciągami zawierającymi różne symbole, dlatego zapiszmy $\Sigma = \{0,1\}$ i od tej pory będziemy używać tej notacji dla wygody, odnosząc się do alfabetu binarnego. Będziemy rozważać różne problemy obliczeniowe – kilka prostych przykładów zostanie opisanych wkrótce – ale dla wszystkich nich wejście będzie reprezentowane przez funkcję postaci

$$f:\Sigma^n \rightarrow \Sigma^m$$

dla dwóch dodatnich liczb całkowitych $n$ i $m.$ Oczywiście moglibyśmy wybrać inną nazwę zamiast $f,$ ale przez całą lekcję będziemy trzymać się $f.$

Powiedzieć, że obliczenie wykonuje zapytanie, oznacza, że wybierany jest pewien ciąg $x \in \Sigma^n,$ a następnie ciąg $f(x)\in\Sigma^m$ jest udostępniany obliczeniu przez oracle. Dokładny sposób, w jaki to działa dla algorytmów kwantowych, zostanie omówiony wkrótce – musimy upewnić się, że jest to możliwe do wykonania za pomocą unitarnej operacji kwantowej pozwalającej na wykonywanie zapytań w superpozycji – ale na razie możemy myśleć o tym intuicyjnie na wysokim poziomie abstrakcji.

Na koniec, sposób, w jaki będziemy mierzyć efektywność algorytmów zapytań, jest prosty: będziemy liczyć liczbę zapytań, których wymagają. Jest to związane z czasem potrzebnym do wykonania obliczeń, ale nie jest dokładnie tym samym, ponieważ pomijamy czas operacji innych niż zapytania, a ponadto traktujemy zapytania tak, jakby każde z nich miało koszt jednostkowy. Możemy uwzględnić operacje inne niż zapytania, jeśli chcemy (i czasem się to robi), ale ograniczenie uwagi wyłącznie do liczby zapytań pomaga zachować prostotę.

Przykłady problemów zapytań

Oto kilka prostych przykładów problemów zapytań.

• OR. Funkcja wejściowa ma postać $f:\Sigma^n \rightarrow \Sigma$ (czyli $m=1$ dla tego problemu). Zadanie polega na zwróceniu $1,$ jeśli istnieje ciąg $x\in\Sigma^n,$ dla którego $f(x) = 1,$ i na zwróceniu $0,$ jeśli taki ciąg nie istnieje. Jeśli myślimy o funkcji $f$ jako o reprezentacji ciągu $2^n$ bitów, do których mamy dostęp swobodny, problem sprowadza się do obliczenia sumy logicznej OR tych bitów.

• Parzystość. Funkcja wejściowa znowu ma postać $f:\Sigma^n \rightarrow \Sigma.$ Zadanie polega na ustaleniu, czy liczba ciągów $x\in\Sigma^n,$ dla których $f(x) = 1,$ jest parzysta czy nieparzysta. Dokładniej mówiąc, wymaganym wyjściem jest $0,$ jeśli zbiór $\{x\in\Sigma^n : f(x) = 1\}$ ma parzystą liczbę elementów, i $1,$ jeśli ma nieparzystą liczbę elementów. Jeśli myślimy o funkcji $f$ jako o reprezentacji ciągu $2^n$ bitów, do których mamy dostęp swobodny, problem sprowadza się do obliczenia parzystości (czyli sumy modulo 2) tych bitów.

• Minimum. Funkcja wejściowa ma postać $f:\Sigma^n \rightarrow \Sigma^m$ dla dowolnych dodatnich liczb całkowitych $n$ i $m.$ Wymaganym wyjściem jest ciąg $y \in \{f(x) : x\in\Sigma^n\},$ który pojawia się jako pierwszy w leksykograficznym (czyli słownikowym) porządku $\Sigma^m.$ Jeśli myślimy o funkcji $f$ jako o reprezentacji ciągu $2^n$ liczb całkowitych zakodowanych jako ciągi długości $m$ w notacji binarnej, do których mamy dostęp swobodny, problem sprowadza się do znalezienia minimum tych liczb całkowitych.

Rozważamy też problemy zapytań, w których mamy obietnicę dotyczącą wejścia. Oznacza to, że dysponujemy pewnego rodzaju gwarancją dotyczącą wejścia i nie odpowiadamy za to, co się dzieje, gdy ta gwarancja nie jest spełniona. Innym sposobem opisania tego rodzaju problemu jest stwierdzenie, że niektóre funkcje wejściowe (te, dla których obietnica nie jest spełniona) są traktowane jako wejścia „nie obchodzi nas". Wobec algorytmów, które otrzymują wejścia „nie obchodzi nas", nie są stawiane żadne wymagania.

Oto jeden przykład problemu z obietnicą:

• Unikalne wyszukiwanie. Funkcja wejściowa ma postać $f:\Sigma^n \rightarrow \Sigma,$ i obiecane jest, że istnieje dokładnie jeden ciąg $z\in\Sigma^n,$ dla którego $f(z) = 1,$ przy czym $f(x) = 0$ dla wszystkich ciągów $x\neq z.$ Zadanie polega na znalezieniu tego unikalnego ciągu $z.$

Wszystkie cztery opisane właśnie przykłady są naturalne w tym sensie, że są łatwe do opisania i można sobie wyobrazić różnorodne sytuacje lub konteksty, w których mogłyby się pojawić.

W odróżnieniu od nich, niektóre problemy zapytań nie są w ogóle „naturalne" w ten sposób. W rzeczywistości w badaniu modelu zapytań czasami tworzymy bardzo skomplikowane i wysoce sztuczne problemy, co do których trudno sobie wyobrazić, żeby ktokolwiek chciał je kiedykolwiek rozwiązywać w praktyce. Nie oznacza to jednak, że problemy te nie są interesujące! To, co początkowo może wydawać się sztuczne lub nienaturalne, może dostarczyć niespodziewanych wskazówek lub zainspirować nowe pomysły. Kwantowy algorytm Shora do faktoryzacji, zainspirowany algorytmem Simona, jest świetnym przykładem. Ważną częścią badania modelu zapytań jest też szukanie skrajnych przypadków, które mogą rzucić światło zarówno na potencjalne zalety, jak i na ograniczenia obliczeń kwantowych.

Gate'y zapytań

Kiedy opisujemy obliczenia za pomocą Circuit, zapytania są wykonywane przez specjalne Gate'y zwane gate'ami zapytań.

Najprostszym sposobem zdefiniowania gate'ów zapytań dla klasycznych Circuit Boolowskich jest po prostu zezwolenie im na bezpośrednie obliczanie funkcji wejściowej $f,$ jak sugeruje poniższy rysunek.

Kiedy tworzony jest Circuit Boolowski dla problemu zapytania, funkcja wejściowa $f$ jest dostępna przez te gate'y, a liczba zapytań wykonywanych przez Circuit to po prostu liczba gate'ów zapytań pojawiających się w Circuit. Przewody wejściowe samego Circuit Boolowskiego są inicjalizowane do stałych wartości, które należy traktować jako część algorytmu (w odróżnieniu od bycia wejściami do problemu).

Na przykład oto Circuit Boolowski z klasycznymi gate'ami zapytań, który rozwiązuje opisany powyżej problem parzystości dla funkcji postaci $f:\Sigma\rightarrow\Sigma$:

Ten algorytm wykonuje dwa zapytania, ponieważ zawiera dwa gate'y zapytań. Działa w następujący sposób: funkcja $f$ jest odpytywana dla dwóch możliwych wejść, $0$ i $1,$ a wyniki są wprowadzane do Circuit Boolowskiego obliczającego XOR. (Ten konkretny Circuit pojawił się jako przykład Circuit Boolowskiego w lekcji Kwantowe Circuit kursu Podstawy informacji kwantowej.)

W przypadku Circuit kwantowych ta definicja gate'ów zapytań nie działa, ponieważ gate'y te byłyby nieunitarne dla niektórych wyborów funkcji $f.$ Dlatego zamiast tego definiujemy unitarne gate'y zapytań, które działają na standardowych stanach bazowych zgodnie z tym rysunkiem:

Tutaj zakładamy, że $x\in\Sigma^n$ i $y\in\Sigma^m$ są dowolnymi ciągami. Notacja $y\oplus f(x)$ odnosi się do bitowego alternatywnego sumy wyłączającej (XOR) dwóch ciągów, które mają długość $m$ w tym przypadku. Na przykład $001 \oplus 101 = 100.$

Mówiąc intuicyjnie, to, co robi gate $U_f$ (dla dowolnie wybranej funkcji $f$), to odwzorowywanie wejściowego ciągu $x$ na wyjście i dodawanie wartości funkcji $f(x)$ poprzez XOR do dolnego ciągu wejściowego $y,$ co jest operacją unitarną dla każdego wyboru funkcji $f.$ W rzeczywistości jest to operacja deterministyczna, będąca swoją własną odwrotnością. Wynika z tego, że jako macierz $U_f$ jest zawsze macierzą permutacji, czyli macierzą z pojedynczą $1$ w każdym wierszu i każdej kolumnie, przy czym wszystkie pozostałe elementy wynoszą $0.$ Zastosowanie macierzy permutacji do wektora po prostu przestawia elementy tego wektora (stąd termin macierz permutacji) i dlatego nie zmienia normy euklidesowej tego wektora – co ujawnia, że macierze permutacji są zawsze unitarne.

Warto podkreślić, że kiedy analizujemy algorytmy zapytań, po prostu licząc liczbę zapytań wykonywanych przez algorytm, całkowicie ignorujemy trudność fizycznej konstrukcji gate'ów zapytań – zarówno w klasycznej, jak i kwantowej wersji, którą właśnie opisaliśmy. Mówiąc intuicyjnie, budowa gate'ów zapytań jest częścią przygotowania wejścia, a nie częścią znajdowania rozwiązania.

Może się to wydawać nieuzasadnione, ale musimy pamiętać, że nie staramy się opisywać praktycznych obliczeń ani w pełni rozliczać wymaganych zasobów. Zamiast tego definiujemy model teoretyczny, który pomaga rzucić światło na potencjalne zalety obliczeń kwantowych. Więcej do powiedzenia na ten temat będziemy mieli w następnej lekcji, gdy skupimy uwagę na bardziej standardowym modelu obliczeniowym, w którym wejścia są dostarczane do Circuit wprost jako ciągi binarne.