Grovers Algorithmus: Was muss in Oracle eingegeben werden?

Ich bin verwirrt darüber, was ich in Grovers Algorithmus in Oracle eingeben soll.

Müssen wir nicht zusätzlich zu den überlagerten Quantenzuständen eingeben, wonach wir suchen und wo wir finden, wonach wir suchen?

Angenommen, wir haben eine Liste mit den Namen der Personen {"Alice", "Bob", "Corey", "Dio"} und möchten herausfinden, ob "Dio" auf der Liste steht. Dann sollte Oracle nehmen als eine Eingabe und Ausgabe . Ich verstehe das irgendwie. $1/2(|00\rangle + |01\rangle + |10\rangle + |11\rangle)$ $1/2(|00\rangle + |01\rangle + |10\rangle - |11\rangle)$

Aber müssen wir nicht auch das Wort "Dio" und die Liste {"Alice", "Bob", "Corey", "Dio"} in Oracle eingeben? Wie kann Oracle sonst die Ausgabe zurückgeben? Wird es nicht explizit erwähnt, da Oracle eine Black Box ist und wir nicht darüber nachdenken müssen, wie es implementiert werden soll?

Mein Verständnis von Oracle ist:

Oracle kann erkennen, ob das Wort "Dio" in der Liste enthalten ist.
Zu diesem Zweck verwendet Oracle die überlagerten Quantenzustände als Eingabe, wobei jeder Quantenzustand den Index der Liste darstellt.
Also, Eingabe zu Oracle Mitteln, zu überprüfen , ob das Wort „Dio“ ist in dem Index 0 der Liste und Rückkehr wenn ja und Rückgabe anderweitig. $|00\rangle$ $-|00\rangle$ $|00\rangle$
In unserem Fall Oracle liefert . $1/2(|00\rangle + |01\rangle + |10\rangle - |11\rangle)$
Aber was ist mit der Liste und dem Wort?

algorithm grovers-algorithm oracles Bick
quelle

Obwohl Ihre Frage nicht auf die gleiche Weise formuliert ist, glaube ich, dass sie mehr oder weniger dieselbe ist wie diese: Grovers Algorithmus: Wo ist die Liste?

DaftWullie

Antworten:

$O(\sqrt{N} \cdot F)$ $N$ $F$

$N$ $F$ $O(N)$ $O(\sqrt{N} \cdot F) = O(\sqrt{N} \cdot N) = O(N^{1.5})$ $N^{1.5} > N$

Craig Gidney
quelle

O (\sqrt{N} \log (N))

$O(\sqrt{N}\log(N))$

@DaftWullie Das Problem ist, dass Grover unter Überlagerung eine Suche durchführen muss, und dies erfordert eine Multiplexerschaltung mit N UND-Gattern (oder anderen Nicht-Clifford-Operationen). Ein Quanten-UND-Gatter (dh ein Toffoli) hat nicht vernachlässigbare Kosten bei der Durchführung einer Fehlerkorrektur. Diese Kosten sind technisch auch bei der klassischen Maschine vorhanden (dh RAM hat O (N) UND-Gatter), sie sind in diesem Zusammenhang einfach vernachlässigbar und sogar vermeidbar.

Craig Gidney

Ich verstehe nicht, was du sagst. Könnten Sie eine Frage ausdrücken und beantworten, um die Details zu zeigen? (Ich glaube nicht, dass ich an dieser Stelle eine ausreichend gute Frage

formulieren kann

@DaftWullie Ich denke, die Frage wäre so etwas wie "Wie gebe ich einem Quantencomputer Lesezugriff auf eine klassische Datenbank und wie teuer ist sie?".

Craig Gidney