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

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ę.

algorithm grovers-algorithm

— Sanchayan Dutta
źródło

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

Myślę, że odpowiednim dokumentem jest „Optymalny algorytm kwantowy do aproksymacji średniej i jego zastosowanie do aproksymacji mediany zbioru punktów na dowolnej odległości” Brassarda i in .

— Craig Gidney

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

Dla każdego który daje dane wyjściowe w liczbach rzeczywistych, zdefiniuj przeskalowany który daje dane wyjściowe w zakresie od 0 do 1. Naszym celem jest oszacowanie średniej . $f(x)$ $F(x)$ $F(x)$
Zdefiniuj jednostkowy którego operacją jest $U_a$ Ważne jest, aby pamiętać, że ten unit jest łatwy do wdrożenia. Zaczynasz od transformacji Hadamarda w pierwszym rejestrze, wykonujesz obliczeniaw rejestrze ancilla, używasz go do implementacji kontrolowanego obrotu drugiego rejestru, a następnie odliczasz rejestr ancilla.
$U_{za} : | 0 ⟩ | 0 ⟩ \mapsto \frac{1}{{2)}^{n / 2)}} \sum_{x} | x ⟩ (\sqrt{1 - fa (x)} | 0 ⟩ + \sqrt{fa (x)} | 1 ⟩) .$ $U_a:|0\rangle|0\rangle\mapsto\frac{1}{2^{n/2}}\sum_x|x\rangle(\sqrt{1-F(x)}|0\rangle+\sqrt{F(x)}|1\rangle).$ $f(x)$
Określić jednolity . $G=U_a (\mathbb{I}-2|0\rangle\langle 0|\otimes |0\rangle\langle 0|)U_a^\dagger \mathbb{I}\otimes Z$
Począwszy od stanu użyj podobnie jak byłoby użyć Grover iterator oszacować liczbę rozwiązań problemu wyszukiwania. $U_a|0\rangle|0\rangle$ $G$

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 to

| ψ ⟩ = \frac{1}{\sqrt{\sum_{x} fa (x)}} \sum_{x} \sqrt{fa (x)} | x ⟩ | 1 ⟩ | ψ^{⊥} ⟩ = \frac{1}{\sqrt{\sum_{x} 1 - fa (x)}} \sum_{x} \sqrt{1 - fa (x)} | x ⟩ | 0 ⟩,

$|\psi\rangle=\frac{1}{\sqrt{\sum_x F(x)}}\sum_x\sqrt{F(x)}|x\rangle|1\rangle \qquad |\psi^\perp\rangle=\frac{1}{\sqrt{\sum_x 1-F(x)}}\sum_x\sqrt{1-F(x)}|x\rangle|0\rangle,$

. Amplituda

termin jasno przedstawiona informacja o średnią

, jeśli moglibyśmy oszacować go. Możesz po prostu wielokrotnie przygotowywać ten stan i mierzyć prawdopodobieństwo otrzymania

na drugim rejestrze, ale wyszukiwania Grovera daje kwadratowego poprawę. Jeśli porównasz to ze sposobem ustawienia Grovera, amplituda tego

U_{a} | 0 ⟩ | 0 ⟩ = (\sqrt{\sum_{x} F (x)} | ψ ⟩ + \sqrt{\sum_{x} 1 - F (x)} | ψ^{⊥} ⟩) 2^{- n / 2}

$U_a|0\rangle|0\rangle=(\sqrt{\sum_x F(x)}|\psi\rangle+\sqrt{\sum_x 1-F(x)}|\psi^\perp\rangle)2^{-n/2}$

| ψ ⟩

$|\psi\rangle$

F (x)

$F(x)$

| 1 ⟩

$|1\rangle$

| ψ ⟩

$|\psi\rangle$ którą możesz „oznaczyć” (w tym przypadku poprzez zastosowanie

) byłoby

I \otimes Z

$\mathbb{I}\otimes Z$

gdzie

jest liczbą rozwiązań.

\sqrt{\frac{m}{2^{n}}}

$\sqrt{\frac{m}{2^n}}$

m

$m$

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 $U_a$ , prawdopodobieństwo otrzymania 1 odpowiedzi jest dokładnie takie samo jak w przypadku wersji nieprzyspieszonej i daje oszacowanie średniej. $\frac{\mathbb{I}}{2^n}\otimes|0\rangle\langle 0|$

$z$

\sum_{x} | fa (x) - fa (z) | .

$\sum_x|f(x)-f(z)|.$

T

$T$

x

$x$

f (x) \leq T

$f(x)\leq T$

T

$T$

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

— DaftWullie
źródło

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