<jupyter_start><jupyter_text>Algorithme de recherche de marche quantique Les marches quantiques sont l'équivalence quantique d'une chaîne de Markov classique et sont devenues la clé de nombreux algorithmes quantiques. Dans cette section, nous implémentons un algorithme de recherche de marche quantique qui trouve des éléments marqués dans un graphe. L'algorithme a une accélération quadratique par rapport à son homologue classique. 1. Chaînes de Markov classiquesUne chaîne de Markov est un processus stochastique souvent utilisé pour modéliser des processus réels. Il se compose d'états et de probabilités de transition associées, qui décrivent les probabilités de se déplacer entre les états à chaque pas de temps. Dans les chaînes de Markov à temps discret, avec lesquelles nous travaillons ici, les pas de temps sont discrets. Les chaînes de Markov satisfont la propriété de Markov, ce qui signifie que l'étape suivante du processus ne dépend que de l'étape actuelle et non de l'une des étapes précédentes. Une chaîne de Markov a une matrice de transition associée, P, qui décrit la probabilité de se déplacer entre chacun des états. Nous montrons ci-dessous un exemple de chaîne de Markov et sa matrice de transition associée $P$. \begin{equation} P= \begin{pmatrix} 0.1 &amp; 0.3 &amp; 0.3\ 0.1 &amp; 0.1 &amp; 0.2 \ 0.8 &amp; 0.6 &amp; 0.5 \end{pmatrix} \label{eq:matrix_example} \end{equation}Étant donné une matrice de transition $P$, nous pouvons obtenir la distribution de probabilité après $t$ pas de temps par $P^t$. 2. Marches quantiquesLes marches quantiques sont l'équivalent quantique de la chaîne de Markov classique. En raison de la superposition, une marche quantique empruntera simultanément tous les chemins possibles jusqu'à ce que nous mesurions le circuit. En raison des interférences quantiques, certains états s'annuleront. Cela rend les algorithmes de marche quantique plus rapides que les algorithmes classiques, car nous pouvons les concevoir de manière à ce que les mauvaises réponses s'annulent rapidement. Il existe deux modèles courants pour les marches quantiques, les marches quantiques inventées et les marches quantiques de Szegedy, qui sont équivalentes dans certaines circonstances. Une marche quantique inventée est une marche sur les sommets du graphe tandis que la marche quantique de Szegedy a lieu sur les arêtes. Avant de montrer comment nous pouvons implémenter une marche quantique, nous présenterons les deux modèles.$\newcommand{\ket}[1]{\left|{1}\right\rangle}$ $\newcommand{\bra}[1]{\left\langle{1}\right|}$ 2.A Marches quantiques inventéesUn exemple simple d'une marche quantique inventée est une marche sur la ligne entière infinie. Dans ce cas, nous représentons la position du marcheur par un entier, ${\ket{j} : j \in \mathbb{Z} }$, puisque le marcheur peut parcourir tous les entiers dans $\mathbb{Z}$. Une pièce décide comment le marcheur doit se déplacer. Sur la droite entière, le promeneur peut aller soit à gauche, soit à droite. Par conséquent, la base de calcul de la pièce est ${\ket{0}, \ket{1}}$, et nous déplaçons le marcheur dans un sens si la pièce est $\ket{0}$ et dans l'autre sens si la pièce est $\ket{1}$.Un quantum inventé est une marche sur les nœuds d'un graphe, et nous appelons les nœuds des états. Le marcheur peut se déplacer entre des états reliés par une arête. Dans le modèle des pièces, nous avons deux états quantiques et deux opérateurs. Le premier état est l'état de position, qui représente la position du marcheur. Pour la marche ci-dessus, il s'agit d'un entier puisque le marcheur peut être n'importe où sur la ligne entière. L'autre état est l'état de la pièce. L'état de la pièce décide comment le marcheur doit se déplacer à l'étape suivante. Nous pouvons représenter à la fois l'état de la pièce et l'état de la position par des vecteurs dans l'espace de Hilbert. Si nous pouvons exprimer l'état de la pièce par un vecteur dans $\mathcal{H}_C$ et l'état de la position avec un vecteur dans $\mathcal{H}_P$, nous pouvons exprimer l'espace quantique pour le marcheur entier comme $\mathcal {H} = \mathcal{H}_C \otimes \mathcal{H}_P$.Comme nous l'avons mentionné, le modèle a également deux opérateurs ; l'opérateur de pièces, $C$, et l'opérateur de décalage, $S$. L'opérateur de pièces agit sur $\mathcal{H}_C$ à chaque pas de temps et met le marcheur en superposition, de sorte qu'il parcourt tous les chemins possibles simultanément. Pour la marche sur la ligne entière, cela signifie qu'elle se déplace à la fois vers la gauche et vers la droite à chaque pas de temps. Il existe différents opérateurs de pièces, mais les plus courants sont la pièce Hadamard et la pièce Grover. Une pièce Hadamard est une porte Hadamard qui place le promeneur dans une superposition égale :\begin{equation} H = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 &amp; 1 \ 1 &amp; -1 \end{bmatrix} \end{equation}Une pièce Grover est l'opérateur de diffusion Grover de l'algorithme de Grover. Nous le définissons comme\begin{équation} G = \begin{bmatrice} \frac{2}{n} -1 &amp; \frac{2}{n} &amp; \ldots &amp; \frac{2}{n}\ \frac{2}{ n} &amp; \frac{2}{n} - 1 &amp; \ldots &amp; \frac{2}{n} \ \vdots &amp; \vdots &amp; \ddots &amp; \vdots \ \frac{2}{n} &amp; \frac{ 2}{n} &amp; \ldots &amp; \frac{2}{n} -1 \end{bmatrice} \end{équation}Comme la pièce Hadamard, une pièce Grover met le promeneur en superposition. Cependant, il se comporte un peu différemment. Si nous appliquons une pièce Grover à un marcheur en position $\ket{000}$, nous obtenons les probabilités de vecteur d'état présentées dans la figure ci-dessous. Comme on peut le voir, la pièce ne met pas le promeneur dans une superposition égale comme le fait la pièce Hadamard. Au lieu de cela, $\ket{000}$ a une probabilité beaucoup plus grande que les autres états.L'autre opérateur du modèle, l'opérateur de décalage, agit sur $\mathcal{H}_P$ et déplace le marcheur vers la position suivante. Pour la marche sur la droite entière, l'opérateur de décalage déplace le marcheur vers la gauche de la pièce est $\ket{0}$ et vers la droite si la pièce est $\ket{1}$ :\begin{équation} S \ket{0}\ket{j} = \ket{0}\ket{j+1} \end{équation}\begin{équation} S \ket{1}\ket{j} = \ket{1}\ket{j-1} \end{équation}Avec l'opérateur de décalage défini ci-dessus, nous pouvons représenter une étape du quantum inventé comme l'opérateur unitaire $U$ donné par \begin{equation} U = SC, \end{equation}où C est le monnayeur. Pour la marche quantique sur la ligne entière, nous utilisons la pièce Hadamard, mais C peut être une pièce Hadamard, une pièce Grover ou tout autre opérateur de pièces.Nous pouvons également regarder plusieurs étapes en avant. Nous pouvons exprimer l'état quantique $\ket{\psi}$ après $t$ pas de temps comme \begin{equation} \ket{\psi (t)} = U^t \ket{\psi(0)}, \ end{equation} où $\ket{\psi(0)}$ est l'état initial et U est l'opérateur pour une étape de la marche [1].Les marches quantiques inventées conviennent le mieux aux graphes réguliers, des graphes où tous les nœuds ont le même nombre de voisins [2]. Un autre modèle de marche quantique plus pratique pour les graphes non réguliers est le modèle de Szegedy que nous examinerons ensuite. 2.B Marche quantique de SzedgedyAlors qu'une marche inventée est une marche sur les nœuds du graphe, une marche de Szegedy est une marche sur les arêtes d'une double couverture bipartite du graphe d'origine. Le graphe à double couverture est un graphe avec deux fois plus de sommets que le graphe d'origine. Deux nœuds du graphe bipartite à double couverture sont connectés par une arête si et seulement si les nœuds sont également connectés dans le graphe d'origine. Pour créer ce modèle, nous partons de la matrice de probabilité de transition P pour la marche classique. Comme décrit dans la section 1, nous représentons une marche aléatoire classique en temps discret par une matrice de transition $P$. Pour tout graphe $N$-vertex avec $N \times N$ matrice de transition $P$, nous pouvons définir la marche quantique en temps discret correspondante comme une opération unitaire sur l'espace de Hilbert $\mathcal{H}^N \otimes \ mathcal{H}^N$. Soit $P_{jk}$ la probabilité que l'on fasse une transition de l'état $j$ à $k$. Avant de définir la marche, nous définissons les états normalisés\begin{equation} \ket{\psi_j} := \sum_{k=1}^N \sqrt{P_{kj}} \ket{j,k}, ; j=1,...,N \end{équation}et la projection sur ${\ket{\psi_j}}:j=1,...,N$\begin{equation} \Pi := \sum_{j=1}^N \ket{\psi_j} \bra{\psi_j} \label{eq:sz_pi} \end{equation}Nous introduisons également l'opérateur de décalage S :\begin{equation} S := \sum_{j,k=1}^N \ket{j,k} \bra{k,j} \label{eq:sz_s} \end{equation}Avec $S$ et $\Pi$ définis comme ci-dessus, nous pouvons introduire une étape de la marche quantique en temps discret :\begin{equation} U := S(2 \Pi - 1), \label{eq:sz_op} \end{equation}où $(2 \Pi - 1)$ est l'opérateur de réflexion. Nous définissons également $t$ pas de marche comme $U^t$ [2]. 2.C Équivalence des marches quantiques inventées et de SzegedyOn sait qu'une marche inventée avec une pièce Grover équivaut à une marche quantique de Szegedy. Pour plus de détails, nous renvoyons à cet article [3] de <NAME>, où il montre également l'équivalence entre les opérateurs dans les deux modèles. 3. Exemple : Implémentation de la marche quantique sur un hypercubeUn hypercube est la contrepartie $n$-dimensionnelle du cube $3$-dimensionnel. Tous les nœuds ont un degré $n$, et l'hypercube a un total de $N=2^n$ nœuds. Nous pouvons représenter les nœuds d'un graphe hypercube par $n$-uplets de nombres binaires. La représentation binaire des voisins d'un nœud ne différera que d'un seul nombre binaire. Par exemple, dans l'hypercube à 4 dimensions, les voisins de $0000$ sont $0001$, $0010$, $0100$ et $1000$. Ainsi, un nœud est connecté à tous les nœuds auxquels la distance de Hamming est 1. Les arêtes sont également étiquetées. Deux nœuds voisins qui diffèrent par le a:ème bit sont connectés par le bord étiqueté $a$.L'espace de Hilbert représentant une marche quantique inventée sur l'hypercube est $\mathcal{H} = \mathcal{H}^n \otimes \mathcal{H}^{2^n}$, où $\mathcal{H}^n $ désigne l'espace pièce et $\mathcal{H}^{2^n}$ la position du marcheur. La base de calcul est\begin{equation} \big{ \ket{a,\vec{v}}, 0 \leq a \leq n-1, \vec{v} \in {(00...00), (00.. .01), ....., (11...11 )} \big}. \end{équation}La valeur de la base de calcul des pièces $a$, qui est associée à l'arête $a$, décide où le marcheur doit se déplacer. Si le $a=0$, le marcheur ira au nœud où la première valeur binaire diffère du nœud courant. Si $a=1$, le marcheur se déplacera vers le nœud dans lequel la deuxième valeur diffère de la valeur actuelle, et cetera. Soit $\vec{e}_a$ un n-uplet où toutes les valeurs binaires, à l'exception de la valeur d'indice $a$, sont $0$. Ensuite, l'opérateur de décalage $S$ déplace le marcheur de l'état $\ket{a} \ket{\vec{v}}$ vers $\ket{\vec{v} \oplus \vec{e}_a}$ :\begin{equation} S \ket{a} \ket{\vec{v}} = \ket{a} \ket{\vec{v} \oplus \vec{e}_a}. \end{équation}Nous utilisons la pièce Grover, $G$, pour cette marche. Ainsi, l'opérateur d'évolution est\begin{équation} U = SG. \end{équation}Nous allons maintenant montrer comment implémenter une marche quantique sur un hypercube à 4 dimensions. Nous devons implémenter l'opérateur de pièces et l'opérateur de décalage. Nous commençons par importer toutes les bibliothèques nécessaires depuis Qiskit.<jupyter_code># Importing standard Qiskit libraries
from qiskit import QuantumCircuit, execute, Aer, IBMQ, QuantumRegister, ClassicalRegister
from qiskit.compiler import transpile, assemble
from qiskit.tools.jupyter import *
from qiskit.visualization import *
from qiskit.circuit.library import QFT
from numpy import pi
from qiskit.quantum_info import Statevector
from matplotlib import pyplot as plt
import numpy as np
# Loading your IBM Q account(s)
provider = IBMQ.load_account()<jupyter_output><empty_output><jupyter_text>Le circuit aura 6 qubits, 4 qui représentent la position et 2 qui représentent la pièce. Comme nous l'avons mentionné précédemment, la pièce est une pièce Grover, qui est le diffuseur dans l'algorithme de Grover. Nous commençons par mettre cela en œuvre.<jupyter_code>one_step_circuit = QuantumCircuit(6, name=' ONE STEP') 
# Coin operator
one_step_circuit.h([4,5])
one_step_circuit.z([4,5])
one_step_circuit.cz(4,5)
one_step_circuit.h([4,5])
one_step_circuit.draw()<jupyter_output><empty_output><jupyter_text>Maintenant, implémentons l'opérateur de décalage. Nous savons que le marcheur ne peut se déplacer que vers les nœuds voisins, et tous les nœuds voisins ne diffèrent que d'un bit. Nous voulons déplacer le marcheur en fonction de la pièce, et nous déplaçons le marcheur en appliquant une porte NON à l'un des qubits du nœud. Si la pièce est dans l'état $\ket{11}$, nous déplaçons le marcheur vers l'état dans lequel le premier nœud qubit diffère. Si la pièce est $\ket{10}$ ou $\ket{01}$, le marcheur passe à l'état où le deuxième et le troisième qubit, respectivement, diffèrent. Enfin, si la pièce Grover est $\ket{00}$, nous retournons le quatrième qubit. Nous implémentons cela avec des portes CCNOT- et NOT après la pièce Grover. Ensemble, ils sont une étape d'une marche quantique sur un hypercube à 4 dimensions.<jupyter_code># Shift operator function for 4d-hypercube
def shift_operator(circuit):
    for i in range(0,4):
        circuit.x(4)
        if i%2==0:
            circuit.x(5)
        circuit.ccx(4,5,i)

