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 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 , où 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 , 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[3].

Définition

[modifier | modifier le code]

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 :

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

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

Propriétés

[modifier | modifier le code]

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

[modifier | modifier le code]

Les portes quantiques utilisées dans ce circuit sont la porte d'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

Circuit quantique pour Quantum-Fourier-Transform avec n qubits (sans réarranger l'ordre des états de sortie). Il utilise la notation de fraction binaire présentée ci-dessous.

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[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 portes de phase contrôlées, la suivante nécessite une porte d'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.

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

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

QFT pour 3 Qubits (sans réorganiser l'ordre des qubits de sortie)

Comme calculé ci-dessus, le nombre de portes utilisées est qui est égal à , pour .

Relation avec la transformée d'Hadamard quantique

[modifier | modifier le code]

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

[modifier | modifier le code]
  1. Coppersmith, « An approximate Fourier transform useful in quantum factoring. », Technical Report RC19642, IBM,‎
  2. a et b Michael Nielsen and Isaac Chuang, Quantum Computation and Quantum Information, Cambridge, Cambridge University Press, (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, CiteSeerx 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

[modifier | modifier le code]