La mise en forme de cet article est à améliorer (juin 2022).

La mise en forme du texte ne suit pas les recommandations de Wikipédia : il faut le « wikifier ».

Comment faire ?

Les points d'amélioration suivants sont les cas les plus fréquents. Le détail des points à revoir est peut-être précisé sur la page de discussion.

• Les titres sont pré-formatés par le logiciel. Ils ne sont ni en capitales, ni en gras.
• Le texte ne doit pas être écrit en capitales (les noms de famille non plus), ni en gras, ni en italique, ni en « petit »…
• Le gras n'est utilisé que pour surligner le titre de l'article dans l'introduction, une seule fois.
• L'italique est rarement utilisé : mots en langue étrangère, titres d'œuvres, noms de bateaux, etc.
• Les citations ne sont pas en italique mais en corps de texte normal. Elles sont entourées par des guillemets français : « et ».
• Les listes à puces sont à éviter, des paragraphes rédigés étant largement préférés. Les tableaux sont à réserver à la présentation de données structurées (résultats, etc.).
• Les appels de note de bas de page (petits chiffres en exposant, introduits par l'outil «  Source ») sont à placer entre la fin de phrase et le point final^{[comme ça]}.
• Les liens internes (vers d'autres articles de Wikipédia) sont à choisir avec parcimonie. Créez des liens vers des articles approfondissant le sujet. Les termes génériques sans rapport avec le sujet sont à éviter, ainsi que les répétitions de liens vers un même terme.
• Les liens externes sont à placer uniquement dans une section « Liens externes », à la fin de l'article. Ces liens sont à choisir avec parcimonie suivant les règles définies. Si un lien sert de source à l'article, son insertion dans le texte est à faire par les notes de bas de page.
• La présentation des références doit suivre les conventions bibliographiques. Il est recommandé d'utiliser les modèles {{Ouvrage}}, {{Chapitre}}, {{Article}}, {{Lien web}} et/ou {{Bibliographie}}. Le mode d'édition visuel peut mettre en forme automatiquement les références.
• Insérer une infobox (cadre d'informations à droite) n'est pas obligatoire pour parachever la mise en page.

Pour une aide détaillée, merci de consulter Aide:Wikification.

Si vous pensez que ces points ont été résolus, vous pouvez retirer ce bandeau et améliorer la mise en forme d'un autre article.

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].

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}}}$

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.

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.

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}$.

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.

Certaines informations figurant dans cet article ou cette section devraient être mieux reliées aux sources mentionnées dans les sections « Bibliographie », « Sources » ou « Liens externes » (juin 2022).

Vous pouvez améliorer la vérifiabilité en associant ces informations à des références à l'aide d'appels de notes.

• 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)

• 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