shift_operator(one_step_circuit)

one_step_gate = one_step_circuit.to_instruction() 
one_step_circuit.draw()<jupyter_output><empty_output><jupyter_text>4. Algorithme de recherche de marche quantiqueNous allons maintenant implémenter un algorithme de recherche de marche quantique qui trouve un sommet marqué dans un graphe. Tout d'abord, nous décrivons l'algorithme, puis nous passons en revue sa mise en œuvre. L'algorithme de recherche de marche quantique résout le problème de la recherche de sommets marqués dans un graphe par une marche quantique. Autrement dit, nous marquons un ensemble de sommets $|M|$, commençons à un nœud arbitraire dans le graphe et nous déplaçons selon la marche jusqu'à ce que nous trouvions les nœuds marqués. Les états de base dans l'algorithme de recherche de marche quantique ont deux registres, l'un correspondant au nœud actuel et l'autre correspondant au nœud précédent. Autrement dit, les états de base correspondent aux arêtes du graphe. On note la marche quantique basée sur la chaîne de Markov classique de matrice de transition $P$ par l'opération unitaire $W(P)$ sur $\mathcal{H}$. Nous définissons également $\ket{p_x} = \sum_y \sqrt{P_{xy}}\ket{y}$ comme la superposition uniforme sur les voisins du nœud $x$. Soit $\ket{x}\ket{y}$ un état de base. Nous définissons l'état de base $\ket{x}\ket{y}$ comme ''bon'' si $x$ est un nœud marqué. Sinon, nous l'appelons ''mauvais''. Nous introduisons maintenant les états ''bon'' et ''mauvais'' :\begin{equation} \ket{G} = \frac{1}{\sqrt{|M|}} \sum_{x \in M} \ket{x} \ket{p_x}, ; \ket{B} = \frac{1}{\sqrt{N-|M|}} \sum_{x \notin M} \ket{x} \ket{p_x}, \end{équation}qui sont les superpositions sur les bons et les mauvais états de base. Ensuite, définissons $\epsilon = |M|/N$ et $\theta = \arcsin(\sqrt{\epsilon})$.En bref, l'algorithme se compose de trois étapes :1. Configurer l'état initial $\ket{U} = \frac{1}{\sqrt{N}} \sum_{x} \ket{x} \ket{p_x} = \sin{\theta} \ket{G } + \cos{\theta} \ket{B}$, une superposition uniforme sur toutes les arêtes2. Répétez $O(1/\sqrt{\epsilon})$ fois :    (a) Réfléchissez à travers $\ket{B}$    (b) Réfléchissez à travers $\ket{U}$3. Faire une mesure dans la base de calculNous pouvons facilement implémenter l'étape $1$ avec des portes d'Hadamard et la réflexion à travers $\ket{B}$ avec un oracle de phase qui décale la phase de $x$ si $x$ est dans le premier registre, et laisse le circuit inchangé sinon.L'étape 2(b) équivaut à trouver un $R(P)$ unitaire qui effectue le mappage suivant : \begin{align} \label{eq:mapping_1} \ket{U} &amp;\mapsto \ket{U}, : \text{and} \ \ket{\psi} &amp;\mapsto -\ket{\psi}, : \forall \ket{\psi} \text{dans l'étendue des vecteurs propres de $W(P)$ qui sont orthogonaux à $\ket{U}$} \label{eq:mapping_2} \end{align}Pour trouver cet opérateur, nous appliquons une estimation de phase sur $W(P)$. Ci-dessus, nous avons défini $W(P)$ comme l'opérateur d'évolution de la marche aléatoire. Comme nous l'avons vu dans la section 2.A, il s'agit d'un opérateur unitaire. Il en résulte que les valeurs propres de $W(P)$ ont pour norme $1$. De ce fait, nous pouvons écrire les valeurs propres de $W(P)$ sous la forme $e^{\pm 2i\theta_j}$. L'unité $W(P)$ a un vecteur propre avec la valeur propre correspondante $1$, qui est $\ket{U}$. Ceci est donné par $\theta_1=0$. $R(P)$ trouvera ce vecteur $\ket{U}$ en ajoutant un registre avec des qubits auxiliaires et effectuera une estimation de phase avec une précision $O(1/\sqrt{\delta})$, où $\delta$ est l'écart spectral de $P$. Pour ce faire, nous devons appliquer $W(P)$ $O(1/\sqrt{\delta})$ fois. Soit $\ket{w}$ un vecteur propre de $W(P)$ de valeur propre $e^{\pm 2i\theta_j}$. Supposons que $\tilde{\theta_j}$ est la meilleure approximation de $\theta_j$ donnée par l'estimation de phase. L'opération $R(P)$ qui effectue les mappages dans pour $\ket{w}$ à l'étape 2(b) est donnée par [4]\begin{equation} \ket{w} \ket{0} \mapsto \ket{w} \ket{\tilde{\theta_j}} \mapsto (-1)^{|\tilde{\theta_j} \neq 0 |} \ket{w} \ket{\tilde{\theta_j}} \mapsto (-1)^{|\tilde{\theta_j} \neq 0|} \ket{w} \ket{0} \end{ équation} 5.Exemple : recherche de marche quantique sur un hypercube à 4 dimensionsL'algorithme de recherche de marche quantique permet de trouver un ensemble marqué de nœuds en $O(1/\sqrt{\epsilon})$ pas, $\epsilon = |M|/N$, où $M$ est le nombre de nœuds marqués et $N$ est le nombre total de nœuds. Cet algorithme est utilisé à l'origine avec les marches quantiques de Szegedy, où nous utilisons deux registres de nœuds pour représenter l'état quantique. Cependant, une marche inventée avec une pièce de Grover équivaut à une marche quantique de Szegedy et comme les implémentations des marches inventées sont moins complexes en général, nous choisissons d'implémenter l'algorithme avec une marche inventée. Nous utiliserons l'hypercube à 4 dimensions que nous avons implémenté dans la section 3.En bref, nous allons implémenter l'algorithme comme suit. Nous réalisons l'étape 1, une superposition uniforme sur tous les bords, en appliquant des portes Hadamard aux qubits de nœud ainsi qu'aux qubits de pièces. Pour l'étape 2(a), nous implémentons un oracle de phase. L'étape 2(b) est implémentée par une estimation de phase sur une étape de la marche quantique sur l'hypercube suivie du marquage de tous les états quantiques où $\theta \neq 0$. Nous faisons cela en faisant tourner un qubit auxiliaire. Dans la dernière partie de cette étape, nous inversons l'estimation de phase. Le nombre de qubits thêta dépend de la précision de $\theta$.Ci-dessous, nous implémentons l'algorithme de recherche de marche quantique sur l'hypercube à 4 dimensions.  Pour cet algorithme, nous devrons utiliser l'inverse de la porte à une étape implémentée précédemment. Nous obtenons cela en utilisant la fonction de circuit intégrée inverse().<jupyter_code>one_step_circuit.inverse().draw()<jupyter_output><empty_output><jupyter_text>La porte inversée à un pas sera utilisée pour inverser l'estimation de phase ultérieurement. Nous devons créer des portes contrôlées à partir de la porte à une étape que nous avons implémentée dans la section 3 et de son inverse. Nous les utiliserons plus tard en fonction de la valeur du qubit de contrôle.<jupyter_code># Make controlled gates
inv_cont_one_step = one_step_circuit.inverse().control()
inv_cont_one_step_gate = inv_cont_one_step.to_instruction()
cont_one_step = one_step_circuit.control()
cont_one_step_gate = cont_one_step.to_instruction()<jupyter_output><empty_output><jupyter_text>La porte à un pas contrôlée et la porte à un pas inversée contrôlée seront utilisées dans l'estimation de phase. Une autre chose que nous utiliserons dans l'estimation de phase est la transformée de Fourier quantique. Qiskit a une fonction, QFT, qui implémente la transformée de Fourier quantique. L'estimation de phase utilise la transformée de Fourier quantique inverse, mais nous devrons également utiliser le QFT ordinaire pour inverser l'estimation de phase.<jupyter_code>inv_qft_gate = QFT(4, inverse=True).to_instruction()  
qft_gate = QFT(4, inverse=False).to_instruction()

