Algorithme d'estimation de phase quantique

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Représentation du circuit quantique (en) de l'algorithme d'estimation de phase

En informatique quantique, l’algorithme d'estimation de phase quantique est un algorithme quantique (en) 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[modifier | modifier le code]

Les valeurs propres d'un opérateur unitaire U, agissant sur m bits, sont de module 1. Si \left| \psi \right\rangle est un vecteur propre de U, nous avons donc U\left| \psi \right\rangle =  e^{ i \theta}\left|\psi \right\rangle. 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[modifier | modifier le code]

Cas où le vecteur propre est connu[modifier | modifier le code]

L'algorithme utilise deux registres quantiques : un registre de n bits initialisé à \left| 0 \right\rangle, 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 \left| \psi \right\rangle. 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-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 \left| x \right\rangle \otimes \left| \psi \right\rangle.

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^{ i x\theta} \left| x \right\rangle \otimes \left| \psi \right\rangle.

La dernière étape consiste a 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 i x\cdot y/2^n} e^{ ix\theta} \left| y \right\rangle \otimes \left| \psi \right\rangle.

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\ldots a_n la meilleur 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} \left| a \right\rangle \otimes \left| \psi \right\rangle = \frac{1}{2^n}  \frac{1-e^{2\pi i \delta 2^n}}{1-e^{2\pi i \delta}} \left| a \right\rangle \otimes \left| \psi \right\rangle.

Si \delta=0 alors on obtient à coup sûr la phase, sinon on obtient son apxormixation 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 \geq \frac{4}{\pi^2}.

Cas où les vecteurs propres ne sont pas connus[modifier | modifier le code]

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

\left| \psi \right\rangle = \sum_i c_i \left| \psi_i\right\rangle

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

\sum_i \left| a_i \right\rangle \otimes \left| \psi_i \right\rangle

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 \left| \psi_i \right\rangle 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.

Voir aussi[modifier | modifier le code]

Article connexe[modifier | modifier le code]

Algorithme de Shor

Lien externe[modifier | modifier le code]

Alexandre Blais, « Algorithmes et architectures pour ordinateurs quantiques supraconducteurs », Annales de physique, vol. 28, no 5,‎ 2003, p. 1-147, § 1.6.2 (en) R. Cleve, A. Ekert, C. Macchiavello, et M. Mosca, « Quantum algorithms revisited », Proceedings of the Royal Society of London A, vol. 454,‎ 1998, p. 339-354 (lire en ligne [PDF]), § 5