Algorithme d'estimation de phase quantique
En informatique quantique, l’algorithme d'estimation de phase quantique est un  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  est un vecteur propre de U, nous avons donc .
Le but de cet algorithme est de trouver la valeur de la phase  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é à , 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 .
Concernant l'opérateur unitaire U, il est uniquement requis de pouvoir l'appliquer plusieurs fois de manière contrôlé, plus exactement nous devons être capables d'appliquer les portes contrôle-, contrôle-, contrôle- et ainsi de suite jusqu'à contrôle-.

La première étape consiste à appliquer une porte de Hadamard aux n qubits du premier registre, donnant ainsi l'état
.
Ensuite, on applique au second registre les portes  contrôlées par le jème qubit du premier registre (j variant de 0 à n-1). On obtient alors l'état
.
La dernière étape consiste à appliquer une transformée de Fourier quantique inverse aux n qubits du premier registre, ce qui nous donne
.
En appelant  la meilleure approximation, à n bits, de , on obtient  avec . Et l'état précédent peut se réécrire
.
Si  alors on obtient à coup sûr la phase, sinon on obtient son approximation a avec une probabilité .

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  peut être décomposé dans la base  des vecteurs propres de U :

Auquel cas au lieu d'obtenir l'état  à la fin de l'algorithme, nous obtenons l'état

où  représente ici l'approximation de la phase  de la valeur propre  associée au vecteur propre 
Après mesure, on obtient donc (toujours avec une certaine probabilité supérieure à ) 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  qubits sont utilisés pour approximer , le coût de la transformée de Fourier quantique est en . Cependant, pour , la porte contrôle- est implémentée en appliquant la porte contrôle-  fois. De fait, en notant  le temps nécessaire pour implémenter la porte contrôle-, la complexité de l'algorithme est en .

Si l'on souhaite avoir une approximation de  à  près, alors il suffit de choisir un nombre  de qubits, aboutissant à une complexité en .

Voir aussi

Article connexe
Algorithme de Shor

Lien externe
, § 1.6.2
, § 5

Estimation
Informatique quantique