Pourquoi un qubit oracle est-il nécessaire dans l'algorithme de Grover?

Je suis un peu confus quant à la nécessité d'un qubit oracle dans l'algorithme de Grover.

Ma question est, cela dépend-il de la façon dont vous implémentez votre oracle, que vous ayez besoin d'un orbit qubit ou non? Ou, y at-il une raison pour un qubit oracle? (comme, il existe des problèmes qui ne peuvent pas être résolus sans qubit oracle, ou il est plus facile de penser au problème avec un qubit oracle, ou c'est une convention, etc.)

De nombreuses ressources présentent l'algorithme de Grover avec un qubit oracle, mais j'ai trouvé qu'il y a des cas où vous n'avez pas besoin d'un qubit oracle.

Par exemple, voici deux implémentations de l'algorithme de Grover dans le simulateur IBM Q. L'un utilise un qubit oracle, et l'autre non. Dans les deux cas, j'aimerais trouver | 11> à partir d'un espace de | 00>, | 01>, | 10> et | 11>. Dans les deux cas, oracle retourne avec succès | 11> à - | 11>.

・ Avec un qubit oracle ( Lien vers le simulateur IBM Q )

・ Sans qubit oracle ( Lien vers le simulateur IBM Q )

algorithm grovers-algorithm Bick
la source

Réponses:

U | x ⟩ | y ⟩ = | x ⟩ | y \oplus f (x) ⟩,

$U|x\rangle|y\rangle=|x\rangle|y\oplus f(x)\rangle,$

f (x)

$f(x)$

x

$x$

(| 0 ⟩ - | 1 ⟩) / \sqrt{2}

$(|0\rangle-|1\rangle)/\sqrt{2}$

\tilde{U} | x ⟩ = (- 1)^{f (x)} | x ⟩

$\tilde U|x\rangle=(-1)^{f(x)}|x\rangle$

$x$ $\tilde U$ $U$

DaftWullie
la source

Il est en fait très facile d'éviter le qubit supplémentaire, en supposant qu'il ne soit pas utilisé comme espace de travail pendant le calcul Oracle. Trouvez tous les CNOT sur le qubit supplémentaire et remplacez-les par une porte Z sur le contrôle du CNOT. De même, remplacez CCNOTs sur le qubit supplémentaire par un CZ entre les deux commandes du CCNOT. Etc.

Craig Gidney

@CraigGidney C'est un bon point, bien que je pense qu'il y ait plus d'hypothèses intégrées dans votre déclaration (la rendant non générique, même si la majorité des cas que nous connaissons les satisfont): (1) il ne devrait pas y avoir d'ancillas intermédiaires utilisées pendant l'évaluation de la fonction; (2) le circuit de l'oracle doit être décomposé en un ensemble de portes où les seules portes multi-qubit agissant sur le qubit oracly sont des notations (multi) contrôlées qui ciblent le qubit oracle; (3) aucune autre porte ne peut agir sur le qubit oracle (c'est-à-dire que vous ne pouvez pas simplement inverser les c-nots agissant de la mauvaise façon en utilisant des Hadamards sur les entrées et les sorties).

DaftWullie

C'est exact.

Craig Gidney