Wie wird der Grover-Algorithmus verwendet, um den Mittelwert und den Median einer Reihe von Zahlen zu schätzen?

Auf der Wikipedia-Seite für Grovers Algorithmus wird Folgendes erwähnt:

"Der Grover-Algorithmus kann auch zur Schätzung des Mittelwerts und des Medians einer Reihe von Zahlen verwendet werden."

Bisher wusste ich nur, wie man damit eine Datenbank durchsuchen kann. Sie sind sich jedoch nicht sicher, wie Sie diese Technik implementieren sollen, um den Mittelwert und den Median einer Reihe von Zahlen zu schätzen. Außerdem gibt es auf dieser Seite kein Zitat (soweit ich es bemerkt habe), das die Technik erklärt.

algorithm grovers-algorithm Sanchayan Dutta
quelle

Entweder wenn Sie Ihre eigene Frage beantworten möchten oder für jeden, der die Aufgabe selbst übernimmt, ist dieser Link ein

guter

@agaitaarino Danke. Ich werde es durchsehen. Übrigens wird Ihr Kommentar als Link nicht richtig gerendert, da Sie nach der öffnenden Klammer ein Leerzeichen gelassen haben. :)

Sanchayan Dutta

Ich denke, das relevante Papier ist "Ein optimaler Quantenalgorithmus zur Approximation des Mittelwerts und seiner Anwendung zur Approximation des Medians einer Menge von Punkten über eine beliebige Entfernung" von Brassard et al .

Craig Gidney

Antworten:

Die Idee zur Schätzung des Mittelwerts ist ungefähr wie folgt:

$f(x)$ $F(x)$ $F(x)$
$U_a$
$U_{a} : | 0 ⟩ | 0 ⟩ \mapsto \frac{1}{2^{n / 2}} \sum_{x} | x ⟩ (\sqrt{1 - F (x)} | 0 ⟩ + \sqrt{F (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)$ in einem Ancilla-Register durch, implementieren damit eine kontrollierte Drehung des zweiten Registers und berechnen dann das Ancilla-Register.
$G=U_a (\mathbb{I}-2|0\rangle\langle 0|\otimes |0\rangle\langle 0|)U_a^\dagger \mathbb{I}\otimes Z$ .
$U_a|0\rangle|0\rangle$ $G$

| ψ ⟩ = \frac{1}{\sqrt{\sum_{x} F (x)}} \sum_{x} \sqrt{F (x)} | x ⟩ | 1 ⟩ | ψ^{⊥} ⟩ = \frac{1}{\sqrt{\sum_{x} 1 - F (x)}} \sum_{x} \sqrt{1 - F (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,$

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$

I \otimes Z

$\mathbb{I}\otimes Z$

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

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

m

$m$

Dies ist übrigens interessant im Vergleich zur "Leistung eines sauberen Qubits", auch bekannt als DQC1. Dort, wenn Sie anwenden $U_a$ $\frac{\mathbb{I}}{2^n}\otimes|0\rangle\langle 0|$

$z$

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

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

T

$T$

x

$x$

f (x) \leq T

$f(x)\leq T$

T

$T$

Natürlich überspringe ich einige Details zu genauen Laufzeiten, Fehlerschätzungen usw.

DaftWullie
quelle

Müssen Sie den Grover-Algorithmus zuerst logarithmisch ausführen, um den Min- und Max-Wert der Funktion zu berechnen, bevor Sie die Neuskalierung in Schritt 1 durchführen können?

Parker

@tparker Das kommt wohl drauf an. Oft wird angenommen, dass Sie genug über die Funktion F wissen, um ihre möglichen Werte begrenzen zu können.

DaftWullie