Czy możemy przyspieszyć algorytm Grovera, uruchamiając równoległe procesy?

W obliczeniach klasycznych możemy uruchomić wyszukiwanie klucza (na przykład AES), uruchamiając równolegle węzły obliczeniowe jak najwięcej.

Oczywiste jest, że możemy również uruchomić wiele algorytmów Grovera.

Moje pytanie brzmi ; czy możliwe jest przyspieszenie przy użyciu więcej niż jednego algorytmu Grovera, jak w przypadku klasycznego przetwarzania?

classical-computing grovers-algorithm cryptography Kelalaka
źródło

Odpowiedzi:

Na pewno! Wyobraź sobie, że masz $K=2^k$ kopie wyroczni poszukiwawczej $U_S$ z którego możesz skorzystać. Zwykle wyszukiwałbyś, powtarzając akcję

H^{\otimes n} (I_{n} - 2 | 0 ⟩ ⟨ 0 |^{\otimes n}) H^{\otimes n} U_{S},

$H^{\otimes n}(\mathbb{I}_n-2|0\rangle\langle 0|^{\otimes n})H^{\otimes n}U_S,$ zaczynając od stanu początkowego

(H | 0 ⟩)^{\otimes n}

$(H|0\rangle)^{\otimes n}$ . To wymaga czasu

Θ (\sqrt{N})

$\Theta(\sqrt{N})$ . (Używam

I_{n}

$\mathbb{I}_n$ oznaczać

2^{n} \times 2^{n}

$2^n\times 2^n$ macierz jednostkowa.)

Możesz to zastąpić $2^k$ równoległe kopie, każda zindeksowana przez $x\in\{0,1\}^k$ , za pomocą

(I_{k} \otimes H^{\otimes (n - k)}) I_{k} \otimes (I_{n - k} - 2 | 0 ⟩ ⟨ 0 |^{\otimes (n - k)}) (I_{k} \otimes H^{\otimes (n - k)}) U_{S}

$\left(\mathbb{I}_k\otimes H^{\otimes (n-k)}\right)\mathbb{I}_k\otimes(\mathbb{I}_{n-k}-2|0\rangle\langle 0|^{\otimes (n-k)})\left(\mathbb{I}_k\otimes H^{\otimes (n-k)}\right)U_S$ i zaczynając od stanu

| x ⟩ (H | 0 ⟩)^{\otimes (n - k)}

$|x\rangle(H|0\rangle)^{\otimes(n-k)}$ Czas wymagany do ich uruchomienia zostałby skrócony do

O (\sqrt{N / K})

$O(\sqrt{N/K})$ , kosztem wymagania

K

$K$ razy więcej miejsca.

W sensie skalowania można uznać to za nieistotny wynik. Jeśli masz określoną liczbę wyroczni, $K$ , wtedy otrzymasz naprawiony ( $\sqrt{K}$ ) poprawa (tak jak, jeśli masz $K$ równoległe klasyczne rdzenie, najlepsza poprawa, jaką możesz uzyskać, jest czynnikiem $K$ ), a to nie zmienia skalowania. Ale zmienia podstawowy czas działania. Wiemy, że algorytm Grovera jest dokładnie optymalny. Pojedyncza wyrocznia zajmuje absolutnie minimalny możliwy czas. Więc wiedząc, że dostaniesz $\sqrt{K}$ skrócenie czasu jest przydatne w odniesieniu do tego wskaźnika dla określonego czasu działania przy określonej wartości $N$ .

DaftWullie
źródło

ale jeśli to zrobisz, porównanie z klasycznym wykonaniem straci trochę na znaczeniu, prawda? W końcu możesz także przyspieszyć klasyczne wyszukiwanie, uruchamiając operację, która sprawdza, czy dana

x

$x$ jest celem równoległym dla wszystkich danych wejściowych. To oczywiście wymaga dodatkowych założeń w stosunku do dostępnych zasobów, ale takich samych założeń, jakie zostały poczynione w twoim argumencie

glS

N

$N$ idzie w nieskończoność, ale

K

$K$ nie. Twój problem staje się większy, ale twoich zasobów pozostaje niewiele.

AHusain,

