Jak zaimplementować klasyczne obliczenia na komputerze kwantowym

Ukończone

Teraz, gdy rozumiesz klasyczny problem, który próbujesz rozwiązać, zobaczmy, jak przekonwertować ten opis problemu na operację kwantową, która może być używana przez algorytm wyszukiwania Grovera i uruchamiana na komputerze kwantowym.

Jak wykonywać obliczenia w ramach stanu superpozycji?

Jedną z kluczowych właściwości przetwarzania kwantowego jest możliwość wykonywania obliczeń nie tylko na poszczególnych danych wejściowych, ale również na superpozycjach danych wejściowych. Podczas pracy z problemem z wyszukiwaniem i konkretną funkcją $f(x)$ opisującą wystąpienie problemu z wyszukiwaniem, który próbujemy rozwiązać, musimy mieć możliwość obliczenia tej funkcji również w ramach superpozycji danych wejściowych.

Uwaga

Wyrocznia kwantowa to operacja „nieprzezroczystej skrzynki”, która jest używana jako dane wejściowe dla innego algorytmu (w tym przypadku algorytmu Grovera, ale termin „wyrocznia” jest szeroko używany również w odniesieniu do przetwarzania klasycznego). Niektóre algorytmy kwantowe są opisywane z punktu widzenia wyroczni kwantowych, co podkreśla możliwość ich stosowania do szerokiej klasy problemów, o ile problem można efektywnie zaimplementować jako wyrocznię kwantową. W przypadku takich algorytmów analiza środowiska uruchomieniowego jest zwykle przeprowadzana pod kątem liczby wywołań wyroczni (czyli ocen funkcji), a nie w odniesieniu do pierwotnych operacji wykonanych przez algorytm.

Jeśli do rozwiązania określonego problemu używamy algorytmu opisanego w odniesieniu do wyroczni kwantowych, musimy zaimplementować dla tego problemu odpowiednią wyrocznię kwantową. W przypadku algorytmu Grovera wyrocznia oblicza wartość funkcji $f(x)$, którą próbujemy odwrócić.

Istnieją dwa typowe sposoby kodowania efektów przetwarzania funkcji dla stanu superpozycji — przy użyciu wyroczni fazowej lub wyroczni oznaczającej.

Załóżmy, że chcemy zaimplementować operator kwantowy $U$, który oblicza funkcję $f(x)$ przyjmującą jeden bit jako dane wejściowe i tworzącą pojedynczy bit jako dane wyjściowe. Zaczynamy od stanu superpozycji $a_0 |0\rangle + a_1 |1\rangle$.

  • Możemy zakodować wartości $f(0)$ i $f(1)$ we względnych fazach stanów bazowych, odpowiednio $|0\rangle$ and $|1\rangle$.
    W tym przypadku zastosowanie operatora $U_\textrm{phase}$ konwertuje stan $a_0 |0\rangle + a_1 |1\rangle$ na stan $(-1)^{f(0)} a_0 |0\rangle + (-1)^{f(1)} a_1 |1\rangle$. Mówiąc inaczej, operator $U_\textrm{phase}$ nie zmienia fazy stanów bazowych, dla których $f(x) = 0$, ale mnoży fazy stanów bazowych, dla których $f(x) = 1$, przez $-1$.
    Operator $U_\textrm{phase}$ nosi nazwę wyroczni fazowej.

  • Alternatywnie można przydzielić dodatkowy kubit $y$ i zakodować wartości $f(0)$ i $f(1)$ w stanie tego kubitu.
    W tym przypadku dzielimy połączony stan naszego kubitu danych i dodatkowego kubitu w ramach liniowej kombinacji stanów bazowych $a_{00} |0\rangle_x|0\rangle_y + a_{01} |0\rangle_x|1\rangle_y + a_{10} |1\rangle_x|0\rangle_y + a_{11} |1\rangle_x|1\rangle_y$ i stosujemy operator $U_\textrm{mark}$ do każdego z tych stanów osobno. Ten operator przekształca stan bazowy $|x\rangle|y\rangle$ w $|x\rangle|y \oplus f(x)\rangle$ ($\oplus$ to dodawanie modulo 2). Mówiąc inaczej, operator $U_\textrm{mark}$ nie zmienia stanów bazowych, dla których $f(x) = 0$ i przerzuca stan kubitu dodatkowego dla stanów, dla których $f(x) = 1$. Pełen wpływ na superpozycję można wywnioskować za pomocą faktu, że operatory kwantowe są liniowe: oznacza to, że nasz stan początkowy zostanie przekształcony w $a_{00} |0\rangle_x|f(0)\rangle_y + a_{01} |0\rangle_x|1 \oplus f(0)\rangle_y + a_{10} |1\rangle_x|f(1)\rangle_y + a_{11} |1\rangle_x|1 \oplus f(1)\rangle_y$. W takim przypadku kubit dodatkowy na koniec jest często splątany z kubitami danych.
    Operator $U_\textrm{mark}$ jest nazywany wyrocznią oznaczającą.

Uwaga

Wykonywanie obliczeń w ten sposób to nie to samo co „możliwość szacowania funkcji dla wszystkich danych wejściowych jednocześnie”. Przypomnij sobie, że miary kwantowe ograniczają ilość informacji, które można wyodrębnić z systemu kwantowego, więc w obu przypadkach nie będzie można wyodrębnić wszystkich wartości funkcji z takich obliczeń. Musimy stworzyć inteligentny algorytm, który wykorzystuje zalety wykonywania obliczeń w superpozycji, aby znaleźć odpowiedź.

Najlepszy sposób reprezentowania klasycznych obliczeń w algorytmie kwantowym zależy od celów:

  • Wiele algorytmów kwantowych wymaga użycia pierwszego podejścia, które polega na zakodowaniu klasycznych wartości funkcji w fazach stanów bazowych, ponieważ takie podejście upraszcza wyrażanie algorytmu.
  • Drugie podejście, czyli kodowanie klasycznych wartości funkcji w stanach kubitów dodatkowych, sprawia, że wdrażanie klasycznych obliczeń jest łatwiejsze.
  • W praktyce często widzimy, że wyrocznia oznaczająca jest używana do implementowania klasycznych obliczeń, a następnie jest konwertowana na wyrocznię fazową w ostatnim kroku przed włączeniem operacji do pozostałej części algorytmu kwantowego.

Gałąź klasycznej nauki o komputerach o nazwie przetwarzanie odwracalne oferuje nam techniki potrzebne do implementowania klasycznych obliczeń na komputerze kwantowym. W ostatniej lekcji tego modułu wrócimy do pytania dotyczącego efektywnego implementowania wyroczni kwantowych podczas omawiania typów problemów, które mogą skorzystać z zalet algorytmu Grovera.

W następnej lekcji zobaczysz, jak zaimplementować przykładowy problem z kolorowania grafu jako wyrocznię kwantową przy użyciu języka Q#.