Czy możemy wykorzystać równoległość kwantową do obliczenia wielu funkcji jednocześnie?

Dobrze wiadomo, że wykorzystując paralelizm kwantowy możemy obliczyć funkcję dla wielu różnych wartości jednocześnie. Potrzebne są jednak pewne sprytne manipulacje w celu wydobycia informacji o każdej wartości, tj. Algorytmem Deutscha.$f(x)$$x$

Rozważmy odwrotny przypadek: czy możemy użyć równoległości kwantowej do obliczenia wielu funkcji (powiedzmy ) jednocześnie dla pojedynczej wartości x_0 ?$f(x),g(x),\dots$$x_0$

Dokładna odpowiedź zależy od dokładnego rodzaju superpozycji, którą chcesz. Odpowiedzi piramid i Niel dają ci coś podobnego

Tutaj śledziłem Niel w oznaczaniu różnych funkcji , itd., oznacza całkowitą liczbę funkcji, które chcesz nałożyć. Użyłem również do oznaczenia opisu funkcji jako zapisanego programu. Tylko cokolwiek potrzeby numer będzie tam stan zostać znormalizowane.$f_1$$f_2$$n$$F_t$$f_t$$A$

Zauważ, że nie jest to po prostu superpozycja . Jest zaplątany w przechowywany program. Jeśli miałbyś wyśledzić zapisany program, miałbyś po prostu kombinację . Oznacza to, że przechowywany program może stanowić „śmieci”, co zapobiega efektom interferencyjnym, na które możesz liczyć. A może nie. To zależy od tego, w jaki sposób ta superpozycja zostanie wykorzystana w obliczeniach.$f_t(x)$$f_t(x)$

Jeśli chcesz pozbyć się śmieci, sprawy stają się trudniejsze. Załóżmy na przykład, że chcesz uzyskać jednolity który ma efekt$U$

dla wszystkich możliwych danych wejściowych (które, jak zakładam, są łańcuchami bitów zapisanymi w podstawie obliczeniowej). Zauważ, że umieściłem również puste kubity po stronie wejściowej, na wypadek gdyby funkcje miały dłuższe wyjścia niż wejścia.$x$

Z tego możemy bardzo szybko znaleźć warunek, który muszą spełniać funkcje: ponieważ stany wejściowe tworzą zbiór ortogonalny, podobnie jak wyniki. Spowoduje to znaczne ograniczenie rodzajów funkcji, które można łączyć w ten sposób.

Funkcje , które chcesz ocenić w różnych gałęziach obliczeniowych, muszą być, aby w ogóle być obliczalne, w jakiś sposób określone (np. Sekwencja klasycznych bramek logicznych). A zbiór funkcji, które chcesz obliczyć, powinien sam być obliczalny: dla danego musisz być w stanie obliczyć specyfikację tego, jak ma być obliczony na podstawie jego argumentu. W rezultacie: musisz mieć możliwość opisania funkcji jako zapisanych programów. (Wszystkie są konieczne, nawet zanim rozważymy obliczenia kwantowe, na pytanie „obliczenie jednej / wszystkich funkcji na wejściu$f,g,\ldots$ $\{ f_1, f_2 , \ldots \}$$t$$f_t$$f_t$$f_1, f_2, \ldots$$x_0$„mieć sens.)

Gdy masz już sposób określania funkcji jako przechowywanych programów, to w zasadzie gotowe: program jest zasadniczo innym rodzajem danych wejściowych, które możesz przygotować w superpozycji, i np. Ocenić na stałym wejściu lub superpozycji danych wejściowych, obliczając funkcje z ich specyfikacji w każdej branży.

Aby uzyskać comptational przewagę od tego jest inna sprawa, i będzie musiał zaangażować jakąś specyficzną strukturę w funkcje , które można wykorzystać, ale po prostu do „oceny w superpozycji” jest łatwo zrobić, jeśli masz wystarczająco dużo informacji dla pytanie rozsądne.$f_t$

Tak (w zależności od tego, co oznacza „oblicz wiele funkcji jednocześnie”)

Opisując obwód, który daje funkcję jako i obwód dający jako , można to na kilka sposobów:$f$$U_f$$g$$U_g$

1. Zaczynając od rejestrów qubit w , Przygotuj stan na pierwszych dwóch rejestrach. Można to zrobić poprzez zastosowanie jednolitego ¹ w pierwszym rejestrze, aby umieścić ten rejestr w stanie przed nałożeniem CNOT, potem . Następnie zastosuj z pierwszego rejestru do trzeciego i z drugiego do trzeciego.$\left|00x\right>$$\alpha\left|01\right>+\beta\left|10\right>$$\alpha\left|0\right> + \beta\left|1\right>$$I\otimes X$$CU_f$$CU_g$

   1.1 Daje to, że trzeci rejestr jest teraz w stanie , kiedy początkowe operacje (do ) na pierwszych dwóch rejestrach są wywrócony. Jednak ze względu na ogólne trudności związane z realizacją arbitralnych operacji kontrolowanych-jednostkowych (a także niepotrzebnego korzystania z dodatkowych kubitów) prawdopodobnie łatwiej byłoby to zrealizować bezpośrednio, wybierając numer jednolity . Zauważ, że nie jest to ani implementacja ani , ale nowa, inna funkcja$\left(\alpha U_f + \beta U_g\right)\left|x\right>$$I\otimes X$$\alpha U_f + \beta U_g$$f$$g$$f+g$

   1.2 Brak odwrócenia początkowych operacji na pierwszych dwóch rejestrach stawia trzeci w pewnym splątanym stanie i , co omówiono w innych odpowiedziach.$f$$g$

2. Zaczynając od stanu i stosując do pierwszego rejestru i do drugiego. Jest to najbliższy klasycznemu paralelizmowi, w którym obie funkcje są stosowane niezależnie do kopii tego samego stanu. Poza wymaganiem podwójnej liczby kubitów, problem polega na tym, że ze względu na brak klonowania, aby skopiować , musi on być znany lub być stanem klasycznym (tj. Nie obejmować superpozycji w podstawie obliczeniowej). Można również zastosować przybliżone klonowanie .$\left|xx\right>$$U_f$$U_g$$\left|x\right>$

3. Zacznij od stanu , a także klasycznego rejestru. Zastosuj jednostkę ^1, aby umieścić pierwszy rejestr w superpozycji . Teraz zmierz ten rejestr (umieszczając wynik w rejestrze klasycznym) i zastosuj klasyczną operację . Chociaż może się to wydawać mniej skuteczne niż którakolwiek z powyższych operacji, jest to w pewnym sensie równoważne kanałowi kwantowemu . Takie metody można stosować do tworzenia losowych jednostek, które mają zastosowanie np. W próbkowaniu bozonów i$\left|0x\right>$$\alpha\left|0\right>+\beta\left|1\right>$IF RESULT = 0 U_f ELSE U_g$\mathcal E\left(\rho\right) = \lvert\alpha\rvert^2U_f\rho U_f^\dagger + \lvert\beta\rvert^2U_g\rho U_g^\dagger$randomizowane testy porównawcze

^{1 podany przez}

Tak, można. Sztuczka polega na zdefiniowaniu (i zaimplementowaniu) nowej funkcji która ma wartość jeśli , do jeśli itd. Następnie przygotowuje się kubity reprezentujące żądanej superpozycji i ustaw na .$f_\mathrm{all}(y,x)$$f(x)$$y=0$$g(x)$$y=1$$y$$x$$x_0$