Transformée de Fourier quantique

En informatique quantique, la transformée de Fourier quantique (TFQ) est une transformation linéaire sur des bits quantiques, et est l'analogie quantique de la transformée de Fourier discrète. La transformée de Fourier quantique est l'un des nombreux algorithmes quantiques, qui incluent notamment l'algorithme de Shor qui permet de factoriser et de calculer le logarithme discret, l'algorithme d'estimation de phase quantique qui estime les valeurs propres d'un opérateur unitaire et les algorithmes traitant du problème de sous-groupe caché. La transformée de Fourier quantique a été découverte par Don Coppersmith^[1].

La transformée de Fourier quantique peut être calculée efficacement à l'aide d'un ordinateur quantique, en utilisant une décomposition en un produit de matrices unitaires plus simples. À l'aide de cette décomposition, la transformée de Fourier discrète sur ${\displaystyle 2^{n}}$amplitudes peut être mise en œuvre sous la forme d'un circuit quantique avec un nombre de Portes d'Hadamard et de portes à déphasage commandé évoluant en ${\displaystyle O(n^{2})}$, où ${\displaystyle n}$ est le nombre de qubits^[2] (le nombre de portes évolue selon une fonction en n^2). En comparaison, la transformée de Fourier discrète classique requiert un nombre de portes évoluant en ${\displaystyle O(n2^{n})}$, soit exponentiellement supérieur à ${\displaystyle O(n^{2})}$.

La transformée de Fourier quantique agit sur un vecteur d'état quantique, tandis que la transformée de Fourier classique agit sur un vecteur (classique). Dans les deux cas, ces vecteurs peuvent être écrits sous la forme de listes de nombres complexes. En ce qui concerne le cas quantique, ces nombres complexes représentent les amplitudes de probabilité des différents résultats obtenables par la mesure. Étant donné que la mesure réduit l'état quantique à une seule valeur (appelée état de base ou état propre), il n'est pas possible de profiter de l'accélération exponentielle apportée par la transformée de Fourier quantique pour chacune des tâches impliquant la transformée de Fourrier classique : la mesure d'un état quantique étant irréversible, on ne peut utiliser la transformée quantique comme raccourci que si cela n'implique qu'une seule mesure.

Les meilleurs algorithmes de transformée de Fourier quantique connus à ce jour (à la fin des années 2000) ne nécessitent qu'un nombre en ${\displaystyle O(n\log n)}$ de portes pour obtenir une approximation efficace^[3].

Définition

La transformée de Fourier quantique est la transformée de Fourier discrète classique appliquée au vecteur d'amplitudes d'un état quantique, où l'on considère habituellement des vecteurs de longueur ${\displaystyle N=2^{n}}$.

La transformée de Fourier classique agit sur un vecteur ${\displaystyle (x_{0},x_{1},\ldots ,x_{N-1})\in \mathbb {C} ^{N}}$ et lui associe le vecteur ${\displaystyle (y_{0},y_{1},\ldots ,y_{N-1})\in \mathbb {C} ^{N}}$ selon la formule :

${\displaystyle y_{k}={\frac {1}{\sqrt {N}}}\sum _{n=0}^{N-1}x_{n}\omega _{N}^{-kn},\quad k=0,1,2,\ldots ,N-1,}$

où ${\displaystyle \omega _{N}=e^{\frac {2\pi i}{N}}}$ et ${\displaystyle \omega _{N}^{n}}$ est une racine N -ième de l'unité.

De même, la transformée de Fourier quantique agit sur un état quantique ${\textstyle |x\rangle =\sum _{i=0}^{N-1}x_{i}|i\rangle }$ et renvoie un état quantique ${\textstyle \sum _{i=0}^{N-1}y_{i}|i\rangle }$ selon la formule :

${\displaystyle y_{k}={\frac {1}{\sqrt {N}}}\sum _{n=0}^{N-1}x_{n}\omega _{N}^{nk},\quad k=0,1,2,\ldots ,N-1,}$

(Les conventions pour le signe de l'exposant du facteur de phase varient ; ici, l'on suit la convention telle que la transformée de Fourier quantique a le même effet que la transformée de Fourier discrète inverse, et vice versa. )

