Algorithme de Grover: quoi entrer dans Oracle?

Je ne sais pas quoi saisir dans Oracle dans l'algorithme de Grover.

N'avons-nous pas besoin de saisir ce que nous recherchons et où trouver ce que nous recherchons pour Oracle, en plus des états quantiques superposés?

Par exemple, supposons que nous ayons une liste de noms de personnes {"Alice", "Bob", "Corey", "Dio"}, et nous voulons savoir si "Dio" est sur la liste. Ensuite, Oracle devrait prendre comme entrée et sortie . Je comprends en quelque sorte cela. $1/2(|00\rangle + |01\rangle + |10\rangle + |11\rangle)$ $1/2(|00\rangle + |01\rangle + |10\rangle - |11\rangle)$

Mais ne faut-il pas aussi saisir le mot "Dio" et la liste {"Alice", "Bob", "Corey", "Dio"} dans Oracle? Sinon, comment Oracle peut-il renvoyer la sortie? N'est-il pas explicitement mentionné, car Oracle est une boîte noire et nous n'avons pas à réfléchir à la façon de l'implémenter?

Ma compréhension d'Oracle est,

Oracle a la capacité de reconnaître si le mot "Dio" est dans la liste.
Pour ce faire, Oracle prend les états quantiques superposés en entrée, où chaque état quantique représente l'index de la liste.
Alors, entrez aux moyens Oracle, vérifier si le mot « Dio » dans l'index 0 de la liste et retour si oui et retour autrement. $|00\rangle$ $-|00\rangle$ $|00\rangle$
$1/2(|00\rangle + |01\rangle + |10\rangle - |11\rangle)$
Mais qu'en est-il de la liste et du mot?

algorithm grovers-algorithm oracles Bick
la source

Bien qu'elle ne soit pas formulée de la même manière, je pense que votre question est plus ou moins la même que celle-ci: algorithme de Grover: où est la liste?

DaftWullie

Réponses:

$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
la source

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

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

@DaftWullie Le problème est que Grover doit effectuer une recherche sous superposition, ce qui nécessite un circuit multiplexeur avec des portes N ET (ou d'autres opérations non Clifford). Une porte ET quantique (c'est-à-dire un Toffoli) a un coût non négligeable lors de la correction d'erreurs. Ce coût est techniquement également présent dans la machine classique (c'est-à-dire que la RAM a des portes O (N) ET), il se trouve juste être négligeable et même évitable dans ce contexte.

Craig Gidney

Je ne comprends pas ce que tu dis. Pourriez-vous exprimer une question et y répondre, en montrer les détails? (Je ne pense pas pouvoir formuler une assez bonne question à ce stade)

DaftWullie

@DaftWullie Je pense que la question serait quelque chose comme "comment donner à un ordinateur quantique un accès en lecture à une base de données classique et combien coûte-t-il".

Craig Gidney