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

10

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?

Kelalaka
źródło

Odpowiedzi:

6

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

Hn(In2|00|n)HnUS,
zaczynając od stanu początkowego (H|0)n. To wymaga czasuΘ(N). (UżywamIn oznaczać 2n×2n macierz jednostkowa.)

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

(IkH(nk))Ik(Ink2|00|(nk))(IkH(nk))US
i zaczynając od stanu |x(H|0)(nk) Czas wymagany do ich uruchomienia zostałby skrócony do O(N/K), kosztem wymagania 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 (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 dostanieszK 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 danaxjest 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
1
N idzie w nieskończoność, ale Knie. Twój problem staje się większy, ale twoich zasobów pozostaje niewiele.
AHusain,
1
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, czyKjest 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,
3

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 Noperacje dla przypadku nierównoległego. Powiedzmy, że mamy dwa węzły i dzielimy listę N elementów na dwie listy wielkościN1,N2. Trwa wyszukiwanie na listach podrzędnychN1,N2.

Mamy to jednak

N=N1+N2N1+N2

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ą wO 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
2
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,
3
@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,
2
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 zrobiszkO(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 N. do log(k)N./k dla k(N.)Ω(1) równoległe procesy Grovera, co stanowi poprawę o współczynnik k/log(k)(współczynnik log pochodzi z identyfikacji, które, jeśli jakiś proces znalazł rozwiązanie).
Niel de Beaudrap,