Jakie aplikacje ma algorytm wyszukiwania Grovera?

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.

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 $n$$f:\{1,...,n\}\to\{1,...,n\}$$f$$f(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\in\{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+1$$n/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+1$$n/r$$n/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.$\Theta(\sqrt{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 ( $n^{1/3}$$f$$f$$f$$f$$n^{2/3}$$f$zapytania dof.$\mathcal{O}(\sqrt{n^{2/3}})=\mathcal{O}(n^{1/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

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.

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 .