QFT(4, inverse=True).decompose().draw("mpl")<jupyter_output><empty_output><jupyter_text>Avant d'implémenter l'estimation de phase, nous implémentons un oracle de phase qui marque les états 1011 et 1111. Ensuite, nous en faisons un circuit. C'est l'étape 2(a) de l'algorithme.<jupyter_code>phase_circuit =  QuantumCircuit(6, name=' phase oracle ')
# Mark 1011
phase_circuit.x(2)
phase_circuit.h(3)
phase_circuit.mct([0,1,2], 3)
phase_circuit.h(3)
phase_circuit.x(2)
# Mark 1111
phase_circuit.h(3)
phase_circuit.mct([0,1,2],3)
phase_circuit.h(3)
phase_oracle_gate = phase_circuit.to_instruction()
# Phase oracle circuit
phase_oracle_circuit =  QuantumCircuit(11, name=' PHASE ORACLE CIRCUIT ')
phase_oracle_circuit.append(phase_oracle_gate, [4,5,6,7,8,9])
phase_circuit.draw()<jupyter_output><empty_output><jupyter_text>Nous allons maintenant implémenter une porte qui fait tourner un qubit auxiliaire si les autres qubits sont non nuls. Nous utiliserons cette porte dans l'estimation de phase, où elle fera tourner le qubit auxiliaire si $\theta \neq 0$.<jupyter_code># Mark q_4 if the other qubits are non-zero 
mark_auxiliary_circuit = QuantumCircuit(5, name=' mark auxiliary ')
mark_auxiliary_circuit.x([0,1,2,3,4])
mark_auxiliary_circuit.mct([0,1,2,3], 4)
mark_auxiliary_circuit.z(4)
mark_auxiliary_circuit.mct([0,1,2,3], 4)
mark_auxiliary_circuit.x([0,1,2,3,4])