Étant donné ${\displaystyle \omega _{N}^{n}}$ est une rotation de ${\displaystyle \omega _{N}}$ , la transformée de Fourier quantique inverse agit de manière similaire, mais avec :

${\displaystyle x_{n}={\frac {1}{\sqrt {N}}}\sum _{k=0}^{N-1}y_{k}\omega _{N}^{-nk},\quad n=0,1,2,\ldots ,N-1,}$

Si ${\displaystyle |x\rangle }$ est un état de base, la transformée de Fourier quantique peut également être exprimée ainsi

${\displaystyle {\text{TFQ}}:|x\rangle \mapsto {\frac {1}{\sqrt {N}}}\sum _{k=0}^{N-1}\omega _{N}^{xk}|k\rangle .}$

De manière équivalente, la transformée de Fourier quantique peut être considérée comme une matrice unitaire (ou porte quantique ) agissant sur des vecteurs d'état quantiques, où la matrice unitaire ${\displaystyle F_{N}}$ est donné par

${\displaystyle F_{N}={\frac {1}{\sqrt {N}}}{\begin{bmatrix}1&1&1&1&\cdots &1\\1&\omega &\omega ^{2}&\omega ^{3}&\cdots &\omega ^{N-1}\\1&\omega ^{2}&\omega ^{4}&\omega ^{6}&\cdots &\omega ^{2(N-1)}\\1&\omega ^{3}&\omega ^{6}&\omega ^{9}&\cdots &\omega ^{3(N-1)}\\\vdots &\vdots &\vdots &\vdots &&\vdots \\1&\omega ^{N-1}&\omega ^{2(N-1)}&\omega ^{3(N-1)}&\cdots &\omega ^{(N-1)(N-1)}\end{bmatrix}}}$

où ${\displaystyle \omega =\omega _{N}}$. Par exemple, dans le cas où ${\displaystyle N=4=2^{2}}$ et où la phase ${\displaystyle \omega =i}$ la matrice de transformation devient alors

${\displaystyle F_{4}={\frac {1}{2}}{\begin{bmatrix}1&1&1&1\\1&i&-1&-i\\1&-1&1&-1\\1&-i&-1&i\end{bmatrix}}}$

Propriétés

Unitarité

La plupart des propriétés de la transformée de Fourier quantique se déduisent du fait qu'il s'agit d'une transformation unitaire. Ceci peut être vérifié en effectuant une multiplication matricielle et en s'assurant que la relation ${\displaystyle FF^{\dagger }=F^{\dagger }F=I}$ détient, où ${\displaystyle F^{\dagger }}$ est l'adjoint hermitien de ${\displaystyle F}$. Alternativement, on peut vérifier que les vecteurs orthogonaux de norme 1 ont pour image des vecteurs orthogonaux de norme 1.

Du fait que la transformée soit unitaire, il s'ensuit que son inverse est l'adjoint hermitien de la matrice de Fourier, d'où ${\displaystyle F^{-1}=F^{\dagger }}$. Puisqu'il existe un circuit quantique efficace mettant en œuvre la transformée de Fourier quantique, ce même circuit peut être utilisé dans le sens opposé afin de calculer la transformée de Fourier quantique inverse. Ainsi, ces deux transformations peuvent être effectuées efficacement sur un ordinateur quantique.

Structure pratique du circuit

Les portes quantiques utilisées dans ce circuit sont la porte d'Hadamard et les portes de phase ${\displaystyle R_{m}}$

${\displaystyle H={\frac {1}{\sqrt {2}}}{\begin{pmatrix}1&1\\1&-1\end{pmatrix}}\qquad {\text{and}}\qquad R_{m}={\begin{pmatrix}1&0\\0&e^{2\pi i/2^{m}}\end{pmatrix}}}$

