Algorithme de Deutsch

L'algorithme de Deutsch résout le problème de parité dans le cas particulier où $n = 1.$ Dans le contexte de l'informatique quantique, ce problème est parfois appelé problème de Deutsch, et nous suivrons cette nomenclature 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 à un bit. Ces fonctions sont au nombre de quatre :

La première et la dernière de ces fonctions sont constantes et les deux autres sont équilibrées, ce qui signifie que les deux valeurs de sortie possibles pour la fonction se produisent le même nombre de fois lorsque nous parcourons les entrées. Le problème de Deutsch est de déterminer à laquelle de ces deux catégories la fonction d'entrée appartient : constante ou équilibrée.

Si nous considérons la fonction d'entrée $f$ dans le problème de Deutsch comme représentant un accès aléatoire à une chaîne de caractères, nous pensons à une chaîne de deux bits : $f(0)f(1).$

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 d'interrogation classique qui résout correctement ce problème doit interroger les deux bits : $f(0)$ et $f(1).$ Si nous apprenons que $f(1) = 1,$ par exemple, la réponse pourrait toujours être $0$ ou $1,$ selon que $f(0) = 1$ ou $f(0) = 0,$ respectivement. Tous les autres cas sont similaires : la connaissance d'un seul des deux bits ne fournit aucune information sur leur parité. Le circuit booléen décrit dans la section précédente est donc le meilleur que nous puissions 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 à l'aide d'une seule requête, offrant ainsi un avantage quantifiable des calculs quantiques par rapport aux calculs classiques. Il s'agit peut-être d'un avantage modeste - une requête au lieu de deux - mais il faut bien commencer quelque part. Les avancées scientifiques ont parfois des origines apparemment modestes.

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

Analyse

Pour analyser l'algorithme de Deutsch, nous allons retracer 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 Hadamard sur le côté gauche du circuit transforment cet état en

(Comme toujours, nous suivons la convention d'ordonnancement des qubits de Qiskit, qui place le qubit supérieur à droite et le qubit inférieur à gauche) Il peut sembler peu intuitif d'écrire l'état de ce produit partiellement distribué (en laissant les états du qubit 1 pris en compte), mais cela rendra nos expressions ultérieures plus compactes.

Ensuite, la porte $U_f$ est exécutée. Selon la définition de la porte $U_f$, la valeur de la fonction $f$ pour l'état classique du qubit supérieur/le plus à droite est XORée sur le qubit inférieur/le plus à gauche, ce qui transforme $\vert \pi_1\rangle$ en l'état

Nous pouvons simplifier cette expression en observant que la formule

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

Nous pouvons donc exprimer $\vert\pi_2\rangle$ de la manière suivante :

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 supérieur/le plus à droite seul et XOR la valeur de la fonction sur le qubit inférieur/le plus à gauche, nous voyons ici que l'état du qubit supérieur/le plus à droite a changé (en général) tandis que l'état du qubit inférieur/le plus à gauche reste le même - étant spécifiquement dans l'état $\vert - \rangle$ avant et après l'exécution de la porte $U_f$. Ce phénomène est connu sous le nom de " retour de phase" et nous y reviendrons.

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

Remarquez que dans cette expression, nous avons $f(0) \oplus f(1)$ dans l'exposant de $-1$ au lieu de $f(1) - f(0),$, ce qui est ce que nous pourrions attendre d'un point de vue purement algébrique, mais nous obtenons le même résultat d'une manière ou d'une autre. En effet, la valeur $(-1)^k$ pour tout entier $k$ dépend uniquement du fait que $k$ est pair ou impair.

L'application de la dernière porte de Hadamard au qubit supérieur nous donne l'état suivant

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

Remarques supplémentaires sur le recul de phase

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

Tout d'abord, il convient de noter que la formule suivante fonctionne pour tous les choix de bits $b,c\in\Sigma.$

On peut s'en assurer en le vérifiant pour les deux valeurs possibles $c = 0$ et $c = 1$ :

En utilisant cette formule, nous constatons que

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

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

La clé de ce fonctionnement est la suivante $X\vert - \rangle = - \vert - \rangle.$ En termes mathématiques, le vecteur $\vert - \rangle$ est un vecteur propre de la matrice $X$ ayant pour valeur propre $-1.$

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

En gardant à l'esprit que les scalaires flottent librement à travers les produits tensoriels, nous trouvons une autre façon de raisonner comment l'opération $U_f$ transforme $\vert \pi_1\rangle$ en $\vert \pi_2\rangle$ dans l'analyse ci-dessus :

Implémentation dans Qiskit

Voyons maintenant comment nous pouvons implémenter l'algorithme de Deutsch dans Qiskit. Nous commencerons par vérifier la version, puis nous effectuerons les importations nécessaires uniquement pour cette mise en œuvre. Pour les implémentations d'autres algorithmes qui suivent, nous effectuerons les importations nécessaires séparément dans un souci de plus grande modularité.

from qiskit import __version__

print(__version__)

Output:

2.1.1

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator

Tout d'abord, nous allons définir un circuit quantique qui met en œuvre une porte d'interrogation pour l'une des quatre fonctions $f_1,$ $f_2,$ $f_3,$ ou $f_4$ d'un bit à un bit décrites précédemment. Comme nous l'avons déjà mentionné, la mise en œuvre des portes d'interrogation ne fait pas vraiment partie de l'algorithme de Deutsch lui-même; ici, nous montrons essentiellement une façon de préparer l'entrée, sous la forme d'une implémentation de circuit d'une porte d'interrogation.

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

Nous pouvons voir à quoi ressemble chaque circuit en utilisant la méthode draw . Voici le circuit de la fonction $f_3.$

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

Output:

Ensuite, nous créerons le circuit quantique réel pour l'algorithme de Deutsch, en remplaçant la porte d'interrogation par une implémentation de circuit quantique donnée en argument. Nous brancherons bientôt l'un des quatre circuits définis par la fonction deutsch_function que nous avons définie plus tôt. Des barrières sont incluses pour montrer la séparation visuelle entre l'implémentation de la porte d'interrogation 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

Une fois de plus, nous pouvons voir à quoi ressemble le circuit en utilisant la méthode draw .

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

Output:

Enfin, nous créerons une fonction qui exécutera une fois le circuit défini précédemment et produira le résultat approprié : "constant" ou "équilibré"

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"

Nous pouvons 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))

Output:

'balanced'