mark_auxiliary_gate = mark_auxiliary_circuit.to_instruction()
mark_auxiliary_circuit.draw()<jupyter_output><empty_output><jupyter_text>Maintenant, nous allons implémenter l'étape 2(b) de l'algorithme. Cette étape consiste en une estimation de phase une étape de la marche quantique suivie d'un qubit auxiliaire que l'on fait tourner si $\theta \neq 0$. Pour cela, nous utilisons le mark_auxiliary_gate que nous venons de créer. Ensuite, on inverse l'estimation de phase.<jupyter_code># Phase estimation
phase_estimation_circuit = QuantumCircuit(11, name=' phase estimation ')
phase_estimation_circuit.h([0,1,2,3])
for i in range(0,4):
    stop = 2**i
    for j in range(0,stop):
        phase_estimation_circuit.append(cont_one_step, [i,4,5,6,7,8,9])

# Inverse fourier transform
phase_estimation_circuit.append(inv_qft_gate, [0,1,2,3])

# Mark all angles theta that are not 0 with an auxiliary qubit
phase_estimation_circuit.append(mark_auxiliary_gate, [0,1,2,3,10])

# Reverse phase estimation
phase_estimation_circuit.append(qft_gate, [0,1,2,3])   

for i in range(3,-1,-1):
    stop = 2**i
    for j in range(0,stop):
        phase_estimation_circuit.append(inv_cont_one_step, [i,4,5,6,7,8,9])