avec ${\displaystyle e^{2\pi i/2^{m}}=\omega _{m}'=\omega _{\left(2^{m}\right)}}$ la primitive ${\displaystyle 2^{m}}$ -ème racine de l'unité. Le circuit est composé de portes ${\displaystyle H}$ et des versions contrôlée de ${\displaystyle R_{m}}$

On suppose ${\displaystyle N=2^{n}}$. L'on a une base orthonormée constituée des vecteurs

${\displaystyle |0\rangle ,\ldots ,|2^{n}-1\rangle .}$

Les états de base incluent tous les états possibles des qubits :

${\displaystyle |x\rangle =|x_{1}x_{2}\ldots x_{n}\rangle =|x_{1}\rangle \otimes |x_{2}\rangle \otimes \cdots \otimes |x_{n}\rangle }$

où, avec la notation du produit tensoriel (ou produit de Kronecker) ${\displaystyle \otimes }$, ${\displaystyle |x_{j}\rangle }$ indique ce qubit ${\displaystyle j}$ est en état ${\displaystyle x_{j}}$, avec ${\displaystyle x_{j}}$ soit 0 soit 1. Par convention, l'indice d'état de base ${\displaystyle x}$ est le nombre binaire codé par le ${\displaystyle x_{j}}$, avec ${\displaystyle x_{1}}$ le bit le plus significatif. Ainsi, nous pouvons écrire la transformée de Fourier quantique comme suit :

${\displaystyle {\text{TFQ}}(|x\rangle )={\frac {1}{\sqrt {N}}}\bigotimes _{j=1}^{n}\left(|0\rangle +\omega _{n}'^{x2^{n-j}}|1\rangle \right).}$

Il est également utile d'emprunter la notation binaire fractionnaire :

${\displaystyle [0.x_{1}\ldots x_{m}]=\sum _{k=1}^{m}x_{k}2^{-k}.}$

Avec cette notation, la transformée de Fourier quantique peut s'exprimer de manière compacte :

${\displaystyle {\text{TFQ}}(|x_{1}x_{2}\ldots x_{n}\rangle )={\frac {1}{\sqrt {N}}}\ \left(|0\rangle +e^{2\pi i\,[0.x_{n}]}|1\rangle \right)\otimes \left(|0\rangle +e^{2\pi i\,[0.x_{n-1}x_{n}]}|1\rangle \right)\otimes \cdots \otimes \left(|0\rangle +e^{2\pi i\,[0.x_{1}x_{2}\ldots x_{n}]}|1\rangle \right).}$

Afin d'obtenir cet état à partir du circuit décrit ci-dessus, une opération d'échange des qubits doit être effectuée pour inverser leur ordre. Au plus ${\displaystyle n/2}$ échanges sont nécessaires^[2].

En d'autres termes, la transformée de Fourier discrète, une opération sur n qubits, peut être factorisée comme le produit tensoriel de n opérations à un seul qubit. Cela suggère qu'elle peut être facilement représentée comme un circuit quantique (à une inversion de l'ordre de sortie près). En effet, chacune des opérations affectant un seul qubit peuvent être mise en œuvre efficacement à l'aide d'une porte d'Hadamard et de portes à phase contrôlées. Le premier terme nécessite une porte d'Hadamard et ${\displaystyle (n-1)}$ portes de phase contrôlées, la suivante nécessite une porte d'Hadamard et ${\displaystyle (n-2)}$ porte de phase contrôlée, et chaque terme suivant nécessite une porte à phase contrôlée de moins. En additionnant le nombre de portes, à l'exclusion de celles nécessaires à l'inversion de sortie, on obtient ${\displaystyle n+(n-1)+\cdots +1=n(n+1)/2=O(n^{2})}$ portes, ce qui est un polynôme quadratique en nombre de qubits.

Exemple

Considérons la transformée de Fourier quantique à trois qubits. Il s'agit de la transformation suivante :

${\displaystyle {\text{TFQ}}:|x\rangle \mapsto {\frac {1}{\sqrt {2^{3}}}}\sum _{k=0}^{2^{3}-1}\omega _{3}'^{xk}|k\rangle ,}$

où ${\displaystyle \omega _{3}'=\omega _{\left(2^{3}\right)}}$ est une racine huitième de l'unité satisfaisant ${\displaystyle \omega _{3}'^{8}=\left(e^{\frac {2\pi i}{2^{3}}}\right)^{8}=1}$ (puisque ${\displaystyle N=2^{3}=8}$).

En posant ${\displaystyle \omega =\omega _{3}'=\omega _{8}}$, la représentation matricielle de cette transformation sur 3 qubits est :

${\displaystyle F_{2^{3}}={\frac {1}{\sqrt {2^{3}}}}{\begin{bmatrix}1&1&1&1&1&1&1&1\\1&\omega &\omega ^{2}&\omega ^{3}&\omega ^{4}&\omega ^{5}&\omega ^{6}&\omega ^{7}\\1&\omega ^{2}&\omega ^{4}&\omega ^{6}&1&\omega ^{2}&\omega ^{4}&\omega ^{6}\\1&\omega ^{3}&\omega ^{6}&\omega &\omega ^{4}&\omega ^{7}&\omega ^{2}&\omega ^{5}\\1&\omega ^{4}&1&\omega ^{4}&1&\omega ^{4}&1&\omega ^{4}\\1&\omega ^{5}&\omega ^{2}&\omega ^{7}&\omega ^{4}&\omega &\omega ^{6}&\omega ^{3}\\1&\omega ^{6}&\omega ^{4}&\omega ^{2}&1&\omega ^{6}&\omega ^{4}&\omega ^{2}\\1&\omega ^{7}&\omega ^{6}&\omega ^{5}&\omega ^{4}&\omega ^{3}&\omega ^{2}&\omega \\\end{bmatrix}}.}$

La transformée de Fourier quantique à 3 qubits peut être réécrite comme suit :

${\displaystyle {\text{TFQ}}(|x_{1},x_{2},x_{3}\rangle )={\frac {1}{\sqrt {2^{3}}}}\ \left(|0\rangle +e^{2\pi i\,[0.x_{3}]}|1\rangle \right)\otimes \left(|0\rangle +e^{2\pi i\,[0.x_{2}x_{3}]}|1\rangle \right)\otimes \left(|0\rangle +e^{2\pi i\,[0.x_{1}x_{2}x_{3}]}|1\rangle \right).}$

Dans le schéma suivant, nous avons le circuit respectif pour ${\displaystyle n=3}$ (l'ordre des qubits de sortie étant inversé par rapport à la TFQ à proprement parler):

Comme calculé ci-dessus, le nombre de portes utilisées est ${\displaystyle n(n+1)/2}$ qui est égal à ${\displaystyle 6}$, pour ${\displaystyle n=3}$.

Relation avec la transformée d'Hadamard quantique

En utilisant la transformée de Fourier généralisée sur des groupes finis (abéliens), il existe en fait deux manières naturelles de définir une transformée de Fourier quantique sur un registre quantique à n qubits. La TFQ tel que définie ci-dessus est équivalente à la TFD, qui considère ces n qubits comme indexés par le groupe cyclique ${\displaystyle \mathbb {Z} /2^{n}\mathbb {Z} }$. Cependant, il est également logique de considérer les qubits comme indexés par le groupe booléen ${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}}$, et dans ce cas la transformée de Fourier est la transformée d'Hadamard. Ceci est fait en appliquant une porte d'Hadamard à chacun des n qubits en parallèle^[4],[5]. Notez que l'algorithme de Shor utilise les deux types de transformées de Fourier, à la fois une transformée d'Hadamard initiale et une TFQ.

Références

1. Coppersmith, « An approximate Fourier transform useful in quantum factoring. », Technical Report RC19642, IBM,‎ 1994
2. Michael Nielsen and Isaac Chuang, Quantum Computation and Quantum Information, Cambridge, Cambridge University Press, 2000 (ISBN 0-521-63503-9, OCLC 174527496)
3. Hales et Hallgren, « An improved quantum Fourier transform algorithm and applications », Proceedings 41st Annual Symposium on Foundations of Computer Science,‎ november 12–14, 2000, p. 515–525 (ISBN 0-7695-0850-2, DOI 10.1109/SFCS.2000.892139, S2CID 424297, CiteSeer^x 10.1.1.29.4161)
4. Fourier Analysis of Boolean Maps– A Tutorial –, pp. 12-13
5. Lecture 5: Basic quantum algorithms, Rajat Mittal, pp. 4-5

• KR Parthasarathy, Conférences sur le calcul quantique et les codes de correction d'erreurs quantiques (Indian Statistical Institute, Delhi Center, juin 2001)
• John Preskill, Notes de Conférences pour la Physique 229 : Information quantique et Calcul (CIT, septembre 1998)

Liens externes

• Wolfram Demonstration Project: Quantum Circuit Implementing Grover's Search Algorithm
• Wolfram Demonstration Project: Quantum Circuit Implementing Quantum Fourier Transform
• Quirk online life quantum fourier transform

• Portail de l’informatique