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

9

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 ? $f(x),g(x),\dots$ $x_0$

algorithm speedup

— donnydm
źródło

Aby ocenić

f (x_{0})

$f(x_0)$ i

g (x_{0})

$g(x_0)$ trzeba wykonać kopię

x_{0}

$x_0$ dla każdej operacji, która w ogóle nie jest możliwe twierdzenia bez klonowania. Z drugiej strony, jeśli po prostu przygotujesz stan, który jest dwa razy

x_{0}

$x_0$ , po prostu przywrócisz klasyczną równoległość.

@HenriMenke A może niedoskonałe klonowanie?

— donnydm,

@HenriMenke: twoje pojęcie „klonowania” wydaje się być bardzo szerokie, do tego stopnia, że stanowi przeszkodę dla twojej zdolności do produktywnego podejścia do problemów.

— Niel de Beaudrap,

5

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

A \sum_{t = 1}^{n} | f_{t} (x) ⟩ \otimes | F_{t} ⟩

$A\sum_{t=1}^n |\,\,f_t (x)\,\,\rangle \otimes |F_t\rangle$

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$

U : | x ⟩ \otimes | 0 ⟩^{\otimes N} \to A \sum_{t = 1}^{n} | f_{t} (x) ⟩

$U : \,\,\, | x \rangle \otimes |0\rangle^{\otimes N} \rightarrow A \sum_{t=1}^n |\,\,f_t (x)\,\,\rangle$

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.

— James Wootton
źródło

Dziękuję, myślę, że w ten sposób można przyspieszyć coś jak obliczenia ekspansji Taylora. W każdym razie, czy można uzyskać dostęp do zmierzonego programu, aby uzyskać jakieś informacje, czy może to tylko narzędzie?

— donnydm,

Zapisany program zostanie zapisany w rejestrze kubitów, więc z pewnością można nim manipulować.

— James Wootton,

5

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$

— Niel de Beaudrap
źródło

3

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$

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$
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>$
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}

(\begin{matrix} α & - β^{*} \\ β & α^{*} \end{matrix})

$\begin{pmatrix}\alpha &&-\beta^* \\ \beta && \alpha^*\end{pmatrix}$

— Mithrandir24601
źródło

Jest to interesujące, częściowo dlatego, że nie jest potrzebny żaden zapisany program. Czy konieczne jest podanie CNOT pod numerem 1?

— donnydm,

2

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$

— piramidy
źródło