phase_estimation_circuit.barrier(range(0,10))
phase_estimation_circuit.h([0,1,2,3])

# Make phase estimation gate
phase_estimation_gate = phase_estimation_circuit.to_instruction()
phase_estimation_circuit.draw()<jupyter_output><empty_output><jupyter_text>Maintenant, nous implémentons l'ensemble de l'algorithme de recherche de marche quantique en utilisant les portes que nous avons créées précédemment. Nous commençons par appliquer les portes Hadamard aux qubits de nœud et de pièce, ce qui est l'étape 1 de l'algorithme. Ensuite, nous appliquons itérativement la porte oracle de phase et la porte d'estimation de phase (étapes 2(a) et 2(b)). Nous avons besoin de $O(1/\sqrt{\epsilon})$ itérations comme indiqué dans la description de l'algorithme dans la section 4. Enfin, nous mesurons les qubits des nœuds.<jupyter_code># Implementation of the full quantum walk search algorithm
theta_q = QuantumRegister(4, 'theta')
node_q = QuantumRegister(4, 'node')
coin_q = QuantumRegister(2, 'coin')
auxiliary_q = QuantumRegister(1, 'auxiliary')
creg_c2 = ClassicalRegister(4, 'c')
circuit = QuantumCircuit(theta_q, node_q, coin_q, auxiliary_q, creg_c2)
# Apply Hadamard gates to the qubits that represent the nodes and the coin
circuit.h([4,5,6,7,8,9])
iterations = 2

