Jakie aplikacje ma algorytm wyszukiwania Grovera?

14

Algorytm wyszukiwania Grovera zwykle mówi się o znalezieniu zaznaczonego wpisu w nieposortowanej bazie danych. Jest to naturalny formalizm, który pozwala na bezpośrednie zastosowanie go do poszukiwania rozwiązań problemów NP (gdzie dobre rozwiązanie można łatwo rozpoznać).

Chciałem dowiedzieć się o innych zastosowaniach poszukiwania Grovera, aby znaleźć minimum, średnią i medianę zbioru liczb. To sprawia, że ​​zastanawiam się, czy są jakieś inne mniej oczywiste zastosowania wyszukiwania Grovera (lub zastosowania jego uogólnień, takie jak wzmocnienie amplitudy), które są już znane? Doceniamy wszelkie krótkie informacje na temat tego, jak to się robi.

DaftWullie
źródło

Odpowiedzi:

7

Oprócz tych, o których wspomniałeś, innym zastosowaniem (zmodyfikowanego) algorytmu Grovera, o którym wiem, jest rozwiązanie problemu kolizji w teorii złożoności, obliczeniach kwantowych i matematyce obliczeniowej . Jest również nazywany algorytmem BHT .

Wprowadzenie :

Problem kolizji najczęściej odnosi się do wersji 2 do 1, którą opisał Scott Aaronson w swojej rozprawie doktorskiej. Zakładając, że jest równe i funkcja f : { 1 , . . . , N } { 1 , . . . , n } wiemy z góry, że albo f wynosi 1 do 1, albo 2 do 1. Możemy zadawać pytania tylko o wartość f ( i ) dla dowolnego i { 1 , 2 ,nf:{1,...,n}{1,...,n}ff(i) . Następniepojawia siępytanie, ile zapytań musimy zadać, aby z całą pewnością ustalić, czy f jest 1 do 1, czy 2 do 1.i{1,2,...,n}f

Deterministyczne rozwiązanie wersji 2-do-1 wymaga zapytań, a ogólnie rozróżnienie funkcji r-to-1 od funkcji 1-do-1 wymaga n / r + 1 zapytań.n/2+1n/r+1

Deterministyczne klasyczne rozwiązanie :

Jest to proste zastosowanie zasady szufladki: jeśli funkcja jest r-do-1, to po zapytaniach mamy gwarancję znalezienia kolizji. Jeśli funkcja ma wartość od 1 do 1, kolizja nie istnieje. Jeśli będziemy mieli pecha, zapytania n / r mogą zwrócić różne odpowiedzi. Tak n / R + 1 zapytania są konieczne.n/r+1n/rn/r+1

Randomizowane klasyczne rozwiązanie :

Jeśli pozwolimy na losowość, problem będzie łatwiejszy. Według paradoksu urodzinowego, jeśli wybieramy (odrębne) zapytania losowo, wówczas z dużym prawdopodobieństwem znajdujemy kolizję w dowolnej stałej funkcji 2 do 1 po zapytania.Θ(n)

Rozwiązanie Quantum BHT :

Intuicyjnie algorytm łączy przyspieszenie pierwiastka kwadratowego z paradoksu urodzinowego przy użyciu (klasycznej) losowości z przyspieszeniem pierwiastka kwadratowego z algorytmu Grovera (kwantowego).

Pierwszy wejścia do F są wybierane losowo i F są odpytywane w każdym z nich. Jeśli między tymi danymi wejściowymi występuje kolizja, zwracamy kolidującą parę danych wejściowych. W przeciwnym razie wszystkie te dane wejściowe zostaną odwzorowane na różne wartości przez f . Następnie algorytm Grovera jest używany do znalezienia nowego wejścia do f, które koliduje. Ponieważ tylko n 2 / 3 takie środki do f algorytm Grover może odnaleźć jeden (jeżeli istnieje), dokonując jedynie O ( n1/3ffffn2/3fzapytania dof.O(n2/3)=O(n1/3)f

Źródła:

  1. https://en.wikipedia.org/wiki/Collision_problem

  2. https://en.wikipedia.org/wiki/BHT_algorithm

  3. Algorytm kwantowy dla problemu kolizji - Gilles Brassard, Peter Hoyer, Alain Tapp

Sanchayan Dutta
źródło
Uwagi dotyczące roztworu BHT (nie znaleźć źródło Wikipedia bardzo wiecania): najpierw wybrać wejścia do testu f losowo. Załóżmy, że nie kolidują. Posortuj te wartości x według f ( x ) . Teraz, jeśli f ( x ) jest 2-do-1, są N 1 / 3 wartości x nie zostały sprawdzone, że zderzać się z tych testów. Zdefiniuj więc funkcję, która sprawdza „jeszcze nie przetestowane i koliduje”. Określa zaznaczone wpisy. Zderzenie można łatwo przetestować za pomocą posortowanej listy wartości f ( xn1/3fxf(x)f(x)n1/3x . Znając dokładną liczbę zaznaczonych wpisów (jeśli 2 do 1), Grover (prawie) gwarantuje rozwiązanie. f(x)
DaftWullie
@DaftWullie Tak, to z pewnością ma sens. Algorytm Grovera nie gwarantuje rozwiązania, ale ma wysokie prawdopodobieństwo dostarczenia prawidłowego rozwiązania. Ale czy nie jest to dość oczywiste z samego opisu Wikipedii? Nie jestem pewien, czy rozumiem, o co ci chodzi. Czy coś brakuje?
Sanchayan Dutta
Mogę tylko powiedzieć, że nie było to dla mnie oczywiste . W pierwszym czytaniu zrozumiałem (fałszywie), że dla Grovera, zamiast przygotowywać superpozycję wszystkich możliwych stanów, przygotowałem superpozycję w stosunku do tych, które nie zostały jeszcze przetestowane. Ale to wydawało się kluczowe dla sposobu, w jaki wyjaśniono przyspieszenie. Początkowo martwiłem się również o sposób sprawdzania kolizji: które pary sprawdzane są pod kątem kolizji i jak skutecznie można obliczać kolizję?
DaftWullie
@DaftWullie Ah, dobrze. Wiem o co ci chodzi. Wikipedia nie zagłębia się w szczegóły algorytmu. Możesz zawsze odwołać się do oryginalnej pracy ( arxiv.org/abs/quant-ph/9705002 ) w celu uzyskania szczegółowych informacji (które, jak sądzę, już zrobiłeś). Później postaram się rozwinąć tę odpowiedź, aby uwzględnić wszystkie szczegóły. Nadal czytam gazetę.
Sanchayan Dutta
1
O ile kubity i bramy kwantowe nie okażą się niewiarygodnie tańsze od bitów i bram klasycznych, wszelkie dyskusje BHT powinny obejmować zastrzeżenie, że koszty przewyższają najnowocześniejsze klasyczne poszukiwania kolizji z maszyną van Oorschota – Wienera. Szczegółowe informacje można znaleźć na cr.yp.to/papers.html#collisioncost lub blog.cr.yp.to/20171017-collisions.html . (To drugie jest odpowiedzią na rzekome ulepszenie BHT, które twierdzi, że jest bardziej opłacalne niż klasyczne wyszukiwanie kolizji.)
Squeamish Ossifrage
4

Algorytm Grovera jest również szeroko stosowany w kryptografii kwantowej. Może być stosowany do rozwiązywania problemów, takich jak problem z logarytmem transcendentalnym, problem ze znalezieniem pierwiastka wielomianowego itp.

da281
źródło
Czy chciałbyś trochę rozwinąć? Jakie są te problemy? Gdzie mogę o nich przeczytać więcej?
DaftWullie
1
ieeexplore.ieee.org/document/7016940 To jest praca ieee, która ma na celu opracowanie algorytmu kwantowego do rozwiązania problemu wielomianowego znalezienia pierwiastka. Możesz przeczytać więcej na ten temat tam
da281,
0

Algorytm Grovera może być użyty do rozwiązania dowolnego problemu optymalizacji numerycznej szybciej niż wyszukiwanie metodą brute-force, ponieważ każdy problem optymalizacji można sformułować jako problem wyszukiwania (gdzie szukasz wyniku funkcji większego / mniejszego niż niektóre ustalone M. w ramach każdego przebiegu, i powtarzasz dla logarytmicznej liczby przebiegów za pomocą wyszukiwania binarnego, aby uzyskać optymalną wartość M.): https://epubs.siam.org/doi/abs/10.1137/040605072?journalCode=sjope8 .

W rzeczywistości algorytm Grovera jest najbardziej znanym algorytmem kwantowym dla wielu trudnych problemów optymalizacyjnych (takich jak NP-zupełne), które nie mają zbytniej struktury, które można poddać klasycznemu algorytmowi sprytniejszemu niż wyszukiwanie metodą brute-force: https: // link.springer.com/chapter/10.1007/978-3-540-78773-0_67 .

tparker
źródło