Klasyczne obliczenia na komputerach kwantowych

Teraz skupimy się na implementowaniu klasycznych algorytmów na komputerach kwantowych. Zobaczymy, że każde obliczenie, które można wykonać za pomocą klasycznego obwodu boolowskiego, może być również wykonane przez obwód kwantowy o podobnym asymptotycznym koszcie obliczeniowym. Co więcej, można to zrobić w „czysty" sposób, który zostanie wkrótce opisany — jest to ważny wymóg przy stosowaniu tych obliczeń jako podprogramów wewnątrz większych obliczeń kwantowych.

Symulowanie obwodów boolowskich za pomocą obwodów kwantowych

Obwody boolowskie składają się z bramek AND, OR, NOT i FANOUT. Aby symulować obwody boolowskie za pomocą obwodów kwantowych, zaczniemy od pokazania, jak każdą z tych czterech bramek można zasymulować przez bramki kwantowe. Gdy to zostanie zrobione, zamiana danego obwodu boolowskiego na obwód kwantowy jest prostą kwestią symulowania jednej bramki na raz. Do tego celu potrzebujemy jedynie bramek NOT, kontrolowanych-NOT oraz Toffoli — wszystkie są operacjami deterministycznymi, a zarazem unitarnymi.

Bramki Toffoli

Bramki Toffoli można alternatywnie opisać jako bramki kontrolowane-kontrolowane-NOT, których działanie na stanach bazy standardowej przedstawia poniższy rysunek.

Pamiętając, że stosujemy konwencję kolejności Qiskit, w której kubity są uporządkowane rosnąco według znaczenia od góry do dołu, macierzowa reprezentacja tej bramki jest następująca.

$$\begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \end{pmatrix}$$

Innym sposobem myślenia o bramkach Toffoli jest traktowanie ich jako bramek zapytaniowych dla funkcji AND — w tym sensie, że realizują wzorzec, który widzieliśmy w poprzedniej lekcji dla unitarnych implementacji bramek zapytaniowych dowolnych funkcji o wejściach i wyjściach będących ciągami binarnymi.

Bramki Toffoli nie są zawarte w domyślnym zestawie bramek omówionym wcześniej w tej lekcji, ale możliwe jest zbudowanie bramki Toffoli z bramek $H,$ $T,$ $T^{\dagger}$ i CNOT w następujący sposób.

Symulowanie bramek boolowskich za pomocą Toffoli, kontrolowanych-NOT i NOT

Pojedyncza bramka Toffoli, użyta w połączeniu z kilkoma bramkami NOT, może zaimplementować bramkę AND i OR, a bramki FANOUT można łatwo zaimplementować przy użyciu bramek CNOT, co sugerują poniższe diagramy.

We wszystkich trzech przypadkach kubity, na które działają bramki AND, OR i FANOUT, wchodzą z lewej strony jako wejścia, a dla każdej z nich potrzebujemy jeszcze jednego kubitu przestrzeni roboczej zainicjalizowanego do stanu zero. Te kubity przestrzeni roboczej są pokazane wewnątrz prostokątów reprezentujących implementacje bramek, co sugeruje, że są nowe, a zatem stanowią część kosztu tych implementacji.

W przypadku bramek AND i OR mamy również dwa nadmiarowe kubity, poza kubitem wyjściowym. Na przykład wewnątrz prostokąta na diagramie reprezentującego symulację bramki AND, dwa górne kubity pozostają w stanach $\vert a\rangle$ i $\vert b\rangle.$ Kubity te są pokazane jako pozostające wewnątrz prostokątów, ponieważ nie są już potrzebne i nie są częścią wyjścia. Na razie można je zignorować, choć wkrótce do nich wrócimy.

Pozostała bramka boolowska, NOT, jest zawarta w naszym domyślnym zestawie bramek kwantowych, więc nie potrzebujemy dla niej symulacji.

Symulowanie obwodów boolowskich bramka po bramce

Załóżmy teraz, że mamy zwykły obwód boolowski o nazwie $C,$ złożony z bramek AND, OR, NOT i FANOUT, mający $n$ bitów wejściowych i $m$ bitów wyjściowych. Niech $t = \operatorname{size}(C)$ będzie liczbą bramek w $C,$ a funkcję obliczaną przez $C$ nazwijmy $f$ — przyjmuje ona postać

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

