W jaki sposób algorytm Grovera służy do oszacowania średniej i mediany zbioru liczb?


10

Na stronie Wikipedii dotyczącej algorytmu Grovera wspomniano, że:

„Algorytm Grovera można również wykorzystać do oszacowania średniej i mediany zbioru liczb”

Do tej pory wiedziałem tylko, jak można go wykorzystać do przeszukiwania bazy danych. Ale nie jestem pewien, jak wdrożyć tę technikę, aby oszacować średnią i medianę zbioru liczb. Co więcej, nie ma cytatu (o ile zauważyłem) na tej stronie, która wyjaśnia technikę.


Albo jeśli zdecydujesz się odpowiedzieć na własne pytanie, albo dla każdego, kto zdecyduje się wziąć to zadanie dla siebie, ten link wygląda na świetne miejsce do rozpoczęcia korzystania z Algorytmu Grovera w celu znalezienia średniej (czyli średniej, całki) funkcji Weirdo
agaitaarino

@agaitaarino Thanks. Przejrzę to. Nawiasem mówiąc, twój komentarz nie wyświetla się poprawnie jako link, ponieważ pozostawiłeś puste miejsce po nawiasie otwierającym. :)
Sanchayan Dutta

Odpowiedzi:


9

Pomysł oszacowania średniej jest mniej więcej następujący:

  • Dla każdego który daje dane wyjściowe w liczbach rzeczywistych, zdefiniuj przeskalowany F ( x ), który daje dane wyjściowe w zakresie od 0 do 1. Naszym celem jest oszacowanie średniej F ( x ) .fa(x)fa(x)fa(x)

  • Zdefiniuj jednostkowy którego operacją jest U a : | 0 | 0 1UzaWażne jest, aby pamiętać, że ten unit jest łatwy do wdrożenia. Zaczynasz od transformacji Hadamarda w pierwszym rejestrze, wykonujesz obliczeniaf(x)w rejestrze ancilla, używasz go do implementacji kontrolowanego obrotu drugiego rejestru, a następnie odliczasz rejestr ancilla.

    Uza:|0|012)n/2)x|x(1-fa(x)|0+fa(x)|1).
    fa(x)
  • Określić jednolity .sol=Uza(ja-2)|00||00|)UzajaZ

  • Począwszy od stanu użyj G podobnie jak byłoby użyć Grover iterator oszacować liczbę rozwiązań problemu wyszukiwania.Uza|0|0sol

Główną częścią tego algorytmu jest wzmocnienie amplitudy, jak opisano tutaj . Główną ideą jest to, że możesz zdefiniować dwa stany a to określa podprzestrzeń dla ewolucji. Stan początkowy toUa| 0| 0=(

|ψ=1xfa(x)xfa(x)|x|1|ψ=1x1-fa(x)x1-fa(x)|x|0,
. Amplituda| * Ftermin jasno przedstawiona informacja o średniąF(x), jeśli moglibyśmy oszacować go. Możesz po prostu wielokrotnie przygotowywać ten stan i mierzyć prawdopodobieństwo otrzymania| 1na drugim rejestrze, ale wyszukiwania Grovera daje kwadratowego poprawę. Jeśli porównasz to ze sposobem ustawienia Grovera, amplituda tego| * FUza|0|0=(xfa(x)|ψ+x1-fa(x)|ψ)2)-n/2)|ψfa(x)|1|ψktórą możesz „oznaczyć” (w tym przypadku poprzez zastosowanie ) byłoby jaZ gdziemjest liczbą rozwiązań.m2)nm

Nawiasem mówiąc, jest to interesujące w porównaniu z „mocą jednego czystego kubita”, znanego również jako DQC1. Tam, jeśli zastosujesz do IUza, prawdopodobieństwo otrzymania 1 odpowiedzi jest dokładnie takie samo jak w przypadku wersji nieprzyspieszonej i daje oszacowanie średniej.ja2)n|00|


z

x|fa(x)-fa(z)|.
T.xfa(x)T.T.

Oczywiście pomijam niektóre szczegóły dotyczące dokładnych czasów działania, szacunków błędów itp.


Czy musisz najpierw uruchomić algorytm Grovera logarytmiczną liczbę razy, aby obliczyć wartość minimalną i maksymalną funkcji, zanim będziesz mógł wykonać przeskalowanie w kroku 1?
tparker

@tparker To prawdopodobnie zależy. Często zakłada się, że wiesz wystarczająco dużo o funkcji F, aby móc ograniczyć jej możliwe wartości.
DaftWullie
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.