Quantum Amplitudenvergrößerung und Schätzung

Betrachten Sie eine boolesche Funktion χ: X \0, 1\, die die Menge X zwischen ihren guten und schlechten Elementen partitioniert, wobei x gut ist, wenn χ (x) =1 und schlecht, wenn nicht. Betrachten Sie auch einen Quantenalgorithmus A, sodass A |0= ₗ ₗ αₓ |x eine Quantenüberlagerung der Elemente von X ist, und lassen Sie a die Wahrscheinlichkeit bezeichnen, dass ein gutes Element erzeugt wird, wenn A |0 gemessen wird. Wenn wir den Prozess wiederholen, A ausführen, die Ausgabe messen und χ verwenden, um die Gültigkeit des Ergebnisses zu überprüfen, erwarten wir, im Durchschnitt 1/a Mal zu wiederholen, bevor eine Lösung gefunden wird. *Amplitudenvergrößerung* ist ein Prozess, der es ermöglicht, ein gutes x nach einer erwarteten Anzahl von Anwendungen von A und dessen Inversen zu finden, die proportional zu 1/a sind, vorausgesetzt, der Algorithmus A führt keine Messungen durch. Dies ist eine Verallgemeinerung des Suchalgorithmus von Grover, bei dem A auf die Erzeugung einer gleichmäßigen Überlagerung aller Mitglieder von X beschränkt war und wir die Zusage hatten, dass ein einzelnes x existiert, so dass χ (x) =1. Unser Algorithmus funktioniert unabhängig davon, ob der Wert von a im Voraus bekannt ist oder nicht. Falls der Wert von a bekannt ist, können wir ein gutes x nach einer Anzahl von Anwendungen von A und dessen Inversen finden, die proportional zu 1/a sind, selbst im schlimmsten Fall. Wir zeigen, dass dieser quadratische Geschwindigkeitsvorteil auch für eine große Familie von Suchproblemen erzielt werden kann, für die gute klassische Heuristiken existieren. Schließlich kombinieren wir als unser Hauptergebnis Ideen aus Grovers und Shors Quantenalgorithmen, um Amplitudenschätzung durchzuführen, einen Prozess, der es ermöglicht, den Wert von a zu schätzen. Wir wenden die Amplitudenschätzung auf das Problem des *ungefähreren Zählens* an, bei dem wir die Anzahl von x X schätzen möchten, so dass χ (x) =1. Wir erhalten optimale Quantenalgorithmen in einer Vielzahl von Szenarien.