dla $\Sigma = \{0,1\}.$

Teraz zastanówmy się, co się dzieje, gdy przechodzimy kolejno przez bramki AND, OR i FANOUT obwodu $C,$ zastępując każdą z nich odpowiednią symulacją opisaną powyżej, w tym dodając wymagane kubity przestrzeni roboczej. Nazwijmy wynikowy obwód $R$ i uporządkujmy kubity $R$ tak, aby $n$ bitów wejściowych $C$ odpowiadało górnym $n$ kubitom $R,$ a kubity przestrzeni roboczej znajdowały się na dole.

Tutaj $k$ to liczba wymaganych kubitów przestrzeni roboczej — po jednym dla każdej bramki AND, OR i FANOUT obwodu $C$ — a $g$ to funkcja postaci $g:\Sigma^n \rightarrow \Sigma^{n+k-m}$ opisująca stany nadmiarowych kubitów tworzonych przez symulacje bramek po uruchomieniu $R$. Na rysunku kubity odpowiadające wyjściu $f(x)$ znajdują się na górze, a pozostałe, nadmiarowe kubity przechowujące $g(x)$ — na dole. Możemy to wymusić, jeśli chcemy, poprzez przestawienie kubitów za pomocą bramek SWAP, które można zaimplementować przy użyciu trzech bramek CNOT w następujący sposób:

Jak zobaczymy w następnej sekcji, przestawianie kubitów wyjściowych w ten sposób nie jest tak naprawdę konieczne, ale wystarczająco łatwe do wykonania, jeśli zdecydujemy się na to.

Funkcja $g$ opisująca klasyczne stany nadmiarowych kubitów jest wyznaczona przez obwód $C,$ ale w zasadzie nie musimy się nią zbytnio przejmować; nie interesuje nas konkretny stan tych kubitów po zakończeniu obliczeń. Litera $g$ następuje po $f,$ więc jest rozsądną nazwą dla tej funkcji z tego powodu, ale jest lepszy powód, żeby wybrać nazwę $g$ — jest skrótem od garbage (ang. śmieci).

Sprzątanie śmieci

Jeśli naszym jedynym celem jest obliczenie funkcji $f$ wyliczanej przez dany obwód boolowski $C$ za pomocą obwodu kwantowego, nie musimy iść dalej niż symulacja bramka po bramce opisana powyżej. Oznacza to, że oprócz wyjścia funkcji, zostanie nam sporo śmieci.

Jednak to nie wystarczy, jeśli chcemy wykonywać klasyczne obliczenia jako podprogramy w ramach większych obliczeń kwantowych, ponieważ te nadmiarowe kubity będą powodować problemy. Zjawisko interferencji ma kluczowe znaczenie dla algorytmów kwantowych, a nadmiarowe kubity mogą niszczyć wzorce interferencji niezbędne do prawidłowego działania algorytmów kwantowych.

Na szczęście nie jest trudno posprzątać te śmieci. Kluczem jest skorzystanie z faktu, że ponieważ $R$ jest obwodem kwantowym, możemy uruchomić go w odwrotnej kolejności — po prostu zastępując każdą bramkę jej odwrotnością i stosując je w odwrotnej kolejności, uzyskując tym samym obwód kwantowy dla operacji $R^{\dagger}.$ Bramki Toffoli, CNOT i NOT są w rzeczywistości swoimi własnymi odwrotnościami, więc uruchomienie $R$ w odwrotnej kolejności sprowadza się do zastosowania bramek w odwrotnej kolejności — ale ogólnie każdy obwód kwantowy można odwrócić w sposób właśnie opisany.

Konkretnie możemy dodać $m$ kolejnych kubitów (przypominając, że funkcja $f$ ma $m$ bitów wyjściowych), użyć bramek CNOT do skopiowania wyjścia $R$ na te kubity, a następnie odwrócić $R,$ aby posprzątać śmieci. Poniższy rysunek ilustruje wynikowy obwód i opisuje jego działanie na stanach bazy standardowej.

Jeśli obudujemy cały obwód w prostokąt i nazwiemy go $Q,$ wygląda to następująco:

Przy założeniu, że $C$ ma $t$ bramek, obwód $Q$ będzie miał $O(t)$ bramek.