Ta odpowiedź jest poprawna (choć może nie być optymalna, jak ostrzega DaftWullie). Jest to takie samo podejście do równoległości, jak przy klasycznej złożoności obwodu. Jeśli chcesz przyspieszenia z powodu równoległości, zwróć uwagę na głębokość obwodu (ponieważ koordynacja wielu procesów nie zmniejszy całkowitej pracy). Nie ma nawet znaczenia, czy

K

$K$ jest stały --- albo jesteś zainteresowany poprawą głębokości z równoległości, albo nie. Podobnie jak w przypadku samych obliczeń kwantowych, samo rzucenie większej liczby komputerów w problem nie magicznie wszystko przyspiesza!

Niel de Beaudrap,

W pewnym sensie, gdybyśmy robili to równolegle na różnych węzłach, zaoszczędziłbyś czas na uruchamianie. Ale jeśli mówimy o złożoności (to ogólnie nazywamy przyspieszeniem), potrzebujemy trochę analizy.

Zgadzasz się, że potrzebujemy $\sqrt{N}$ operacje dla przypadku nierównoległego. Powiedzmy, że mamy dwa węzły i dzielimy listę N elementów na dwie listy wielkości $N_1,N_2$ . Trwa wyszukiwanie na listach podrzędnych $\sqrt{N_1},\sqrt{N_2}$ .

Mamy to jednak

\sqrt{N} = \sqrt{N_{1} + N_{2}} \leq \sqrt{N_{1}} + \sqrt{N_{2}}

$\sqrt{N} = \sqrt{N_1+N_2} \le \sqrt{N_1} + \sqrt{N_2}$

I nadal musisz sprawdzić, który wynik spośród procesów zwracanych przez procesy równoległe jest tym, którego szukasz. Dodaje stałą w złożoności, więc na ogół ukrywamy ją w $O$ notacja.

Byłoby to jednak interesujące, zwłaszcza jeśli musimy skupić sprzęt, ponieważ mamy ograniczoną liczbę kubitów lub inne ograniczenia.

cnada
źródło

Dla N1 = N2 jest to wciąż nierówność: sqrt (2) * sqrt (N1) <2 * sqrt (N1)

Mariia Mykhailova

Och, rzeczywiście. W mojej głowie $ \ sqrt {a b} = \ sqrt {a} \ sqrt {b} $ myślałem. Powinienem przestać odpowiadać na odpowiedzi tutaj o północy i kiedy jestem zmęczony. Dzięki za zwrócenie na to uwagi.

cnada,

@cnada: Istnieją co najmniej dwa różne pojęcia złożoności, z których oba są istotne dla przyspieszenia. Jeden to złożoność wielkości, a drugi to złożoność głębokości. O ile nie określono inaczej, często wolimy brać pod uwagę złożoność wielkości, ale złożoność głębokości jest nadal przedmiotem zainteresowania kwantowej złożoności obliczeniowej, na przykład w MBQC [arXiv: quant-ph / 0301052 , arXiv: 0704.1736 ] i ostatnich wynikach bezwarunkowe separacje głębokości [arXiv: 1704.00690 ].

Niel de Beaudrap,

@NieldeBeaudrap Myślałem, że ludzie bardziej patrzą na złożoność głębi. Jednak w przypadku Grover złożoność wielkości i głębokości jest mniej więcej taka sama. Jest to kwadratowe pod względem wielkości problemu (ogólnie postrzegane jako rozmiar listy N elementów). Czy uważasz, że moje podejście tutaj jest niewłaściwe?

cnada,

Nie mówisz nic złego , po prostu zwracam uwagę, że nadmiernie podkreślasz złożoność rozmiarów i tak naprawdę nie wypracowujesz korzyści dla złożoności głębokości. Nie dzieje się nic ciekawego, jeśli tylko to zrobisz

k \in O (1)

$k \in O(1)$ równoległe procesy Grovera, ale jak sugeruje odpowiedź DaftWullie (i biorąc pod uwagę klasyczną obróbkę końcową), złożoność głębokości sięga

\sqrt{N}

$\sqrt N$ do

\log (k) \sqrt{N / k}

$\log(k) \sqrt{N/k}$ dla

k (N) \in Ω (1)

$k(N) \in \Omega(1)$ równoległe procesy Grovera, co stanowi poprawę o współczynnik

\sqrt{k} / \log (k)

$\sqrt{k}/\!\!\;\log(k)$ (współczynnik log pochodzi z identyfikacji, które, jeśli jakiś proces znalazł rozwiązanie).

Niel de Beaudrap,