for i in range(0,iterations):
    circuit.append(phase_oracle_gate, [4,5,6,7,8,9])
    circuit.append(phase_estimation_gate, [0,1,2,3,4,5,6,7,8,9,10])

circuit.measure(node_q[0], creg_c2[0])
circuit.measure(node_q[1], creg_c2[1])
circuit.measure(node_q[2], creg_c2[2])
circuit.measure(node_q[3], creg_c2[3])
circuit.draw()<jupyter_output><empty_output><jupyter_text>Enfin, nous exécutons l'implémentation sur le simulateur qasm. Nous voyons que le circuit s'effondre aux états marqués une nette majorité du temps.<jupyter_code>backend = Aer.get_backend('qasm_simulator') 
job = execute( circuit, backend, shots=1024 ) 
hist = job.result().get_counts() 
plot_histogram( hist )<jupyter_output><empty_output><jupyter_text>6. Références1. <NAME>. Marches quantiques et algorithmes de recherche. New York, NY: Springer New York, 20132. <NAME>.Quelques notes d'introduction sur l'informatique quantique. Avr. 20003. <NAME>. "Équivalence des marches quantiques de Szegedy et inventées". Dans : Quantum InformationProcessing 16.9 (juillet 2017). ISSN : 1573-1332. DOI :10.1007/s11128-017-1667-y. URL : http://dx.doi.org/10.1007/s11128-017-1667-y.374. <NAME>. Informatique quantique : Notes de cours. 2021. arXiv:1907.09415 [quant-ph]<jupyter_code>import qiskit.tools.jupyter
%qiskit_version_table<jupyter_output>/usr/local/anaconda3/envs/terra-unstable/lib/python3.9/site-packages/qiskit/aqua/__init__.py:86: DeprecationWarning: The package qiskit.aqua is deprecated. It was moved/refactored to qiskit-terra For more information see <https://github.com/Qiskit/qiskit-aqua/blob/main/README.md#migration-guide>
  warn_package('aqua', 'qiskit-terra')
{'fraction_non_alphanumeric': 0.09549957760540666, 'fraction_numerical': 0.01727977881883112, 'mean_word_length': 5.177182163187855, 'pattern_counts': {'":': 0, '<': 54, '<?xml version=': 0, '>': 54, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '12', 'dir': 'jupyter-structured-clean-dedup', 'id': '20972', 'license': 'Apache-2.0', 'n_tokens_mistral': 9175, 'n_tokens_neox': 8914, 'n_words': 3354, 'path': 'fr/notebooks/ch-algorithms/quantum-walk-search-algorithm.ipynb', 'repo_name': 'TanyaJazzTeam/platypus', 'size': '26080'}