L'algorithme de Deutsch

L'algorithme de Deutsch résout le problème de la parité pour le cas particulier où $n = 1.$ Dans le contexte du calcul quantique, ce problème est parfois appelé problème de Deutsch, et nous utiliserons cette terminologie dans cette leçon.

Pour être précis, l'entrée est représentée par une fonction $f:\Sigma \rightarrow \Sigma$ d'un bit vers un bit. Il y a quatre telles fonctions :

$$\rule[-10mm]{0mm}{10mm} \begin{array}{c|c} a & f_1(a)\\ \hline 0 & 0\\ 1 & 0 \end{array} \qquad \begin{array}{c|c} a & f_2(a)\\ \hline 0 & 0\\ 1 & 1 \end{array} \qquad \begin{array}{c|c} a & f_3(a)\\ \hline 0 & 1\\ 1 & 0 \end{array} \qquad \begin{array}{c|c} a & f_4(a)\\ \hline 0 & 1\\ 1 & 1 \end{array}$$

La première et la dernière de ces fonctions sont constantes, et les deux du milieu sont équilibrées, ce qui signifie que les deux valeurs de sortie possibles apparaissent le même nombre de fois lorsqu'on parcourt toutes les entrées. Le problème de Deutsch consiste à déterminer à laquelle de ces deux catégories appartient la fonction d'entrée : constante ou équilibrée.

Problème de Deutsch

Entrée : une fonction $f:\{0,1\}\rightarrow\{0,1\}$
Sortie : $0$ si $f$ est constante, $1$ si $f$ est équilibrée

Si on considère la fonction d'entrée $f$ du problème de Deutsch comme représentant un accès aléatoire à une chaîne de bits, on pense alors à une chaîne de deux bits : $f(0)f(1).$

$$\begin{array}{cc} \mathsf{fonction} & \mathsf{chaîne}\\ \hline f_1 & 00 \\ f_2 & 01 \\ f_3 & 10 \\ f_4 & 11 \end{array}$$

Vu sous cet angle, le problème de Deutsch consiste à calculer la parité (ou, de manière équivalente, le OU exclusif) des deux bits.

Tout algorithme de requête classique qui résout correctement ce problème doit interroger les deux bits : $f(0)$ et $f(1).$ Si on apprend que $f(1) = 1,$ par exemple, la réponse peut encore être $0$ ou $1,$ selon que $f(0) = 1$ ou $f(0) = 0,$ respectivement. Tous les autres cas sont similaires ; connaître un seul des deux bits ne fournit aucune information sur leur parité. Ainsi, le circuit booléen décrit dans la section précédente est le mieux qu'on puisse faire en termes de nombre de requêtes nécessaires pour résoudre ce problème.

Description du circuit quantique

L'algorithme de Deutsch résout le problème de Deutsch en une seule requête, offrant ainsi un avantage quantifiable du calcul quantique sur le calcul classique. Il peut s'agir d'un avantage modeste — une requête contre deux — mais il faut bien commencer quelque part. Les avancées scientifiques ont parfois des origines en apparence humbles.

Voici un circuit quantique qui décrit l'algorithme de Deutsch :

Analyse

Pour analyser l'algorithme de Deutsch, nous allons suivre l'action du circuit ci-dessus et identifier les états des qubits aux moments suggérés par cette figure :

L'état initial est $\vert 1\rangle \vert 0 \rangle,$ et les deux opérations de Hadamard sur le côté gauche du circuit transforment cet état en

$$\vert \pi_1 \rangle = \vert - \rangle \vert + \rangle = \frac{1}{2} \bigl( \vert 0\rangle - \vert 1\rangle \bigr) \vert 0\rangle + \frac{1}{2} \bigl( \vert 0\rangle - \vert 1\rangle \bigr) \vert 1\rangle.$$

