Algorithme d'estimation de phase quantique

L'algorithme utilise deux registres quantiques : un registre de n bits initialisé à ${\displaystyle \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 ${\displaystyle \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ée, plus exactement nous devons être capables d'appliquer les portes contrôle-${\displaystyle U}$, contrôle-${\displaystyle U^{2}}$, contrôle-${\displaystyle U^{4}}$ et ainsi de suite jusqu'à contrôle-${\displaystyle U^{2^{n-1}}}$.

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

${\displaystyle {\frac {1}{\sqrt {2^{n}}}}\sum _{x}\left|x\right\rangle \otimes \left|\psi \right\rangle }$.

Ensuite, on applique au second registre les portes ${\displaystyle 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

${\displaystyle {\frac {1}{\sqrt {2^{n}}}}\sum _{x}e^{ix\theta }\left|x\right\rangle \otimes \left|\psi \right\rangle }$.

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

${\displaystyle {\frac {1}{2^{n}}}\sum _{y}\sum _{x}e^{-2\pi ix\cdot y/2^{n}}e^{ix\theta }\left|y\right\rangle \otimes \left|\psi \right\rangle }$.

En appelant ${\displaystyle {\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 meilleure approximation, à n bits, de ${\displaystyle \theta }$, on obtient ${\displaystyle \theta ={\frac {a}{2^{n}}}+\delta }$ avec ${\displaystyle 0<\delta <{\frac {1}{2^{n+1}}}}$. Et l'état précédent peut se réécrire

${\displaystyle {\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 ${\displaystyle \delta =0}$ alors on obtient à coup sûr la phase, sinon on obtient son approximation a avec une probabilité ${\displaystyle \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}}}}$.

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

${\displaystyle \left|\psi \right\rangle =\sum _{i}c_{i}\left|\psi _{i}\right\rangle }$

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

${\displaystyle \sum _{i}\left|a_{i}\right\rangle \otimes \left|\psi _{i}\right\rangle }$

où ${\displaystyle a_{i}}$ représente ici l'approximation de la phase ${\displaystyle \theta _{i}}$ de la valeur propre ${\displaystyle e^{i\theta _{i}}}$ associée au vecteur propre ${\displaystyle \left|\psi _{i}\right\rangle }$ Après mesure, on obtient donc (toujours avec une certaine probabilité supérieure à ${\displaystyle 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.

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

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

Algorithme de Shor

Alexandre Blais, « Algorithmes et architectures pour ordinateurs quantiques supraconducteurs », Annales de physique, vol. 28, n^o 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

• Portail de l'analyse
• Portail des sciences quantiques