Algorithme d'estimation de phase quantique 📖 Wikipedia

Les valeurs propres d'un opérateur unitaire U, agissant sur m bits, sont de module 1. Si ${\displaystyle \left|\psi \right\rangle }$  est un vecteur propre de U, nous avons donc ${\displaystyle 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 ${\displaystyle \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 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