Comment le Grover-Algorithm est-il appliqué à une base de données?

Question

Je souhaite utiliser l'algorithme Grover pour rechercher dans une base de données non triée un élément . Maintenant, la question se pose, comment puis-je initialiser l'index et la valeur de la base de données avec les qubits?$x$

Exemple

• Disons que j'ai qubits. Ainsi, valeurs classiques peuvent être mappées.$4$$2 ^ 4 = 16$
• Ma base de données non triée contient les éléments suivants: .$d$$d [\text{Value}] = [3,2,0,1]$
• Je veux rechercher .$x = 2_d = 10_b = |10\rangle$
• Mon approche: indexer la base de données avec . Registres et pour l'index et registres et pour la valeur. Ensuite, appliquez l'algorithme Grover uniquement aux registres et . Cela peut-il être réalisé? Y a-t-il une autre approche?$d$$d [(\text{Index, Value})] = [(0,3), (1,2), (2,0), (3,1)]$$0$$1$$2$$3$$2$$3 (\text{Value})$

Ce que j'ai déjà implémenté ( sur GitHub )

Le "Grover-Algorithm with 2-, 3-, 4-Qubits", mais ce qu'il fait est simple: les bits sont initialisés avec , l'oracle marquera ma solution (qui est juste un nombre comme ), la partie Grover augmentera la probabilité de l'élément sélectionné et diminuera toutes les autres probabilités, puis les qubits seront lus en étant mappés sur les bits classiques. Nous laissons ce processus s'exécuter plusieurs fois de suite et obtenons ainsi une distribution de probabilité, où la probabilité la plus élevée a notre élément recherché .$|0\rangle$$x$$2_d = 10_b$$x$$x$

La sortie est toujours la même que celle marquée dans l'oracle. Comment puis-je générer plus d'informations à partir de la sortie, que je ne connais pas au moment où j'ai construit l'oracle?

J'ai également travaillé sur ce problème. En tant que débutant et programmeur classique (c'est-à-dire que je ne parle pas de mécanique quantique), il est difficile de comprendre les concepts sans des exemples complets. J'ai travaillé avec l' exemple de recherche de base de données Microsoft Q # . Il recherche simplement un index / clé spécifique dans la base de données, ce qui n'est pas très utile. J'ai développé cet échantillon pour rechercher une liste de valeurs dans une base de données et retourner la clé correspondante.

Comme dans votre exemple, il existe un "registre de clé" à deux qubits pour les index et un registre à deux qubits séparé pour les valeurs. Il existe également un cinquième "qubit marqué" qui provient de l'échantillon de Microsoft, pour indiquer quand la valeur souhaitée est trouvée. Les clés et les valeurs sont associées via l'intrication. Cela est mieux démontré avec un circuit. Cliquez ici pour voir le circuit Quirk réel .

Notez que ce circuit ne contient que l'oracle. Il n'implémente pas tout l'algorithme de Grover.

• Les deux qubits supérieurs sont le registre de clé, les deux suivants sont le registre de valeurs et le qubit inférieur est le qubit marqué.
• La première section place le registre de clé dans une superposition uniforme en utilisant des portes Haramard, comme requis par l'algorithme de Grover.
• La deuxième section est l'endroit où les clés sont associées aux valeurs via l'intrication. Chaque clé est emmêlée avec une valeur correspondante dans le registre de valeurs en appliquant des portes X (anti) contrôlées. Ainsi, lorsque le registre de clé est 0, le registre de valeur est défini sur 3. Lorsque la clé est 1, la valeur est définie sur 2, etc.
• La troisième section du circuit est l'oracle de recherche. Le registre de valeurs est enchevêtré avec le qubit marqué. Dans cet exemple, la valeur souhaitée est 2. Lorsque le registre de valeurs contient 2, le qubit marqué sera défini sur 1.
• L'algorithme de Grover examine le registre des clés et le qubit marqué. L'oracle de recherche examine le registre de valeurs et définit le qubit marqué. Cela entraînera l'amplification de la clé 1 lorsque la valeur est 2.

Il est intéressant de noter que les clés et les valeurs ne sont pas stockées dans les qubits, mais plutôt dans le circuit / programme. On pourrait dire que ce n'est pas vraiment une base de données en soi. Cela ressemble plus à une instruction switch / case, mais qui peut s'exécuter sur une superposition de valeurs.

Pour plus de détails, mises en garde et code Q #, consultez mon référentiel GitHub .

EDIT: quelque chose que je comprends mieux depuis la réponse ... vous devez inverser / défaire le circuit dans le cadre de chaque itération. Dans le code Q #, l'appel Adjoint StatePreparationOracle () dans l'opération ReflectStart () gère cela, donc je n'ai pas eu à le faire explicitement. Je ne sais pas si Qiskit a une fonctionnalité similaire. Si j'ai fait la traduction correctement, voici un circuit complet pour l'exemple ci-dessus.

Lors de la présentation de l'algorithme de Grover appliqué à la recherche dans une base de données, il est supposé que l'Oracle a accès aux éléments de la liste classique. C'est pourtant une hypothèse très forte et c'est pourquoi nous représentons cela par un sélecteur contrôlé utilisant CNOT / Toffolis d'un indice représentant simplement cette opération (comme le circuit de Toffoli dans le cas ).$n=4$

Vous mentionnez l'approche du calcul des valeurs dans un autre registre: Vous supposez à nouveau qu'on vous donne un oracle pour le faire et efficacement (une façon simple est de contrôler-NON mais vous devez le faire pour chaque index / valeur donc pas très efficace). Dans ce cas, l'oracle serait la fonction dans un format de circuit quantique (encore une fois un sélecteur contrôlé), marquant cet état et continuant avec les itérations de Grover.

Je pense qu'il vaut mieux penser à l'algorithme de recherche quantique comme optimisant une fonction, au lieu de chercher dans une liste / base de données. Voici un article sur lequel j'ai travaillé où la recherche quantique est utilisée pour résoudre un problème de maximisation combinatoire si vous souhaitez approfondir votre compréhension de l'algorithme.

Vous devez également convertir l'oracle pour contenir la base de données, par conséquent, l'Oracle général (inversion de phase) aura deux sous-oracles jetez un œil à la figure.

Le premier sous-oracle qui doit être préparé est le circuit de mémoire, contrairement à QRAM qui stocke des données quantiques (état) dans son corps, ce circuit de mémoire (tableau) est prêt à stocker uniquement des informations classiques dans sa trame. Un exemple d'un tel type de circuit qui stocke un tableau de binaires [010, 110, 100, 011] est affiché ci-dessous: Pour plus d'informations, lisez cet article .