{ "cells": [ { "cell_type": "markdown", "id": "17463a96", "metadata": {}, "source": [ "---\n", "title: \"L'algorithme Deutsch-Jozsa\"\n", "description: \"Cours gratuit sur l' IBM, l'information quantique et le calcul quantique\"\n", "---\n", "\n", "\n", "\n", "# L'algorithme Deutsch-Jozsa\n", "\n", "L'algorithme de Deutsch est plus performant que tous les algorithmes classiques pour un problème d'interrogation, mais l'avantage est assez modeste : une interrogation contre deux.\n", "L'algorithme de Deutsch-Jozsa étend cet avantage - et, en fait, il peut être utilisé pour résoudre deux problèmes d'interrogation différents.\n", "\n", "Voici une description du circuit quantique de l'algorithme de Deutsch-Jozsa.\n", "Une étape supplémentaire de post-traitement classique, non illustrée dans la figure, peut également être nécessaire en fonction du problème spécifique à résoudre.\n", "\n", "![Algorithme Deutsch-Jozsa](https://quantum.cloud.ibm.com/learning/images/courses/fundamentals-of-quantum-algorithms/quantum-query-algorithms/Deutsch-Jozsa.svg)\n", "\n", "Bien entendu, nous n'avons pas encore discuté des problèmes que cet algorithme permet de résoudre, ce qui sera fait dans les deux sections suivantes.\n", "\n", "\n", "\n", "## Le problème Deutsch-Jozsa\n", "\n", "Nous commencerons par le problème de requête que l'algorithme de Deutsch-Jozsa était censé résoudre à l'origine, connu sous le nom de *problème de Deutsch-Jozsa*.\n", "\n", "La fonction d'entrée pour ce problème prend la forme $f:\\Sigma^n \\rightarrow \\Sigma$ pour un entier positif arbitraire $n.$ Comme pour le problème de Deutsch, la tâche consiste à produire $0$ si $f$ est constant et $1$ si $f$ est équilibré, ce qui signifie à nouveau que le nombre de chaînes d'entrée sur lesquelles la fonction prend la valeur $0$ est égal au nombre de chaînes d'entrée sur lesquelles la fonction prend la valeur $1$.\n", "\n", "Remarquez que, lorsque $n$ est plus grand que $1,$, il existe des fonctions de la forme $f:\\Sigma^n \\rightarrow \\Sigma$ qui ne sont ni constantes ni équilibrées.\n", "Par exemple, la fonction $f:\\Sigma^2\\rightarrow\\Sigma$ définie comme\n", "\n", "$$\n", "\\begin{aligned}\n", "f(00) & = 0 \\\\\n", "f(01) & = 0 \\\\\n", "f(10) & = 0 \\\\\n", "f(11) & = 1\n", "\\end{aligned}\n", "$$\n", "\n", "n'entre dans aucune de ces deux catégories.\n", "Pour le problème Deutsch-Jozsa, nous ne nous préoccupons tout simplement pas des fonctions de ce type - elles sont considérées comme des entrées \"sans importance\".\n", "En d'autres termes, pour ce problème, nous avons la *promesse* que $f$ est soit constant, soit équilibré.\n", "\n", "
\n", " Entrée : une fonction $f:\\{0,1\\}^n\\rightarrow\\{0,1\\}$ \\ Promesse : $f$ est soit constant, soit équilibré \\ Sortie : $0$ si $f$ est constant, $1$ si $f$ est équilibré\n", "
\n", "\n", "L'algorithme de Deutsch-Jozsa, grâce à sa requête unique, résout ce problème de la manière suivante :\n", "si chacun des résultats de mesure de l' $n$ est de type « $0,$ », alors la fonction $f$ est constante;\n", "et dans le cas contraire, si au moins l'un des résultats de mesure est de type « $1,$ », alors la fonction $f$ est équilibrée.\n", "On peut également dire que le circuit décrit ci-dessus est suivi d'une étape classique de post-traitement au cours de laquelle on calcule la fonction OU des résultats de mesure afin de produire le bit de sortie du problème de Deutsch-Jozsa.\n", "\n", "\n", "\n", "### Analyse algorithmique\n", "\n", "Pour analyser les performances de l'algorithme de Deutsch-Jozsa pour le problème de Deutsch-Jozsa, il est utile de commencer par réfléchir à l'action d'une seule couche de portes de Hadamard.\n", "Une opération de Hadamard peut être exprimée sous la forme d'une matrice de la manière habituelle,\n", "\n", "$$\n", "H = \\begin{pmatrix}\n", "\\frac{1}{\\sqrt{2}} & \\frac{1}{\\sqrt{2}} \\\\[2mm]\n", "\\frac{1}{\\sqrt{2}} & -\\frac{1}{\\sqrt{2}}\n", "\\end{pmatrix},\n", "$$\n", "\n", "mais nous pouvons également exprimer cette opération en termes d'action sur les états de base standard :\n", "\n", "$$\n", "\\begin{aligned}\n", "H \\vert 0\\rangle & = \\frac{1}{\\sqrt{2}} \\vert 0 \\rangle + \\frac{1}{\\sqrt{2}} \\vert 1 \\rangle\\\\[3mm]\n", "H \\vert 1\\rangle & = \\frac{1}{\\sqrt{2}} \\vert 0 \\rangle - \\frac{1}{\\sqrt{2}} \\vert 1 \\rangle.\n", "\\end{aligned}\n", "$$\n", "\n", "Ces deux équations peuvent être combinées en une seule formule,\n", "\n", "$$\n", "H \\vert a \\rangle = \\frac{1}{\\sqrt{2}} \\vert 0 \\rangle + \\frac{1}{\\sqrt{2}} (-1)^a \\vert 1 \\rangle\n", "= \\frac{1}{\\sqrt{2}} \\sum_{b\\in\\{0,1\\}} (-1)^{ab} \\vert b\\rangle,\n", "$$\n", "\n", "ce qui est vrai pour les deux choix de $a\\in\\Sigma.$\n", "\n", "Supposons maintenant qu'au lieu d'un seul qubit, nous ayons $n$ qubits, et qu'une opération de Hadamard soit effectuée sur chacun d'entre eux.\n", "L'opération combinée sur les qubits $n$ est décrite par le produit tensoriel $H\\otimes \\cdots \\otimes H$ ( $n$ fois), que nous écrivons $H^{\\otimes n}$ par souci de concision et de clarté.\n", "En utilisant la formule ci-dessus, puis en la développant et en la simplifiant, nous pouvons exprimer l'action de cette opération combinée sur les états de base standard des qubits $n$ de la manière suivante :\n", "\n", "$$\n", "\\begin{aligned}\n", " & H^{\\otimes n} \\vert x_{n-1} \\cdots x_1 x_0 \\rangle \\\\\n", " & \\qquad = \\bigl(H \\vert x_{n-1} \\rangle \\bigr) \\otimes \\cdots \\otimes \\bigl(H \\vert x_{0} \\rangle \\bigr) \\\\\n", " & \\qquad = \\Biggl( \\frac{1}{\\sqrt{2}} \\sum_{y_{n-1}\\in\\Sigma} (-1)^{x_{n-1} y_{n-1}} \\vert y_{n-1} \\rangle \\Biggr)\n", " \\otimes \\cdots \\otimes\n", " \\Biggl( \\frac{1}{\\sqrt{2}} \\sum_{y_{0}\\in\\Sigma} (-1)^{x_{0} y_{0}} \\vert y_{0} \\rangle \\Biggr) \\\\\n", " & \\qquad = \\frac{1}{\\sqrt{2^n}} \\sum_{y_{n-1}\\cdots y_0 \\in \\Sigma^n}\n", " (-1)^{x_{n-1}y_{n-1} + \\cdots + x_0 y_0} \\vert y_{n-1} \\cdots y_0 \\rangle.\n", "\\end{aligned}\n", "$$\n", "\n", "Ici, d'ailleurs, nous écrivons les chaînes binaires de longueur $n$ comme $x_{n-1}\\cdots x_0$ et $y_{n-1}\\cdots y_0,$ en suivant la convention d'indexation de Qiskit.\n", "\n", "Cette formule nous fournit un outil utile pour analyser le circuit quantique ci-dessus.\n", "Après l'exécution de la première couche de portes de Hadamard, l'état des qubits $n+1$ (y compris le qubit le plus à gauche/le plus en bas, qui est traité séparément du reste) est le suivant\n", "\n", "$$\n", "\\bigl( H \\vert 1 \\rangle \\bigr) \\bigl( H^{\\otimes n} \\vert 0 \\cdots 0 \\rangle \\bigr)\n", "= \\vert - \\rangle \\otimes \\frac{1}{\\sqrt{2^n}} \\sum_{x_{n-1}\\cdots x_0 \\in \\Sigma^n} \\vert x_{n-1} \\cdots x_0 \\rangle.\n", "$$\n", "\n", "Lorsque l'opération $U_f$ est effectuée, cet état est transformé en\n", "\n", "$$\n", "\\vert - \\rangle \\otimes \\frac{1}{\\sqrt{2^n}}\n", "\\sum_{x_{n-1}\\cdots x_0 \\in \\Sigma^n} (-1)^{f(x_{n-1}\\cdots x_0)} \\vert x_{n-1} \\cdots x_0 \\rangle\n", "$$\n", "\n", "par le même phénomène de retour de phase que nous avons vu dans l'analyse de l'algorithme de Deutsch.\n", "\n", "Ensuite, la deuxième couche de portes de Hadamard est exécutée, ce qui (selon la formule ci-dessus) transforme cet état en\n", "\n", "$$\n", "\\vert - \\rangle \\otimes \\frac{1}{2^n}\n", "\\sum_{x_{n-1}\\cdots x_0 \\in \\Sigma^n}\n", "\\sum_{y_{n-1}\\cdots y_0 \\in \\Sigma^n}\n", "(-1)^{f(x_{n-1}\\cdots x_0) + x_{n-1}y_{n-1} + \\cdots + x_0 y_0}\n", "\\vert y_{n-1} \\cdots y_0 \\rangle.\n", "$$\n", "\n", "Cette expression semble quelque peu compliquée, et il n'est pas possible de tirer des conclusions sur les probabilités d'obtenir différents résultats de mesure sans en savoir plus sur la fonction $f.$\n", "\n", "Heureusement, tout ce que nous avons besoin de savoir, c'est la probabilité que chacun des résultats de mesure soit $0$ - car c'est la probabilité que l'algorithme détermine que $f$ est constant.\n", "Cette probabilité a une formule simple.\n", "\n", "$$\n", "\\Biggl\\vert\n", "\\frac{1}{2^n}\n", "\\sum_{x_{n-1}\\cdots x_0 \\in \\Sigma^n}\n", "(-1)^{f(x_{n-1}\\cdots x_0)}\n", "\\Biggr\\vert^2\n", "= \\begin{cases}\n", "1 & \\text{if $f$ is constant}\\\\[1mm]\n", "0 & \\text{if $f$ is balanced}\n", "\\end{cases}\n", "$$\n", "\n", "Il convient de noter que ces valeurs correspondent à la probabilité de mesurer l'état\n", "$\\vert 0^{\\otimes n} \\rangle$, et non pas directement au bit de sortie classique final du\n", "problème de Deutsch-Jozsa. L'algorithme renvoie « $0$ » lorsque tous les résultats de mesure\n", "sont « $0$ » (ce qui indique que « $f$ » est constant), et renvoie « $1$ » dans le cas contraire\n", "(ce qui indique que « $f$ » est équilibré).\n", "\n", "Plus précisément, si $f$ est constant, alors soit $f(x_{n-1}\\cdots x_0) = 0$ pour chaque chaîne de caractères $x_{n-1}\\cdots x_0,$ auquel cas la valeur de la somme est $2^n,$ ou $f(x_{n-1}\\cdots x_0) = 1$ pour chaque chaîne de caractères $x_{n-1}\\cdots x_0,$ auquel cas la valeur de la somme est $-2^n.$ En divisant par $2^n$ et en prenant le carré de la valeur absolue, on obtient $1.$\n", "\n", "Si, en revanche, $f$ est équilibré, alors $f$ prend la valeur $0$ sur la moitié des chaînes $x_{n-1}\\cdots x_0$ et la valeur $1$ sur l'autre moitié, de sorte que les termes $+1$ et $-1$ de la somme s'annulent et qu'il nous reste la valeur $0.$\n", "\n", "Nous concluons que l'algorithme fonctionne correctement à condition que la promesse soit tenue.\n", "\n", "\n", "\n", "### Difficulté classique\n", "\n", "L'algorithme Deutsch-Jozsa fonctionne à chaque fois, nous donnant toujours la bonne réponse lorsque la promesse est respectée, et ne nécessite qu'une seule requête.\n", "Quelle est la comparaison avec les algorithmes de requête classiques pour le problème Deutsch-Jozsa?\n", "\n", "Premièrement, tout algorithme classique *déterministe* qui résout correctement le problème de Deutsch-Jozsa doit effectuer un nombre exponentiel de requêtes : $2^{n-1} + 1$ requêtes sont nécessaires dans le pire des cas.\n", "Le raisonnement est le suivant : si un algorithme déterministe interroge $f$ sur $2^{n-1}$ ou moins de chaînes différentes et obtient la même valeur de fonction à chaque fois, les deux réponses sont toujours possibles.\n", "La fonction peut être constante ou équilibrée mais, par malchance, les requêtes renvoient toutes la même valeur de fonction.\n", "\n", "La deuxième possibilité peut sembler improbable, mais les algorithmes déterministes n'ont pas de caractère aléatoire ou incertain et échouent donc systématiquement sur certaines fonctions.\n", "Les algorithmes quantiques présentent donc un avantage significatif sur les algorithmes classiques à cet égard.\n", "\n", "Il y a toutefois un hic : les algorithmes classiques *probabilistes* peuvent résoudre le problème Deutsch-Jozsa avec une probabilité très élevée en utilisant seulement quelques requêtes.\n", "En particulier, si nous choisissons simplement quelques chaînes différentes de longueur $n$ de manière aléatoire et que nous interrogeons $f$ sur ces chaînes, il est peu probable que nous obtenions la même valeur de fonction pour toutes ces chaînes lorsque $f$ est équilibré.\n", "\n", "$x^1,\\ldots,x^k \\in \\Sigma^n$ Plus précisément, si nous choisissons les chaînes d'entrée $k$ uniformément au hasard, évaluons $f(x^1),\\ldots,f(x^k),$ et répondons $0$ si les valeurs de la fonction sont toutes identiques, et $1$ dans le cas contraire, nous aurons toujours raison lorsque $f$ est constant, et tort dans le cas où $f$ est équilibré avec une probabilité juste $2^{-k + 1}.$ Si nous prenons $k = 11,$ par exemple, cet algorithme répondra correctement avec une probabilité supérieure à $99.9$ %.\n", "\n", "Pour cette raison, nous avons encore un avantage assez modeste des algorithmes quantiques par rapport aux algorithmes classiques, mais il s'agit néanmoins d'un avantage quantifiable représentant une amélioration par rapport à l'algorithme de Deutsch.\n", "\n" ] }, { "cell_type": "markdown", "id": "83b0e8b5", "metadata": {}, "source": [ "\n", "\n", "## Deutsch-Jozsa avec Qiskit\n", "\n" ] }, { "cell_type": "code", "execution_count": 12, "id": "c7839d8f", "metadata": {}, "outputs": [], "source": [ "from qiskit import QuantumCircuit\n", "from qiskit_aer import AerSimulator\n", "import numpy as np" ] }, { "cell_type": "markdown", "id": "59738a5c", "metadata": {}, "source": [ "Pour implémenter l'algorithme de Deutsch-Jozsa dans Qiskit, nous commencerons par définir une fonction `dj_query` qui génère un circuit quantique implémentant une porte d'interrogation, pour une fonction choisie au hasard satisfaisant la promesse du problème de Deutsch-Jozsa.\n", "Avec une chance sur deux, la fonction est constante, et avec une variation sur deux, la fonction est équilibrée.\n", "Pour chacune de ces deux possibilités, la fonction est sélectionnée uniformément parmi les fonctions de ce type.\n", "L'argument est le nombre de bits d'entrée de la fonction.\n", "\n" ] }, { "cell_type": "code", "execution_count": 13, "id": "b39e7af8", "metadata": {}, "outputs": [], "source": [ "def dj_query(num_qubits):\n", " # Create a circuit implementing for a query gate for a random function\n", " # satisfying the promise for the Deutsch-Jozsa problem.\n", "\n", " qc = QuantumCircuit(num_qubits + 1)\n", "\n", " if np.random.randint(0, 2):\n", " # Flip output qubit with 50% chance\n", " qc.x(num_qubits)\n", " if np.random.randint(0, 2):\n", " # return constant circuit with 50% chance\n", " return qc\n", "\n", " # Choose half the possible input strings\n", " on_states = np.random.choice(\n", " range(2**num_qubits), # numbers to sample from\n", " 2**num_qubits // 2, # number of samples\n", " replace=False, # makes sure states are only sampled once\n", " )\n", "\n", " def add_cx(qc, bit_string):\n", " for qubit, bit in enumerate(reversed(bit_string)):\n", " if bit == \"1\":\n", " qc.x(qubit)\n", " return qc\n", "\n", " for state in on_states:\n", " qc.barrier() # Barriers are added to help visualize how the functions are created.\n", " qc = add_cx(qc, f\"{state:0b}\")\n", " qc.mcx(list(range(num_qubits)), num_qubits)\n", " qc = add_cx(qc, f\"{state:0b}\")\n", "\n", " qc.barrier()\n", "\n", " return qc" ] }, { "cell_type": "markdown", "id": "60b36f11", "metadata": {}, "source": [ "Nous pouvons montrer l'implémentation du circuit quantique de la porte d'interrogation en utilisant la méthode `draw` comme d'habitude.\n", "\n" ] }, { "cell_type": "code", "execution_count": 14, "id": "b4a6df3d", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "display(dj_query(3).draw(output=\"mpl\"))" ] }, { "cell_type": "markdown", "id": "6ed6dd43", "metadata": {}, "source": [ "Ensuite, nous définissons une fonction qui crée le circuit Deutsch-Jozsa, en prenant comme argument une implémentation de circuit quantique d'une porte de requête.\n", "\n" ] }, { "cell_type": "code", "execution_count": 15, "id": "79ab8817", "metadata": {}, "outputs": [], "source": [ "def compile_circuit(function: QuantumCircuit):\n", " # Compiles a circuit for use in the Deutsch-Jozsa algorithm.\n", "\n", " n = function.num_qubits - 1\n", " qc = QuantumCircuit(n + 1, n)\n", " qc.x(n)\n", " qc.h(range(n + 1))\n", " qc.compose(function, inplace=True)\n", " qc.h(range(n))\n", " qc.measure(range(n), range(n))\n", " return qc" ] }, { "cell_type": "markdown", "id": "71c07df9", "metadata": {}, "source": [ "Enfin, une fonction qui exécute une fois le circuit Deutsch-Jozsa est définie.\n", "\n" ] }, { "cell_type": "code", "execution_count": 16, "id": "8a6cf538", "metadata": {}, "outputs": [], "source": [ "def dj_algorithm(function: QuantumCircuit):\n", " # Determine if a function is constant or balanced.\n", "\n", " qc = compile_circuit(function)\n", "\n", " result = AerSimulator().run(qc, shots=1, memory=True).result()\n", " measurements = result.get_memory()\n", " if \"1\" in measurements[0]:\n", " return \"balanced\"\n", " return \"constant\"" ] }, { "cell_type": "markdown", "id": "49113ebf", "metadata": {}, "source": [ "Nous pouvons tester notre implémentation en choisissant une fonction au hasard, en affichant l'implémentation du circuit quantique d'une porte d'interrogation pour cette fonction, puis en exécutant l'algorithme de Deutsch-Jozsa sur cette fonction.\n", "\n" ] }, { "cell_type": "code", "execution_count": 17, "id": "aca4745e", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "'balanced'" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "f = dj_query(3)\n", "display(f.draw(\"mpl\"))\n", "display(dj_algorithm(f))" ] }, { "cell_type": "markdown", "id": "89e58116", "metadata": {}, "source": [ "\n", "\n", "## Le problème de Bernstein-Vazirani\n", "\n", "Ensuite, nous aborderons un problème connu sous le nom de *problème de Bernstein-Vazirani*.\n", "Il est également appelé *problème d'échantillonnage de Fourier*, bien qu'il existe des formulations plus générales de ce problème qui portent également ce nom.\n", "\n", "Commençons par introduire quelques notions.\n", "Pour deux chaînes binaires quelconques $x = x_{n-1} \\cdots x_0$ et $y = y_{n-1}\\cdots y_0$ de longueur $n,$, nous définissons\n", "\n", "$$\n", "x \\cdot y = x_{n-1} y_{n-1} \\oplus \\cdots \\oplus x_0 y_0.\n", "$$\n", "\n", "Nous appellerons cette opération le *produit de points binaires*.\n", "Une autre façon de le définir est la suivante.\n", "\n", "$$\n", "x \\cdot y =\n", "\\begin{cases}\n", "1 & x_{{n-1}} y_{n-1} + \\cdots + x_0 y_0 \\text{ is odd}\\\\[0.5mm]\n", "0 & x_{{n-1}} y_{n-1} + \\cdots + x_0 y_0 \\text{ is even}\n", "\\end{cases}\n", "$$\n", "\n", "Notez qu'il s'agit d'une opération symétrique, ce qui signifie que le résultat ne change pas si nous intervertissons $x$ et $y,$. Nous sommes donc libres de le faire quand cela nous convient.\n", "Il est parfois utile de considérer le produit de points binaires $x \\cdot y$ comme étant la parité des bits de $x$ dans les positions où la chaîne $y$ a un $1,$ ou, de manière équivalente, la parité des bits de $y$ dans les positions où la chaîne $x$ a un ou, de manière équivalente, la parité des bits de dans les positions où la chaîne a un $1.$\n", "\n", "Avec cette notation en main, nous pouvons maintenant définir le problème de Bernstein-Vazirani.\n", "\n", "
\n", " Entrée : une fonction $f:\\{0,1\\}^n\\rightarrow\\{0,1\\}$ \\ Promesse : il existe une chaîne binaire $s = s_{n-1} \\cdots s_0$ pour laquelle $f(x) = s\\cdot x$ pour tout $x\\in\\Sigma^n$ \\ Sortie : la chaîne de caractères $s$\n", "
\n", "\n", "Nous n'avons pas besoin d'un nouvel algorithme quantique pour ce problème; l'algorithme de Deutsch-Jozsa le résout.\n", "Par souci de clarté, nous appellerons le circuit quantique ci-dessus, qui n'inclut pas l'étape classique de post-traitement consistant à calculer le OU, le *circuit Deutsch-Jozsa*.\n", "\n", "\n", "\n", "### Analyse algorithmique\n", "\n", "Pour analyser le fonctionnement du circuit Deutsch-Jozsa pour une fonction satisfaisant la promesse du problème de Bernstein-Vazirani, nous commencerons par une observation rapide.\n", "En utilisant le produit de point binaire, nous pouvons décrire l'action des portes de Hadamard de $n$ sur les états de base standard des qubits de $n$ de la manière suivante.\n", "\n", "$$\n", "H^{\\otimes n} \\vert x \\rangle = \\frac{1}{\\sqrt{2^n}} \\sum_{y\\in\\Sigma^n} (-1)^{x\\cdot y} \\vert y\\rangle\n", "$$\n", "\n", "Comme nous l'avons vu lors de l'analyse de l'algorithme de Deutsch, c'est parce que la valeur $(-1)^k$ pour tout entier $k$ dépend uniquement du fait que $k$ est pair ou impair.\n", "\n", "En ce qui concerne le circuit Deutsch-Jozsa, après l'exécution de la première couche de portes de Hadamard, l'état des qubits de $n+1$ est le suivant\n", "\n", "$$\n", "\\vert - \\rangle \\otimes \\frac{1}{\\sqrt{2^n}} \\sum_{x \\in \\Sigma^n} \\vert x \\rangle.\n", "$$\n", "\n", "La porte d'interrogation est ensuite exécutée, ce qui (par le biais du phénomène de retour de phase) transforme l'état en\n", "\n", "$$\n", "\\vert - \\rangle \\otimes \\frac{1}{\\sqrt{2^n}} \\sum_{x \\in \\Sigma^n} (-1)^{f(x)} \\vert x \\rangle.\n", "$$\n", "\n", "En utilisant notre formule pour l'action d'une couche de portes de Hadamard, nous voyons que la deuxième couche de portes de Hadamard transforme alors cet état en\n", "\n", "$$\n", "\\vert - \\rangle \\otimes \\frac{1}{2^n}\n", "\\sum_{x \\in \\Sigma^n} \\sum_{y \\in \\Sigma^n} (-1)^{f(x) + x \\cdot y} \\vert y \\rangle.\n", "$$\n", "\n", "Nous pouvons maintenant faire quelques simplifications, dans l'exposant de $-1$ à l'intérieur de la somme.\n", "On nous promet que $f(x) = s\\cdot x$ pour une chaîne de caractères $s = s_{n-1} \\cdots s_0,$, de sorte que nous pouvons exprimer l'état sous la forme suivante\n", "\n", "$$\n", "\\vert - \\rangle \\otimes \\frac{1}{2^n}\n", "\\sum_{x \\in \\Sigma^n} \\sum_{y \\in \\Sigma^n} (-1)^{s\\cdot x + x \\cdot y} \\vert y \\rangle.\n", "$$\n", "\n", "Comme $s\\cdot x$ et $x\\cdot y$ sont des valeurs binaires, nous pouvons remplacer l'addition par un OU exclusif - toujours parce que la seule chose qui compte pour un entier dans l'exposant de $-1$ est qu'il soit pair ou impair.\n", "En utilisant la symétrie du produit point binaire, nous obtenons cette expression pour l'état :\n", "\n", "$$\n", "\\vert - \\rangle \\otimes \\frac{1}{2^n}\n", "\\sum_{x \\in \\Sigma^n} \\sum_{y \\in \\Sigma^n} (-1)^{(s\\cdot x) \\oplus (y \\cdot x)} \\vert y \\rangle.\n", "$$\n", "\n", "(Les parenthèses ont été ajoutées pour plus de clarté, bien qu'elles ne soient pas vraiment nécessaires car il est conventionnel de traiter le produit binaire en points comme ayant une priorité plus élevée que l'OU exclusif)\n", "\n", "À ce stade, nous utiliserons la formule suivante.\n", "\n", "$$\n", "(s\\cdot x) \\oplus (y \\cdot x) = (s \\oplus y) \\cdot x\n", "$$\n", "\n", "Nous pouvons obtenir la formule en utilisant une formule similaire pour les bits,\n", "\n", "$$\n", "(a c) \\oplus (b c) = (a \\oplus b) c,\n", "$$\n", "\n", "ainsi qu'une expansion du produit binaire en points et de l'OU exclusif en bits :\n", "\n", "$$\n", "\\begin{aligned}\n", "(s\\cdot x) \\oplus (y \\cdot x)\n", "& = (s_{n-1} x_{n-1}) \\oplus \\cdots \\oplus (s_{0} x_{0}) \\oplus\n", "(y_{n-1} x_{n-1}) \\oplus \\cdots \\oplus (y_{0} x_{0}) \\\\\n", "& = (s_{n-1} \\oplus y_{n-1}) x_{n-1} \\oplus \\cdots \\oplus (s_{0} \\oplus y_{0}) x_{0} \\\\\n", "& = (s \\oplus y) \\cdot x\n", "\\end{aligned}\n", "$$\n", "\n", "Cela nous permet d'exprimer comme suit l'état du circuit immédiatement avant les mesures :\n", "\n", "$$\n", "\\vert - \\rangle \\otimes \\frac{1}{2^n}\n", "\\sum_{x \\in \\Sigma^n} \\sum_{y \\in \\Sigma^n} (-1)^{(s\\oplus y)\\cdot x} \\vert y \\rangle.\n", "$$\n", "\n", "La dernière étape consiste à utiliser une autre formule, qui fonctionne pour toutes les chaînes binaires $z = z_{n-1}\\cdots z_0.$\n", "\n", "$$\n", "\\frac{1}{2^n}\n", "\\sum_{x \\in \\Sigma^n} (-1)^{z \\cdot x}\n", "= \\begin{cases}\n", "1 & \\text{if $z = 0^n$}\\\\\n", "0 & \\text{if $z\\neq 0^n$}\n", "\\end{cases}\n", "$$\n", "\n", "Nous utilisons ici une notation simple pour les chaînes de caractères que nous utiliserons à plusieurs reprises dans cette leçon : $0^n$ est la chaîne de caractères entièrement nulle de longueur $n.$\n", "\n", "Une façon simple d'affirmer que cette formule fonctionne est de considérer les deux cas séparément.\n", "Si $z = 0^n,$, alors $z\\cdot x = 0$ pour chaque chaîne $x\\in\\Sigma^n,$, la valeur de chaque terme de la somme est donc $1,$ et nous obtenons $1$ en additionnant et en divisant par $2^n.$ D'autre part, si l'un des bits de $z$ est égal à $1,$, le produit binaire point $z\\cdot x$ est égal à $0$ pour exactement la moitié des choix possibles pour $x\\in\\Sigma^n$ et $1$ pour l'autre moitié - parce que la valeur du produit binaire point $z\\cdot x$ est inversée (de $0$ à $1$ ou de $1$ à $0$ ) si nous inversons n'importe quel bit de $x$ dans une position où $z$ a une valeur de $1.$\n", "\n", "Si nous appliquons maintenant cette formule pour simplifier l'état du circuit avant les mesures, nous obtenons\n", "\n", "$$\n", "\\vert - \\rangle \\otimes \\frac{1}{2^n}\n", "\\sum_{x \\in \\Sigma^n} \\sum_{y \\in \\Sigma^n} (-1)^{(s\\oplus y)\\cdot x} \\vert y \\rangle\n", "= \\vert - \\rangle \\otimes \\vert s \\rangle,\n", "$$\n", "\n", "du fait que $s\\oplus y = 0^n$ si et seulement si $y = s.$ Ainsi, les mesures révèlent précisément la corde $s$ que nous recherchons.\n", "\n", "\n", "\n", "### Difficulté classique\n", "\n", "Alors que le circuit Deutsch-Jozsa résout le problème de Bernstein-Vazirani en une seule requête, tout algorithme de requête classique doit effectuer au moins $n$ requêtes pour résoudre ce problème.\n", "\n", "Cela peut être expliqué par un argument dit de *la théorie de l'information*, qui est très simple dans ce cas.\n", "Chaque requête classique révèle un seul bit d'information sur la solution, et il y a $n$ bits d'information qui doivent être découverts - il faut donc au moins $n$ requêtes.\n", "\n", "Il est en fait possible de résoudre le problème de Bernstein-Vazirani de manière classique en interrogeant la fonction sur chacune des chaînes $n$ ayant un seul $1,$ dans chaque position possible, et $0$ pour tous les autres bits, ce qui révèle les bits de $s$ un par un.\n", "Par conséquent, l'avantage des algorithmes quantiques par rapport aux algorithmes classiques pour ce problème est $1$ queries contre $n$ queries.\n", "\n" ] }, { "cell_type": "markdown", "id": "28583734", "metadata": {}, "source": [ "\n", "\n", "## Bernstein-Vazirani avec Qiskit\n", "\n", "Nous avons déjà mis en œuvre le circuit Deutsch-Jozsa ci-dessus, et nous allons l'utiliser ici pour résoudre le problème de Bernstein-Vazirani.\n", "Nous allons tout d'abord définir une fonction qui implémente une porte de requête pour le problème de Bernstein-Vazirani à partir d'une chaîne de caractères binaire $s.$\n", "\n" ] }, { "cell_type": "code", "execution_count": 18, "id": "11861a7e", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "def bv_query(s):\n", " # Create a quantum circuit implementing a query gate for the\n", " # Bernstein-Vazirani problem.\n", "\n", " qc = QuantumCircuit(len(s) + 1)\n", " for index, bit in enumerate(reversed(s)):\n", " if bit == \"1\":\n", " qc.cx(index, len(s))\n", " return qc\n", "\n", "\n", "display(bv_query(\"1011\").draw(output=\"mpl\"))" ] }, { "cell_type": "markdown", "id": "c24e91e8", "metadata": {}, "source": [ "Nous pouvons maintenant créer une fonction qui exécute le circuit Deutsch-Jozsa sur la fonction, en utilisant la fonction `compile_circuit` définie précédemment.\n", "\n" ] }, { "cell_type": "code", "execution_count": 19, "id": "7db2ea99", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "'1011'" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "def bv_algorithm(function: QuantumCircuit):\n", " qc = compile_circuit(function)\n", " result = AerSimulator().run(qc, shots=1, memory=True).result()\n", " return result.get_memory()[0]\n", "\n", "\n", "display(bv_algorithm(bv_query(\"1011\")))" ] }, { "cell_type": "markdown", "id": "86c52e37", "metadata": {}, "source": [ "\n", "\n", "### Remarque sur la nomenclature\n", "\n", "Dans le contexte du problème de Bernstein-Vazirani, il est courant que l'algorithme de Deutsch-Jozsa soit appelé \"algorithme de Bernstein-Vazirani\"\n", "Ceci est légèrement trompeur, car l'algorithme *est l'* algorithme de Deutsch-Jozsa, comme Bernstein et Vazirani l'ont clairement indiqué dans leurs travaux.\n", "\n", "Après avoir montré que l'algorithme de Deutsch-Jozsa résout le problème de Bernstein-Vazirani (comme indiqué ci-dessus), Bernstein et Vazirani ont défini un problème beaucoup plus complexe, connu sous le nom de *problème d'échantillonnage récursif de Fourier*.\n", "Il s'agit d'un problème très complexe dans lequel les solutions apportées aux différentes instances du problème permettent de débloquer de nouveaux niveaux du problème, organisés selon une structure arborescente.\n", "Le problème de Bernstein-Vazirani n'est que le cas de base de ce problème plus complexe.\n", "\n", "Le problème de l'échantillonnage récursif de Fourier a été le premier exemple connu d'un problème d'interrogation pour lequel les algorithmes quantiques ont un avantage dit *super-polynomial* sur les algorithmes probabilistes, surpassant ainsi l'avantage du quantique sur le classique offert par l'algorithme de Deutsch-Jozsa.\n", "Intuitivement, la version récursive du problème amplifie l'avantage de $1$ par rapport à $n$ des algorithmes quantiques pour en faire quelque chose de beaucoup plus grand.\n", "\n", "L'aspect le plus difficile de l'analyse mathématique établissant cet avantage est de montrer que les algorithmes d'interrogation classiques ne peuvent pas résoudre le problème sans effectuer un grand nombre d'interrogations.\n", "C'est tout à fait typique; pour de nombreux problèmes, il peut être très difficile d'exclure les approches classiques créatives qui les résolvent efficacement.\n", "\n", "Le problème de Simon, et l'algorithme décrit dans la section suivante, fournit un exemple beaucoup plus simple d'un avantage super-polynomial (et, en fait, exponentiel) des algorithmes quantiques par rapport aux algorithmes classiques, et c'est pour cette raison que le problème de l'échantillonnage récursif de Fourier est moins souvent abordé.\n", "Il s'agit néanmoins d'un problème informatique intéressant en soi.\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "id": "a1b8767d", "source": "© IBM Corp., 2017-2026" } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3" } }, "nbformat": 4, "nbformat_minor": 5 }