Algorithme d'estimation de phase quantique

Représentation du Modèle:Lien de l'algorithme d'estimation de phase

En informatique quantique, l’algorithme d'estimation de phase quantique est un Modèle:Lien permettant d'estimer la valeur propre (ou sa phase, ce qui, dans ce cas précis, est équivalent) d'un opérateur unité associée à un vecteur propre donné.

Le problème

Les valeurs propres d'un opérateur unitaire U, agissant sur m bits, sont de module 1. Si $|\psi ⟩$ est un vecteur propre de U, nous avons donc $U|\psi ⟩=e^{i\theta }|\psi ⟩$. Le but de cet algorithme est de trouver la valeur de la phase $\theta$ correspondant à un vecteur propre donné, ceci avec une précision de n bits (la phase n'a pas nécessairement une valeur exacte).

L'algorithme

Cas où le vecteur propre est connu

L'algorithme utilise deux registres quantiques : un registre de n bits initialisé à $|0⟩$, c'est lui qui contiendra la valeur de la phase en sortie de l'algorithme, et un registre de m bits initialisé avec le vecteur propre $|\psi ⟩$. Concernant l'opérateur unitaire U, il est uniquement requis de pouvoir l'appliquer plusieurs fois de manière contrôlée, plus exactement nous devons être capables d'appliquer les portes contrôle-$U$, contrôle-$U^2$, contrôle-$U^4$ et ainsi de suite jusqu'à contrôle-$U^{2^{n-1}}$.

La première étape consiste à appliquer une porte de Hadamard aux n qubits du premier registre, donnant ainsi l'état

$\frac{1}{\sqrt{2^n}}\sum _x|x⟩\otimes |\psi ⟩$.

Ensuite, on applique au second registre les portes $U^{2^{j-1}}$ contrôlées par le j^ème qubit du premier registre (j variant de 0 à n-1). On obtient alors l'état

$\frac{1}{\sqrt{2^n}}\sum _x{e}^{ix\theta }|x⟩\otimes |\psi ⟩$.

La dernière étape consiste à appliquer une transformée de Fourier quantique inverse aux n qubits du premier registre, ce qui nous donne

$\frac{1}{2^n}\sum _y\sum _x{e}^{-2\pi ix\cdot y/2^n}{e}^{ix\theta }|y⟩\otimes |\psi ⟩$.

En appelant $\frac{a}{2^n}=\frac{a_1}{2}+\frac{a_2}{4}+\cdots +\frac{a_n}{2^n}\equiv 0.a_1.a_2\dots a_n$ la meilleure approximation, à n bits, de $\theta$, on obtient $\theta =\frac{a}{2^n}+\delta$ avec $0<\delta <\frac{1}{2^{n+1}}$. Et l'état précédent peut se réécrire

$\frac{1}{2^n}\sum _y{e}^{-2\pi i\delta \cdot y}|a⟩\otimes |\psi ⟩=\frac{1}{2^n}\frac{1-e^{2\pi i\delta 2^n}}{1-e^{2\pi i\delta }}|a⟩\otimes |\psi ⟩$.

Si $\delta =0$ alors on obtient à coup sûr la phase, sinon on obtient son approximation a avec une probabilité ${\left|\frac{1}{2^n}\frac{1-e^{2\pi i\delta 2^n}}{1-e^{2\pi i\delta }}\right|}^2\ge \frac{4}{{\pi }^2}$.

Cas où les vecteurs propres ne sont pas connus

Il n'est pas nécessaire de connaitre un vecteur propre à l'avance pour réaliser cet algorithme. En effet tout état $|\psi ⟩$ peut être décomposé dans la base $|{\psi }_i⟩$ des vecteurs propres de U :

$|\psi ⟩=\sum _i{c}_i|{\psi }_i⟩$

Auquel cas au lieu d'obtenir l'état $|a⟩\otimes |\psi ⟩$ à la fin de l'algorithme, nous obtenons l'état

$\sum _i|a_i⟩\otimes |{\psi }_i⟩$

où $a_i$ représente ici l'approximation de la phase ${\theta }_i$ de la valeur propre $e^{i{\theta }_i}$ associée au vecteur propre $|{\psi }_i⟩$ Après mesure, on obtient donc (toujours avec une certaine probabilité supérieure à $4/{\pi }^2$) une des valeurs propres, ainsi que le vecteur propre associé. Le choix de la valeur propre est aléatoire et suit la règle de Born.

Complexité

Lorsque $n$ qubits sont utilisés pour approximer $\theta$, le coût de la transformée de Fourier quantique est en $O\left(n^2\right)$. Cependant, pour $0⩽i⩽n-1$, la porte contrôle-$U^{2^i}$ est implémentée en appliquant la porte contrôle-$U$ $2^i$ fois. De fait, en notant $T_U$ le temps nécessaire pour implémenter la porte contrôle-$U$, la complexité de l'algorithme est en $O\left(T_U{2}^n\right)$.

Si l'on souhaite avoir une approximation de $\theta$ à $\epsilon$ près, alors il suffit de choisir un nombre $n=\lceil {\log }_2\left(\frac{1}{\epsilon }\right)\rceil$ de qubits, aboutissant à une complexité en $O(T_U/\epsilon )$.

Voir aussi

Article connexe

Algorithme de Shor

Lien externe

Modèle:Article, § 1.6.2 Modèle:Article, § 5