Jeśli pominiemy $k$ dodatkowych kubitów przestrzeni roboczej, otrzymujemy obwód $Q,$ który działa dokładnie jak bramka zapytaniowa dla funkcji $f.$ Jeśli chcemy po prostu obliczyć funkcję $f$ dla pewnego ciągu $x,$ możemy ustawić $y = 0^m$ i wynikowa wartość $f(x)$ pojawi się na dolnych $m$ kubitach — lub możemy podać inny stan dla dolnych $m$ kubitów, jeśli chcemy (być może, żeby skorzystać z efektu phase kickback, jak w algorytmie Deutscha lub Deutscha-Jozsy).

Oznacza to, że dla dowolnego algorytmu zapytaniowego, jeśli mamy obwód boolowski obliczający funkcję wejściową, możemy zastąpić każdą bramkę zapytaniową jej implementacją w postaci obwodu — i algorytm zapytaniowy będzie działał poprawnie.

Zauważ, że kubity przestrzeni roboczej są potrzebne do prawidłowego działania tego procesu, ale po wykonaniu całego obwodu są przywracane do swoich początkowych stanów. Pozwala to ponownie używać tych kubitów jako kubitów przestrzeni roboczej do innych celów. Znane są również strategie zmniejszania liczby wymaganych kubitów przestrzeni roboczej (które kosztują zwiększenie rozmiarów obwodów), ale nie będziemy tutaj omawiać tych strategii.

Implementowanie funkcji odwracalnych

Opisana powyżej konstrukcja pozwala nam symulować dowolny obwód boolowski za pomocą obwodu kwantowego w sposób wolny od śmieci. Jeśli $C$ jest obwodem boolowskim implementującym funkcję $f:\Sigma^n \rightarrow \Sigma^m,$ to otrzymujemy obwód kwantowy $Q,$ który działa następująco na stanach bazy standardowej.

$$Q \bigl( \vert y \rangle \vert 0^k \rangle \vert x\rangle\bigr) = \vert y \oplus f(x) \rangle \vert 0^k \rangle \vert x\rangle$$

Liczba $k$ wskazuje, ile kubitów przestrzeni roboczej jest łącznie wymaganych. Dla celów tego kursu to wystarczy, ale możliwe jest posunięcie tej metodologii o krok dalej, gdy sama funkcja $f$ jest odwracalna.

Ściślej, załóżmy, że funkcja $f$ ma postać $f:\Sigma^n \rightarrow \Sigma^n,$ i załóżmy, że istnieje funkcja $f^{-1}$ taka, że $f^{-1}(f(x)) = x$ dla każdego $x\in\Sigma^n$ (która jest jednoznacznie wyznaczona, gdy istnieje). Oznacza to, że operacja przekształcająca $\vert x \rangle$ w $\vert f(x) \rangle$ dla każdego $x\in\Sigma^n$ jest unitarna, więc możemy mieć nadzieję na zbudowanie obwodu kwantowego implementującego operację unitarną zdefiniowaną przez

$$U \vert x \rangle = \vert f(x) \rangle$$

dla każdego $x\in\Sigma^n.$

Żeby było jasne, unitarność tej operacji opiera się na odwracalności $f$ — nie jest unitarna, gdy $f$ nie jest odwracalna. Pomijając kubity przestrzeni roboczej, $U$ różni się od operacji implementowanej przez obwód $Q,$ ponieważ nie zachowujemy kopii wejścia i nie XORujemy go z dowolnym ciągiem — zastępujemy $x$ przez $f(x).$

Pytanie brzmi: gdy $f$ jest odwracalna, czy możemy to zrobić?

Odpowiedź brzmi: tak, pod warunkiem że możemy używać kubitów przestrzeni roboczej, a oprócz obwodu boolowskiego obliczającego $f,$ mamy też taki, który oblicza $f^{-1}.$ Nie jest to więc skrót do obliczeniowego odwracania funkcji, gdy nie wiemy jak to zrobić! Poniższy diagram ilustruje, jak można to osiągnąć poprzez złożenie dwóch obwodów kwantowych, $Q_f$ i $Q_{f^{-1}},$ uzyskanych indywidualnie dla funkcji $f$ i $f^{-1}$ opisaną powyżej metodą, razem z $n$ bramkami swap, przyjmując $k$ jako maksimum liczb kubitów przestrzeni roboczej wymaganych przez $Q_f$ i $Q_{f^{-1}}.$