Comment l'oracle dans l'algorithme de recherche de Grover est-il implémenté?

L'algorithme de recherche de Grover fournit une accélération quadratique prouvable pour la recherche de base de données non triée. L'algorithme est généralement exprimé par le circuit quantique suivant:

Dans la plupart des représentations, une partie cruciale du protocole est la "porte oracle" , qui effectue "par magie" l'opération . On ignore cependant souvent combien il serait difficile de réaliser une telle porte. En effet, il pourrait sembler que cette utilisation d'un "oracle" n'est qu'un moyen de balayer les difficultés sous le tapis.$U_\omega$$|x\rangle\mapsto(-1)^{f(x)}|x\rangle$

Comment savoir si une telle opération oraculaire est effectivement réalisable? Et si oui, quelle est sa complexité (par exemple en termes de complexité de décomposition des portes)?

La fonction est simplement une fonction booléenne arbitraire d'une chaîne de bits: . Pour les applications pour briser la cryptographie, telles que [1] , [2] ou [3] , il ne s'agit pas en fait d'une «recherche de base de données», ce qui nécessiterait de stocker la base de données entière en tant que circuit quantique, mais plutôt une fonction telle que$f$$f\colon \{0,1\}^n \to \{0,1\}$

$$\begin{equation*} x \mapsto \begin{cases} 1, & \text{if $\operatorname{SHA-256}(x) = y$;} \\ 0, & \text{otherwise,} \end{cases} \end{equation*}$$

pour fixe , qui n'a pas de structure, nous pouvons exploiter pour une recherche classique, contrairement, disons, à la fonction$y$

$$\begin{equation*} x \mapsto \begin{cases} 1, & \text{if $2^x \equiv y \pmod{2^{2048} - 1942289}$}, \\ 0, & \text{otherwise}, \end{cases} \end{equation*}$$

qui a une structure qui peut être exploitée pour l'inverser plus rapidement même sur un ordinateur classique.

La question du coût particulier ne peut pas être répondu en général parce que peut être n'importe quel circuit - il s'agit juste de faire un circuit quantique à partir d'un circuit classique . Mais généralement, comme dans l'exemple ci-dessus, la fonction est très bon marché à évaluer sur un ordinateur classique, donc elle ne devrait pas représenter une charge particulièrement onéreuse pour un ordinateur quantique pour lequel tout le reste de l'algorithme de Grover est dans votre budget.$f$$f$

Le seul coût général au-dessus de est une porte NON conditionnelle supplémentaire où est xor, et un qubit auxiliaire supplémentaire pour lui. En particulier, si nous avons un circuit construit à partir de et du circuit pour , puis si nous l'appliquons à avec un qubit auxiliaire initialement dans l'état où$f$

$$C\colon \left|a\right> \left|b\right> \to \left|a\right> \left|a \oplus b\right>$$ $\oplus$ $$F\colon \left|x\right> \left|a\right> \lvert\text{junk}\rangle \mapsto \left|x\right> \left|a \oplus f(x)\right> \lvert\text{junk}'\rangle$$ $C$$f$$\left|x\right>$$\left|-\right> = H\left|1\right> = (1/\sqrt{2})(\left|0\right> - \left|1\right>)$$H$ est une porte Hadamard, nous obtenons

$$\begin{align*} F\left|x\right> \left|-\right> \lvert\text{junk}\rangle &= \frac{1}{\sqrt{2}}\bigl( F\left|x\right> \left|0\right> \lvert\text{junk}\rangle - F\left|x\right> \left|1\right> \lvert\text{junk}\rangle \bigr) \\ &= \frac{1}{\sqrt{2}}\bigl( \left|x\right> \left|f(x)\right> \lvert\text{junk}'\rangle - \left|x\right> \left|1 \oplus f(x)\right> \lvert\text{junk}'\rangle \bigr). \end{align*}$$

Si alors , donc en simplifiant on obtient alors que si alors , donc et donc en général$f(x) = 0$$1 \oplus f(x) = 1$

$$F\left|x\right> \left|-\right> \lvert\text{junk}\rangle = \left|x\right> \left|-\right> \lvert\text{junk}'\rangle,$$ $f(x) = 1$$1 \oplus f(x) = 0$ $$F\left|x\right> \left|-\right> \lvert\text{junk}\rangle = -\left|x\right> \left|-\right> \lvert\text{junk}'\rangle,$$ $$F\left|x\right> \left|-\right> \lvert\text{junk}\rangle = (-1)^{f(x)} \left|x\right> \left|-\right> \lvert\text{junk}'\rangle.$$

Eh bien, l'article original de Grover, "La mécanique quantique aide à rechercher une aiguille dans une botte de foin", indique clairement qu'il suppose que le C (S) peut être évalué en un temps constant. La recherche de Grover ne se préoccupe pas de l'implémentabilité, mais de la réduction polynomiale de ce qu'on appelle une complexité de requête (combien de fois vous consultez l'oracle, comme une base de données classique)

En fait, le concept d' oracle en informatique a été proposé par Alan Turing pour décrire des constructions pour lesquelles une description sur un UTM pourrait ne pas être réalisable (Wikipedia). Il est en quelque magique de sens.

Mais bien sûr, pour revenir à votre question, comment pouvons-nous alors réellement faire le circuit pour l'algorithme de recherche Grover (ou tout autre oraculaire)? Avons-nous besoin de connaître la réponse à l'avance pour rechercher le résultat? Eh bien, dans un certain sens, vous devez. C'est exactement ce que les améliorations intelligentes de la recherche Grover essaient de faire, de sorte que nous n'avons pas besoin de connaître la réponse exacte à l'avance, mais certaines propriétés de celle-ci. Permettez-moi d'illustrer avec un exemple.

Pour le problème de reconnaissance de formes à l'aide de la recherche de Grover, si j'ai 4 configurations sur 2 qubits (00, 01, 10, 11) et que je veux marquer et amplifier 11, la diagonale de mon oracle unitaire devrait ressembler à (1,1,1 , -1) pour prendre en charge le déphasage pi de la solution. Donc, pour cette mise en œuvre simple, pour la construction de l'unité, vous devez connaître la réponse complète à l'avance.

Une amélioration intelligente de l'achèvement du modèle si elle est donnée dans le document "Quantum pattern matching" par Mateas et Omar. En substance, il construit autant d'oracles fixes qu'il y a d'alphabets dans l'ensemble. Donc, pour notre chaîne binaire, il y aura un oracle qui marque tous les 1 et un autre qui marque tous les 0. Les oracles sont invoqués conditionnellement en fonction de ce que je veux rechercher. Si je veux rechercher 11, j'appelle oracle 1 sur le LSqubit et oracle 1 à nouveau sur le MSqubit. Par le premier oracle, j'amplifierais les états (01, 11), c'est-à-dire les états avec LSQ comme 1, et dans le 2ème appel, il amplifierait (10, 11). Donc, comme vous le voyez, 11 est le seul état qui est amplifié deux fois, se terminant par une probabilité de mesure plus élevée. Bien que le circuit quantique compilé changerait en fonction de mon modèle de recherche d'entrée, une description de haut niveau de l'algorithme quantique reste la même. Vous pouvez considérer les oracles comme des appels de fonction basés sur une casse de commutation de l'ensemble d'alphabets invoqué pour chaque caractère de la chaîne de recherche.