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

10

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.

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

Antworten:

9

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

  • f(x)F(x)F(x)

  • Ua

    Ua:|0|012n/2x|x(1F(x)|0+F(x)|1).
    f(x) in einem Ancilla-Register durch, implementieren damit eine kontrollierte Drehung des zweiten Registers und berechnen dann das Ancilla-Register.
  • G=Ua(I2|00||00|)UaIZ .

  • Ua|0|0G

|ψ=1xF(x)xF(x)|x|1|ψ=1x1F(x)x1F(x)|x|0,
Ua|0|0=(xF(x)|ψ+x1F(x)|ψ)2n/2|ψF(x)|1|ψIZm2nm

Dies ist übrigens interessant im Vergleich zur "Leistung eines sauberen Qubits", auch bekannt als DQC1. Dort, wenn Sie anwendenUaI2n|00|


z

x|f(x)f(z)|.
Txf(x)TT

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