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.

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. A l'aide de cette décomposition, la transformée de Fourier discrète sur amplitudes peut être mises en œuvre sous la forme d'un circuit quantique avec un nombre de Portes d' Hadamard et de portes à déphasage commandé évoluant en  , où  est le nombre de qubits (le nombre de porte évolue selon une fonction en n^2). En comparaison, la transformée de Fourier discrète classique requiert un nombre de porte évoluant en  , soit exponentiellement supérieur à .

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  de portes pour obtenir une approximation efficace.

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  .

La transformée de Fourier classique agit sur un vecteur  et lui associe le vecteur  selon la formule :

 

où  et  est une racine N -ième de l'unité.

De même, la transformée de Fourier quantique agit sur un état quantique  et renvoie un état quantique  selon la formule :

 

(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é  est une rotation de  , la transformée de Fourier quantique inverse agit de manière similaire mais avec :

 

Si  est un état de base, la transformée de Fourier quantique peut également être exprimée ainsi

 

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  est donné par

 

où  . Par exemple, dans le cas de  et la phases  la matrice de transformation devient alors

Propriétés

Unitarité 
La plupart des propriétés de la transformée de Fourier quantique se deduisent 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  détient, où  est l'adjoint hermitien de  . 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ù  . 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 Hadamard et les portes de phase 

 

avec  la primitive  -ème racine de l'unité. Le circuit est composé de portes  et des versions contrôlée de 

On suppose  . L'on a une base orthonormée constituée des vecteurs

 

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

 

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

 

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

 

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

 

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   échanges sont nécessaires.

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, ce qui suggère qu'elle est facilement représentée comme un circuit quantique (jusqu'à  une inversion de l'ordre de sortie). En effet, chacune des opérations affectant un seul qubit peuvent être mise en œuvre efficacement à l'aide d'une porte Hadamard et de portes à phase contrôlées. Le premier terme nécessite une porte Hadamard et  portes de phase contrôlées, la suivante nécessite une porte Hadamard et  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  portes, ce qui est un polynôme quadratique en nombre de qubits.

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

 

où  est une racine huitième de l'unité satisfaisant  (puisque  ).

En posant , la représentation matricielle de cette transformation sur 3 qubits est :

 

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

 

Dans le schéma suivant, nous avons le circuit respectif pour  (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  qui est égal à , pour  .

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  . Cependant, il est également logique de considérer les qubits comme indexés par le groupe booléen , et dans ce cas la transformée de Fourier est la transformée de Hadamard. Ceci est fait en appliquant une porte Hadamard à chacun des n qubits en parallèle. Notez que l'algorithme de Shor utilise les deux types de transformées de Fourier, à la fois une transformée de Hadamard initiale et uneTFQ.

Références 

 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

Théorie de Fourier
Transformée