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,