Construction d'Oracle pour l'algorithme de Grover

Dans "Quantum Computation and Quantum Information" de Mike et Ike, l'algorithme de Grover est expliqué en détail. Cependant, dans le livre, et dans toutes les explications que j'ai trouvées en ligne pour l'algorithme de Grover, il ne semble pas y avoir de mention de la façon dont l'Oracle de Grover est construit, à moins que nous ne sachions déjà quel état nous recherchons, ce qui va à l'encontre du but de la algorithme. Plus précisément, ma question est la suivante: étant donné certains f (x) tels que pour une valeur x, f (x) = 1, mais pour tous les autres, f (x) = 0, comment construit-on un oracle qui nous tirera de notre état initial arbitraire | x> | y> à | x> | y + f (x)>? Un maximum de détails explicites (peut-être un exemple?) Serait grandement apprécié. Si une telle construction pour toute fonction arbitraire est possible avec Hadamard, Pauli ou d'autres portes quantiques standard,

quantum-computing quantum-information oracles search-problem black-box Volonté
la source

"Ici, il ne semble pas être fait mention de la façon dont Oracle de Grover est construit, à moins que nous ne sachions déjà quel état nous recherchons, ce qui va à l'encontre du but de l'algorithme." ... "L'Oracle de Grover" est le problème à résoudre. Vous ne le construisez pas. On vous donne (accès oracle à) et on vous demande d'effectuer un calcul pour découvrir la valeur. Si cela aide, faites comme si je construis l'oracle, puis demandez- vous de résoudre le problème. (Notez également que la lecture / l'écriture / la préparation d'une base de données de

éléments prend plus de temps que l'exécution de Grover

N

$N$

Algorithme

time.)

\sqrt{N}

$\sqrt{N}$

Daniel Apon

Mais que se passe-t-il si au lieu de recevoir l'oracle, on nous donne un f (x)? Imaginez que nous résolvions un problème 3-SAT et que nous voulions utiliser Grover pour accélérer la solution. Nous connaissons le f (x) en question (les clauses de vérité 3-SAT), mais nous ne savons pas nécessairement quelle chaîne de bits x donnera un vrai résultat lorsqu'il est branché sur le 3-SAT. Ne doit-il pas y avoir un moyen de construire un oracle à partir de la fonction 3-SAT pour trouver la chaîne de bits correcte? S'il n'y a pas, et c'est comme vous le suggérez, quelque chose à fournir par quelqu'un d'autre, l'algorithme de Grover semble plutôt artificiel, simplement un exercice qui vous est donné.

Will

Réponses:

L'oracle n'est fondamentalement qu'une implémentation du prédicat auquel vous souhaitez rechercher une solution satisfaisante.

Par exemple, supposons que vous ayez un problème à 3 sat:

(¬x1 ∨ ¬x3 ∨ ¬x4) ∧
    (x2 ∨ x3 ∨ ¬x4) ∧
    (x1 ∨ ¬x2 ∨ x4) ∧
    (x1 ∨ x3 ∨ x4) ∧
    (¬x1 ∨ x2 ∨ ¬x3)

Ou, sous forme de tableau, chaque ligne étant une clause à 3, x signifiant "cette variable false", o signifiant "cette variable true" et espace signifiant "pas dans la clause":

1 2 3 4
-------
x   x x
  o o x
o x   o
x o x

Faites maintenant un circuit qui calcule si l'entrée est une solution, comme ceci:

Maintenant, pour transformer votre circuit en un oracle, frappez le bit de sortie avec une porte Z et calculez les ordures que vous avez faites (c'est-à-dire exécutez le circuit de calcul dans l'ordre inverse):

C'est tout ce qu'on peut en dire. Calculez le prédicat, frappez le résultat avec un Z, calculez le prédicat. Voilà un oracle.

Répétez les étapes de diffusion avec les étapes oracle, et vous avez une recherche de grover :

... bien que vous devriez probablement choisir un exemple avec moins de solutions, la progression est donc progressive (au lieu de tourner le long du plan état de départ-solution-état de plus de 90 degrés par étape comme mon exemple).

Craig Gidney
la source

Merci, c'était extrêmement utile. Incroyablement clair, a répondu à tout ce que je demandais (et a même utilisé des portes quantiques communes!) > indiquer les qubits via Hadamards (c'est-à-dire y a-t-il un avantage)? Aussi, quelle opération est-ce pour vos étapes de diffusion? On dirait un X contrôlé, mais utilisez-vous les commandes | 1> ou | 0> comme commandes?

Will

(\frac{1}{\sqrt{2}} | 0 ⟩ - \frac{1}{\sqrt{2}} | 1 ⟩)^{\otimes n}

$(\frac{1}{\sqrt{2}} |0\rangle - \frac{1}{\sqrt{2}} |1\rangle)^{\otimes n}$

Fantastique réponse, et merci pour le lien vers algassert.com/quirk !

Frédéric Grosshans