(Comme toujours, on suit la convention d'ordre des qubits de Qiskit, qui place le qubit du haut à droite et le qubit du bas à gauche.) Il peut sembler peu intuitif d'écrire cet état produit partiellement distribué (en laissant les états du qubit 1 factorisés séparément), mais cela rendra nos expressions ultérieures plus compactes.

Ensuite, la porte $U_f$ est appliquée. Selon la définition de la porte $U_f$, la valeur de la fonction $f$ pour l'état classique du qubit du haut/de droite est appliquée par XOR sur le qubit du bas/de gauche, ce qui transforme $\vert \pi_1\rangle$ en l'état

$$\vert \pi_2 \rangle = \frac{1}{2} \bigl( \vert 0 \oplus f(0) \rangle - \vert 1 \oplus f(0) \rangle \bigr) \vert 0 \rangle + \frac{1}{2} \bigl( \vert 0 \oplus f(1) \rangle - \vert 1 \oplus f(1) \rangle \bigr) \vert 1 \rangle.$$

On peut simplifier cette expression en observant que la formule

$$\vert 0 \oplus a\rangle - \vert 1 \oplus a\rangle = (-1)^a \bigl( \vert 0\rangle - \vert 1\rangle \bigr)$$

est valable pour les deux valeurs possibles $a\in\Sigma.$ Plus explicitement, les deux cas sont les suivants.

$$\begin{aligned} \vert 0 \oplus 0\rangle - \vert 1 \oplus 0\rangle & = \vert 0 \rangle - \vert 1 \rangle = (-1)^0 \bigl( \vert 0\rangle - \vert 1\rangle \bigr)\\ \vert 0 \oplus 1\rangle - \vert 1 \oplus 1\rangle & = \vert 1 \rangle - \vert 0\rangle = (-1)^1 \bigl( \vert 0\rangle - \vert 1\rangle \bigr) \end{aligned}$$

Ainsi, on peut exprimer $\vert\pi_2\rangle$ de manière alternative comme suit :

$$\begin{aligned} \vert\pi_2\rangle & = \frac{1}{2} (-1)^{f(0)} \bigl( \vert 0 \rangle - \vert 1 \rangle \bigr) \vert 0 \rangle + \frac{1}{2} (-1)^{f(1)} \bigl( \vert 0 \rangle - \vert 1 \rangle \bigr) \vert 1 \rangle \\ & = \vert - \rangle \biggl( \frac{(-1)^{f(0)} \vert 0\rangle + (-1)^{f(1)} \vert 1\rangle}{\sqrt{2}}\biggr). \end{aligned}$$

Il vient de se passer quelque chose d'intéressant ! Bien que l'action de la porte $U_f$ sur les états de base standard laisse le qubit du haut/de droite intact et applique le XOR de la valeur de la fonction sur le qubit du bas/de gauche, on voit ici que l'état du qubit du haut/de droite a changé (en général) tandis que l'état du qubit du bas/de gauche reste le même — étant spécifiquement dans l'état $\vert - \rangle$ avant et après l'application de la porte $U_f$. Ce phénomène est connu sous le nom de retour de phase (phase kickback), et nous en dirons plus à ce sujet sous peu.

Avec une dernière simplification, qui consiste à sortir le facteur $(-1)^{f(0)}$ de la somme, on obtient cette expression de l'état $\vert\pi_2\rangle$ :

$$\begin{aligned} \vert\pi_2\rangle & = (-1)^{f(0)} \vert - \rangle \biggl( \frac{\vert 0\rangle + (-1)^{f(0) \oplus f(1)} \vert 1\rangle}{\sqrt{2}}\biggr) \\ & = \begin{cases} (-1)^{f(0)} \vert - \rangle \vert + \rangle & \text{if $f(0) \oplus f(1) = 0$}\\[1mm] (-1)^{f(0)} \vert - \rangle \vert - \rangle & \text{if $f(0) \oplus f(1) = 1$}. \end{cases} \end{aligned}$$

Remarque : dans cette expression, on a $f(0) \oplus f(1)$ dans l'exposant de $-1$ au lieu de $f(1) - f(0),$ ce à quoi on pourrait s'attendre d'un point de vue purement algébrique, mais on obtient le même résultat dans les deux cas. Cela s'explique par le fait que la valeur $(-1)^k$ pour tout entier $k$ dépend uniquement de la parité de $k$.

En appliquant la dernière porte de Hadamard au qubit du haut, on obtient l'état

$$\vert \pi_3 \rangle = \begin{cases} (-1)^{f(0)} \vert - \rangle \vert 0 \rangle & \text{if $f(0) \oplus f(1) = 0$}\\[1mm] (-1)^{f(0)} \vert - \rangle \vert 1 \rangle & \text{if $f(0) \oplus f(1) = 1$}, \end{cases}$$

ce qui conduit au résultat correct avec probabilité $1$ lorsque le qubit de droite/du haut est mesuré.

Remarques complémentaires sur le retour de phase

Avant de poursuivre, examinons l'analyse ci-dessus sous un angle légèrement différent, qui peut éclairer le phénomène de retour de phase.

Tout d'abord, remarquons que la formule suivante est valable pour tous les choix de bits $b,c\in\Sigma.$

$$\vert b \oplus c\rangle = X^c \vert b \rangle$$

Cela peut être vérifié en le testant pour les deux valeurs possibles $c = 0$ et $c = 1$ :

$$\begin{aligned} \vert b \oplus 0 \rangle & = \vert b\rangle = \mathbb{I} \vert b \rangle = X^0 \vert b \rangle\\ \vert b \oplus 1 \rangle & = \vert \neg b\rangle = X \vert b \rangle = X^1 \vert b \rangle. \end{aligned}$$

À l'aide de cette formule, on voit que

$$U_f \bigl(\vert b\rangle \vert a \rangle\bigr) = \vert b \oplus f(a) \rangle \vert a \rangle = \bigl(X^{f(a)}\vert b \rangle\bigr) \vert a \rangle$$

pour tout choix de bits $a,b\in\Sigma.$ Comme cette formule est vraie pour $b=0$ et $b=1,$ on voit par linéarité que

$$U_f \bigl( \vert \psi \rangle \vert a \rangle \bigr) = \bigl(X^{f(a)}\vert \psi \rangle\bigr) \vert a \rangle$$

pour tous les vecteurs d'état de qubit $\vert \psi\rangle,$ et donc

$$U_f \bigl( \vert - \rangle \vert a \rangle \bigr) = \bigl(X^{f(a)} \vert - \rangle \bigr) \vert a \rangle = (-1)^{f(a)} \vert - \rangle \vert a \rangle.$$

La clé qui rend cela possible est que $X\vert - \rangle = - \vert - \rangle.$ En termes mathématiques, le vecteur $\vert - \rangle$ est un vecteur propre de la matrice $X$ avec la valeur propre $-1.$

Nous discuterons des vecteurs propres et des valeurs propres plus en détail dans la leçon à venir sur l'estimation de phase et la factorisation, où le phénomène de retour de phase est généralisé à d'autres opérations unitaires.

En gardant à l'esprit que les scalaires circulent librement dans les produits tensoriels, on trouve une autre façon de raisonner sur la manière dont l'opération $U_f$ transforme $\vert \pi_1\rangle$ en $\vert \pi_2\rangle$ dans l'analyse ci-dessus :

$$\begin{aligned} \vert \pi_2 \rangle & = U_f \bigl( \vert - \rangle \vert + \rangle \bigr)\\ & = \frac{1}{\sqrt{2}} U_f \bigl(\vert - \rangle \vert 0\rangle \bigr) + \frac{1}{\sqrt{2}} U_f \bigl(\vert - \rangle \vert 1\rangle \bigr)\\ & = \vert - \rangle \biggl( \frac{(-1)^{f(0)} \vert 0\rangle + (-1)^{f(1)} \vert 1\rangle}{\sqrt{2}}\biggr). \end{aligned}$$

Implémentation dans Qiskit

Voyons maintenant comment implémenter l'algorithme de Deutsch dans Qiskit. On commencera par une vérification de version, puis on effectuera les imports nécessaires uniquement pour cette implémentation. Pour les implémentations des autres algorithmes qui suivent, on effectuera les imports requis séparément dans un souci de meilleure modularité.

# Added by doQumentation — required packages for this notebook
!pip install -q qiskit qiskit-aer

from qiskit import __version__

print(__version__)

2.1.1

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator

On va d'abord définir un circuit quantique qui implémente une porte de requête pour l'une des quatre fonctions $f_1,$ $f_2,$ $f_3,$ ou $f_4$ d'un bit vers un bit décrites précédemment. Comme on l'a déjà mentionné, l'implémentation des portes de requête ne fait pas vraiment partie de l'algorithme de Deutsch lui-même ; ici, on montre essentiellement une façon de préparer l'entrée, sous la forme d'une implémentation en circuit d'une porte de requête.

def deutsch_function(case: int):
    # This function generates a quantum circuit for one of the 4 functions
    # from one bit to one bit

    if case not in [1, 2, 3, 4]:
        raise ValueError("`case` must be 1, 2, 3, or 4.")

    f = QuantumCircuit(2)
    if case in [2, 3]:
        f.cx(0, 1)
    if case in [3, 4]:
        f.x(1)
    return f

On peut voir à quoi ressemble chaque circuit en utilisant la méthode draw. Voici le circuit pour la fonction $f_3.$

display(deutsch_function(3).draw(output="mpl"))

Ensuite, on va créer le circuit quantique effectif pour l'algorithme de Deutsch, en remplaçant la porte de requête par une implémentation en circuit quantique fournie comme argument. Dans un instant, on branchera l'un des quatre circuits définis par la fonction deutsch_function définie plus tôt. Des barrières sont incluses pour montrer la séparation visuelle entre l'implémentation de la porte de requête et le reste du circuit.

def compile_circuit(function: QuantumCircuit):
    # Compiles a circuit for use in Deutsch's algorithm.

    n = function.num_qubits - 1
    qc = QuantumCircuit(n + 1, n)

    qc.x(n)
    qc.h(range(n + 1))

    qc.barrier()
    qc.compose(function, inplace=True)
    qc.barrier()

    qc.h(range(n))
    qc.measure(range(n), range(n))

    return qc

Encore une fois, on peut voir à quoi ressemble le circuit en utilisant la méthode draw.

display(compile_circuit(deutsch_function(3)).draw(output="mpl"))

Enfin, on va créer une fonction qui exécute le circuit défini précédemment une seule fois et affiche le résultat approprié : « constant » ou « balanced ».

def deutsch_algorithm(function: QuantumCircuit):
    # Determine if a one-bit function is constant or balanced.

    qc = compile_circuit(function)

    result = AerSimulator().run(qc, shots=1, memory=True).result()
    measurements = result.get_memory()
    if measurements[0] == "0":
        return "constant"
    return "balanced"

On peut maintenant exécuter l'algorithme de Deutsch sur n'importe laquelle des quatre fonctions définies ci-dessus.

f = deutsch_function(3)
display(deutsch_algorithm(f))

'balanced'