Deutsch : constante ou équilibrée ?
★★☆Pour la fonction \(f(0)=1,\ f(1)=1\), on exécute le circuit de Deutsch. Que mesure-t-on sur le premier qubit ?
Annexe · hors du programme du polycopié
Avec les amplitudes, les interférences et la porte de Hadamard du chapitre 1, on comprend le principe de deux algorithmes célèbres, sans formalisme supplémentaire.
Un registre de \(n\) qubits porte \(2^n\) amplitudes. Un algorithme quantique ne « teste pas tous les cas en même temps » : il fait interférer ces amplitudes pour que les mauvaises réponses s’annulent et que la bonne reste. La mesure finale fait le reste. Cela ne marche que pour certains problèmes.
Une boîte noire calcule \(f:\{0,1\}\to\{0,1\}\) par \(U_f\ket{x}\ket{y} = \ket{x}\ket{y\oplus f(x)}\). On veut savoir si \(f\) est constante (\(f(0)=f(1)\)) ou équilibrée (\(f(0)\ne f(1)\)). Classiquement, il faut deux appels ; quantiquement, un seul.
Circuit : partir de \(\ket0\ket1\), appliquer \(H\otimes H\), puis \(U_f\), puis \(H\) sur le premier qubit, et mesurer le premier qubit.
La valeur de \(f\) passe dans une phase \((-1)^{f(x)}\) (le « rebond de phase »), et le second \(H\) la convertit en une probabilité : on lit \(0\) si \(f\) est constante, \(1\) si elle est équilibrée.
Pour la fonction \(f(0)=1,\ f(1)=1\), on exécute le circuit de Deutsch. Que mesure-t-on sur le premier qubit ?
On cherche un élément marqué parmi \(N\). On part de l’état uniforme \(\ket s = H^{\otimes n}\ket0\) (toutes les amplitudes égales à \(1/\sqrt N\)), puis on répète deux étapes : l’oracle change le signe de l’amplitude de l’élément marqué ; la diffusion \(2\ket s\bra s - \mathbb 1\) renvoie chaque amplitude de l’autre côté de la moyenne. Pour \(N=4\), une itération suffit : l’oracle donne \((\tfrac12,\tfrac12,\tfrac12,-\tfrac12)\), de moyenne \(\tfrac14\), et l’inversion autour de la moyenne donne \((0,0,0,1)\).
Pour \(N\) grand, il faut environ \(\tfrac\pi4\sqrt N\) itérations : un gain quadratique sur la recherche classique (environ \(N/2\) essais en moyenne), pas exponentiel.
On cherche un élément parmi \(N=64\) avec l’algorithme de Grover. La probabilité de succès après \(k\) itérations est \(\sin^2\!\big((2k+1)\theta\big)\) avec \(\sin\theta = 1/\sqrt N\). Quel nombre entier \(k \le 10\) d’itérations (premier maximum) donne la meilleure probabilité ?