Transformée de Fourier quantique

Pour ce module Qiskit in Classrooms, les étudiants doivent disposer d'un environnement Python fonctionnel avec les paquets suivants installés :

• qiskit v2.1.0 ou plus récent
• qiskit-ibm-runtime v0.40.1 ou plus récent
• qiskit-aer v0.17.0 ou plus récent
• qiskit.visualization
• numpy
• pylatexenc

Pour configurer et installer les paquets ci-dessus, voir le guide d' installation de Qiskit. Afin d'exécuter des tâches sur de véritables ordinateurs quantiques, les étudiants devront créer un compte sur IBM Quantum® en suivant les étapes du guide Configurer votre compte IBM Cloud.

Ce module a été testé et a utilisé 13 secondes de temps QPU. Il s'agit d'une estimation de bonne foi; votre utilisation réelle peut varier.

# Uncomment and modify this line as needed to install dependencies
#!pip install 'qiskit>=2.1.0' 'qiskit-ibm-runtime>=0.40.1' 'qiskit-aer>=0.17.0' 'numpy' 'pylatexenc'

Présentation

La transformée de Fourier est un outil omniprésent qui trouve des applications dans les mathématiques, la physique, le traitement des signaux, la compression des données et d'innombrables autres domaines. Une version quantique de la transformée de Fourier, appelée à juste titre transformée de Fourier quantique, constitue la base de certains des algorithmes quantiques les plus importants.

Aujourd'hui, après un rappel de la transformée de Fourier classique, nous verrons comment mettre en œuvre la transformée de Fourier quantique sur un ordinateur quantique. Nous examinerons ensuite l'une des applications de la transformée de Fourier quantique à un algorithme appelé algorithme d'estimation de phase. L'estimation de la phase quantique est un sous-programme du célèbre algorithme de factorisation de Shor, qui est parfois considéré comme le "joyau de la couronne" de l'informatique quantique. Ce module s'inscrit dans le prolongement d'un autre module consacré à l'algorithme de Shor, mais il est également conçu pour être autonome. La transformée de Fourier quantique est un algorithme fascinant et utile en soi!

La transformée de Fourier classique

Avant d'aborder la transformée de Fourier quantique, rappelons d'abord la version classique. La transformée de Fourier est une méthode de transformation d'une "base" en une autre. Vous pouvez considérer les deux bases comme des perspectives différentes du même problème - ce sont toutes deux des façons valables d'exprimer une fonction, mais l'une ou l'autre peut être plus éclairante, en fonction du problème en question. Quelques exemples de paires de bases reliées par la transformée de Fourier sont la position et la quantité de mouvement, ainsi que le temps et la fréquence.

Voyons comment la transformée de Fourier peut nous aider à déterminer la note jouée par un instrument à partir de sa forme d'onde audio. En général, les formes d'onde sont représentées dans le temps, c'est-à-dire que l'amplitude de l'onde est exprimée en fonction du temps.

Nous pouvons transformer cette forme d'onde en Fourier pour passer de la base temporelle à la base fréquentielle :

Dans la base de fréquence, nous pouvons facilement voir un pic clair à environ 260 Hz. C'est un do du milieu!

Vous auriez pu déterminer qu'un do du milieu était joué sans utiliser de transformée de Fourier, mais qu'en est-il si plusieurs notes sont jouées en même temps? La forme d'onde se complique ensuite lorsque nous la représentons dans le temps :

Mais le spectre de fréquences identifie clairement trois pics :

Il s'agissait d'un accord de do majeur, jouant les notes do, mi et sol.

Ce type d'analyse de Fourier peut nous aider à extraire les composantes de fréquence de n'importe quel type de signal compliqué.

Transformée de Fourier discrète

La transformée de Fourier est utile pour un grand nombre d'applications de traitement des signaux. Mais dans la plupart de ces applications réelles (y compris l'exemple de la musique que nous avons utilisé ci-dessus), nous voulons transformer un ensemble discret de points de données $N$ - et non une fonction continue. Dans ce cas, nous utilisons la transformée de Fourier discrète. La transformée de Fourier discrète (DFT) agit sur un vecteur $(x_0, ..., x_{N-1})$ et le fait correspondre au vecteur $(y_0, ..., y_{N-1})$ selon la formule suivante :

$y_k = \frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}x_j\omega_N^{jk}$

où nous prenons $\omega_N^{jk} = e^{2\pi i \frac{jk}{N}}$. (Notez qu'il existe d'autres conventions qui utilisent le signe moins dans l'exponentielle, alors soyez prudent lorsque vous voyez la TFD dans la nature) Rappelons que $e^{2\pi i \frac{jk}{N}}$ est une fonction périodique, de période $\frac{N}{k}$. Ainsi, en multipliant par cette fonction, la transformée de Fourier est essentiellement un moyen de décomposer la fonction (discrète) $\{x_{j}\}$ en une combinaison linéaire des fonctions périodiques qui la composent, chacune ayant une période $\frac{N}{k}$.

La transformée de Fourier quantique

Nous avons vu comment la transformée de Fourier est utilisée pour représenter une fonction comme une combinaison linéaire d'un nouvel ensemble de "fonctions de base" Les transformations de base sont également effectuées régulièrement sur les états des qubits. Par exemple, l'état d'un qubit unique $|\psi\rangle$ peut être exprimé dans la base de calcul $|\psi\rangle = c_0 |0\rangle + c_1 |1\rangle$, avec les états de base $|0\rangle$ et $|1\rangle$, ou dans la base $X$ $|\psi\rangle = c_+ |+\rangle + c_- |-\rangle$ avec les états de base $|+\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |1\rangle)$ et $|-\rangle = \frac{1}{\sqrt{2}} (|0\rangle - |1\rangle)$. Les deux sont également valables, mais l'une peut être plus naturelle que l'autre, en fonction du type de problème que vous essayez de résoudre.

Les états de Qubit peuvent également être exprimés dans la base de Fourier, où un état est exprimé en termes de combinaison linéaire des états de la base de Fourier $|\phi_y\rangle$, plutôt que des états de la base de calcul habituelle, $|x\rangle$. Pour ce faire, vous devez appliquer une transformée de Fourier quantique (QFT) :

$| \phi_y \rangle = \frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}\omega_N^{y x} \vert x \rangle$

avec $\omega_N^{yx} = e^{\frac{2\pi i y x}{N}}$ comme ci-dessus, et $N$ est le nombre d'états de base dans votre système quantique. Notez que, puisque nous travaillons désormais avec des qubits, $m$ qubits vous donne $2^m$ états de base, donc $N=2^m$. Ici, les états de base sont écrits sous la forme d'un seul nombre $|x\rangle$ où $x$ varie de $0$ à $N-1$, mais vous verrez plus souvent les états de base exprimés sous la forme $|00...00\rangle$, $|00...01\rangle$, $|00...11\rangle$,..., $|11...11\rangle$, où chaque chiffre binaire représente l'état du qubit 0 à $m-1$, de droite à gauche. Il existe un moyen simple de convertir ces états binaires en un seul nombre : il suffit de les traiter comme des nombres binaires! Ainsi, $|00...00\rangle = |0\rangle$, $|00...01\rangle = |1\rangle$, $|00...10\rangle = |2\rangle$, $|00...11\rangle = |3\rangle$, et ainsi de suite, jusqu'à $|11...11\rangle = |2^m -1\rangle = |N-1\rangle$.

Développer l'intuition pour les états de base de Fourier

Nous venons de voir ce que sont les états de la base de calcul et comment ils sont ordonnés : il s'agit de l'ensemble des états où chaque qubit est soit dans $0$ soit dans $1$, et nous les ordonnons de l'état où tous les qubits sont $0$, $|00...00\rangle$, à l'état où ils sont tous $1$, $|11...11\rangle$.

Mais comment donner un sens aux états de la base de Fourier? Tous les états de base de Fourier sont des superpositions égales de tous les états de base de calcul, mais chaque état diffère de l'autre par la périodicité de la phase des composants. Pour comprendre cela plus concrètement, examinons les quatre états de la base de Fourier d'un système à deux qubits. L'état de Fourier le plus bas est celui dont la phase ne varie pas du tout :

$|\phi_0\rangle = \frac{1}{2} (|00\rangle + |01\rangle + |10\rangle + |11\rangle)$

Nous pouvons visualiser cet état en traçant l'amplitude complexe de chacun des termes. La ligne rouge guide l'œil pour montrer comment la phase de cette amplitude s'enroule autour du plan complexe en fonction de l'état de la base de calcul. Pour $|\phi_0\rangle$, la phase reste constante :

L'état de base de Fourier suivant est celui dont les phases des composants passent une seule fois de $0$ à $2\pi$ :

$|\phi_1\rangle = \frac{1}{2} (|00\rangle + e^{i\pi/2}|01\rangle + e^{i\pi}|10\rangle + e^{3i\pi/2}|11\rangle) = \frac{1}{2}(|00\rangle + i|01\rangle - |10\rangle - i|11\rangle)$

Et nous pouvons voir cet enroulement dans le graphique de l'amplitude complexe en fonction de l'état de la base de calcul :

Ainsi, chaque état a une phase qui est $2\pi/4$ radians plus élevée que l'état qui le précède lorsqu'ils sont ordonnés de manière standard, puisque dans cet exemple nous avons quatre états de base ( $N=4$ ). L'état de base suivant s'enroule de 0 à 2 $\pi$ deux fois :

$|\phi_2\rangle = \frac{1}{2} (|00\rangle + e^{i\pi}|01\rangle + e^{2i\pi}|10\rangle + e^{3i\pi}|11\rangle) = \frac{1}{2} (|00\rangle - |01\rangle + |10\rangle - |11\rangle)$

Enfin, la composante de Fourier la plus élevée est celle dont la phase varie le plus rapidement. Pour notre exemple avec deux qubits, c'est celui dont les phases s'enroulent de 0 à $2\pi$ trois fois :

$|\phi_3\rangle = \frac{1}{2} (|00\rangle + e^{3i\pi/2}|01\rangle + e^{6i\pi/2}|10\rangle + e^{9i\pi/2}|11\rangle) = \frac{1}{2} (|00\rangle - i|01\rangle - |10\rangle + i|11\rangle)$

En général, pour un état d' $m$ qubits, il y aura $2^m$ états de base de Fourier, dont la fréquence de variation de phase varie d'une valeur constante, pour $|\phi_0\rangle$, à une variation rapide pour $|\phi_{2^m-1}\rangle$, effectuant $2^m-1$ enroulements autour de $2\pi$ sur la superposition des états. Ainsi, lorsque nous prenons une QFT d'un état quantique, nous effectuons essentiellement la même analyse de base que celle que nous avons effectuée pour la forme d'onde musicale dans l'introduction. Nous déterminons les composantes de fréquence de Fourier qui contribuent à créer l'état quantique qui nous intéresse.

Essayez quelques exemples de QFT

Essayons de continuer à construire notre intuition de la transformée de Fourier quantique en créant un état dans la base de calcul, puis en voyant ce qui se passe lorsque nous lui appliquons la QFT. Pour l'instant, nous traiterons la QFT comme une boîte noire que nous appliquerons en utilisant le site QFTGate de la bibliothèque de circuits Qiskit Plus tard, nous jetterons un coup d'œil sous le capot pour voir comment il est mis en œuvre.

Nous commençons par charger les paquets nécessaires et par sélectionner un appareil sur lequel nous ferons fonctionner notre circuit :

import numpy as np
from qiskit import QuantumCircuit
from qiskit.visualization import plot_histogram
from qiskit.circuit.library import QFTGate

# Load IBM Quantum Compute Service
from qiskit_ibm_runtime import QiskitRuntimeService

# Load the Runtime primitive and session
from qiskit_ibm_runtime import SamplerV2 as Sampler

service = QiskitRuntimeService()

# Use the least busy backend
# backend = service.least_busy(operational=True, simulator=False, min_num_qubits = 127)
backend = service.backend("ibm_pinguino2")

print(backend.name)

Output:

ibm_pinguino2

Si vous n'avez pas de temps disponible sur votre compte ou si vous souhaitez utiliser un simulateur pour une raison quelconque, vous pouvez exécuter la cellule ci-dessous pour configurer un simulateur qui imitera le dispositif quantique que nous avons sélectionné ci-dessus :

# Load the backend sampler
from qiskit.primitives import BackendSamplerV2

# Load the Aer simulator and generate a noise model based on the currently-selected backend.
from qiskit_aer import AerSimulator
from qiskit_aer.noise import NoiseModel

noise_model = NoiseModel.from_backend(backend)

# Define a simulator using Aer, and use it in Sampler.
backend_sim = AerSimulator(noise_model=noise_model)
sampler_sim = BackendSamplerV2(backend=backend_sim)

# Alternatively, load a fake backend with generic properties and define a simulator.
from qiskit.providers.fake_provider import GenericBackendV2

backend_gen = GenericBackendV2(num_qubits=18)
sampler_gen = BackendSamplerV2(backend=backend_gen)

État de base computationnel unique

Tout d'abord, essayons de transformer un seul état de base de calcul. Nous commencerons par créer un état de calcul aléatoire :

# Step 1: Map

qubits = 4
N = 2**qubits


qc = QuantumCircuit(qubits)

# flip state of random qubits to put in a random single computational basis state
for i in range(1, qubits):
    if np.random.randint(0, 2):
        qc.x(i)


# make a copy of the above circuit. (to be used when we apply the QFT in next part)
qc_qft = qc.copy()


qc.measure_all()
qc.draw("mpl")

Output:

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

qc_isa = pm.run(qc)

# Step 3: Run the job on a real quantum computer OR try fake backend

sampler = Sampler(mode=backend)
pubs = [qc_isa]

# Run the job on real quantum device

job = sampler.run(pubs, shots=1000)
res = job.result()
counts = res[0].data.meas.get_counts()

# OR Run the job on the Aer simulator with noise model from real backend

# job = sampler_sim.run([qc_isa])
# res = job.result()
# counts = res[0].data.meas.get_counts()

# Step 4: Post-Process
plot_histogram(counts)

Output:

Transformons maintenant cet état en transformée de Fourier avec QFTGate:

# Step 1: Map

qc_qft.compose(QFTGate(qubits), inplace=True)
qc_qft.measure_all()
qc_qft.draw("mpl")

Output:

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

qc_isa = pm.run(qc_qft)

# Step 3: Run the job on a real quantum computer - try fake backend

sampler = Sampler(mode=backend)
pubs = [qc_isa]

# Run the job on real quantum device

job = sampler.run(pubs, shots=1000)
res = job.result()
counts = res[0].data.meas.get_counts()

# OR Run the job on the Aer simulator with noise model from real backend

# job = sampler_sim.run([qc_isa])
# res = job.result()
# counts = res[0].data.meas.get_counts()

# Step 4: Post-Process
plot_histogram(counts)

Output:

Comme vous pouvez le constater, nous mesurons que les populations de chaque État sont plus ou moins égales, à quelques bruits expérimentaux et statistiques près. Ainsi, si vous prenez la QFT d'un seul état de base de calcul, le résultat est une superposition égale de tous les états. Si vous êtes familier avec les transformées de Fourier, cela ne vous surprendra probablement pas. Un principe de base qui peut nous aider à établir un lien intuitif entre une fonction et sa transformée de Fourier est que la largeur d'une fonction est inversement proportionnelle à la largeur de sa transformée de Fourier. Ainsi, quelque chose qui est très localisé dans le temps, par exemple une impulsion très courte, nécessitera une large gamme de fréquences pour générer cette impulsion. Ce signal sera très large dans l'espace de Fourier.

Ce fait est en fait lié à l'incertitude quantique! Le principe d'incertitude d'Heisenberg est généralement énoncé comme suit : $\Delta x \Delta p \ge \hbar / 2$. Ainsi, si l'incertitude sur $x$ ( $\Delta x$ ) est petite, l'incertitude sur la quantité de mouvement ( $\Delta p$ ) doit être grande, et vice versa. Il s'avère que la transformation de la base de position $x$ à la base de quantité de mouvement $p$ s'effectue au moyen d'une transformée de Fourier.

Note : N'oubliez pas que nous mesurons les populations dans chacun des états de base, ce qui nous fait perdre des informations sur les phases relatives entre les différentes parties de la superposition. Ainsi, bien que la QFT d'un état de base de calcul unique produise la même répartition uniforme de la population sur tous les états de base, les phases ne seront pas nécessairement les mêmes.

Deux états de base computationnels

Voyons maintenant ce qui se passe lorsque nous préparons une superposition d'états de base de calcul. A quoi ressemble la transformée de Fourier dans ce cas?

Choisissons la superposition :

$|\psi\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |N/2\rangle) = \frac{1}{\sqrt{2}} (|000...0\rangle + |100...0\rangle)$

# Step 1: Map
qubits = 4
N = 2**qubits


qc = QuantumCircuit(qubits)

# To make this state, we just need to apply a Hadamard to the last qubit

qc.h(qubits - 1)


qc_qft = qc.copy()


qc.measure_all()

qc.draw("mpl")

Output:

# First, let's go through steps 2-4 for the first circuit, qc

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

qc_isa = pm.run(qc)

# Step 3: Run the job on a real quantum computer - try fake backend

sampler = Sampler(mode=backend)
pubs = [qc_isa]

# Run the job on real quantum device

job = sampler.run(pubs, shots=1000)
res = job.result()
counts = res[0].data.meas.get_counts()

# OR run the job on the Aer simulator with noise model from real backend

# job = sampler_sim.run([qc_isa])
# res = job.result()
# counts = res[0].data.meas.get_counts()

# Step 4: Post-process
plot_histogram(counts)

Output:

Transformons maintenant cet état en transformée de Fourier avec QFTGate:

# Step 1: Map

qc_qft.compose(QFTGate(qubits), inplace=True)
qc_qft.measure_all()
qc_qft.draw("mpl")

Output:

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

qc_isa = pm.run(qc_qft)

# Step 3: Run the job on a real quantum computer OR try fake backend

sampler = Sampler(mode=backend)
pubs = [qc_isa]

# Run the job on real quantum device

job = sampler.run(pubs, shots=1000)
res = job.result()
counts = res[0].data.meas.get_counts()

# OR run the job on the Aer simulator with noise model from real backend

# job = sampler_sim.run([qc_isa])
# res = job.result()
# counts = res[0].data.meas.get_counts()

# Step 4: Post-process
plot_histogram(counts)

Output:

Celle-ci pourrait être un peu plus surprenante. Il semble que la QFT de l'état $|\psi\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |N/2\rangle)$ soit une superposition de tous les états de base pairs. Mais si nous repensons à notre visualisation de chaque état de base $|\phi_y\rangle$, et à la manière dont la phase de chaque composant s'enroule autour de $2\pi$ $y$ fois, la raison pour laquelle nous obtenons ce résultat peut devenir claire.

Vérifiez votre compréhension

En vous appuyant sur l'indice ci-dessus, expliquez pourquoi le résultat obtenu pour la théorie quantique de champ d' $|\psi\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |N/2\rangle)$ e est conforme aux attentes.

• Réponse

  L'état original a une phase relative de 0 (ou un multiple entier de $2\pi$ ) entre les deux parties de la superposition. Nous savons donc que cet état possède des composantes de Fourier dont les phases correspondent également de cette manière : celles qui ont un déphasage nul entre le terme |0000> et le terme |1000>. Chaque état de la base de Fourier $|\phi_y\rangle$ est composé de termes dont la phase s'accumule à un taux de $2\pi y/N$, ce qui signifie que, lorsqu'il est ordonné de la manière habituelle, chaque terme de la superposition a une phase de $2\pi y/N$ supérieure à celle du terme qui le précède. Ainsi, au point médian $N/2$, nous voulons que la phase $2\pi y/N * N/2$ soit un multiple entier de $2\pi$, ce qui se produit lorsque $y$ est pair.

Quelle superposition d'états computationnelle correspondrait à une théorie quantique des champs présentant des pics pour chaque nombre binaire impair?

• Réponse

  Si vous preniez la QFT de l'état $\psi = |0\rangle - |N/2\rangle$, vous verriez des pics sur tous les états binaires impairs.

Décomposer l'algorithme QFT

Maintenant que nous avons mieux compris la relation entre les états des qubits dans la base de calcul et la base de Fourier, examinons l'algorithme QFT lui-même. En d'autres termes, quelles portes mettons-nous en œuvre sur l'ordinateur quantique pour réaliser cette transformation?

Commençons par un qubit unique. Cela signifie que nous aurons deux états de base. QFT $_2$ transforme les états de base de calcul $|0\rangle$ et $|1\rangle$ en états de base de Fourier $\phi_0$ et $\phi_1$ :

$|\phi_0\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$

$|\phi_1\rangle = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$

Vérifiez votre compréhension

Utilisez l'équation de la théorie quantique des champs présentée dans la section précédente pour vérifier ces deux états de base de Fourier ci-dessus.

• Réponse

  La formule générale de la QFT est la suivante :

  $| \phi_y \rangle = \frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}\omega_N^{y x} \vert x \rangle$

  Pour un qubit unique ( $n=1$ ), $N=2^n=2$, et $\omega_N^{xy} = e^{2\pi i \frac {y x}{2}}$. Nous avons donc

  $| \phi_0 \rangle = \frac{1}{\sqrt{2}}(e^{2\pi i \frac {0 \times 0}{2}}|0\rangle + e^{2\pi i \frac {0 \times 1}{2}}|1\rangle) = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$

  $| \phi_1 \rangle = \frac{1}{\sqrt{2}}(e^{2\pi i \frac {1 \times 0}{2}}|0\rangle + e^{2\pi i \frac {1 \times 1}{2}}|1\rangle) = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$

Examinez ces deux équations. Vous connaissez peut-être déjà une porte quantique qui peut être utilisée pour mettre en œuvre cette transformation. En d'autres termes, il existe une porte qui transforme les états de base de calcul $|0\rangle$ et $|1\rangle$ en états de base de Fourier $|\phi_0\rangle$ et $|\phi_1\rangle$. C'est une porte de Hadamard! Cela devient encore plus clair si nous introduisons une représentation matricielle de l'opération QFT $_N$ :

$\text{QFT}_N = \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} \sum_{y=0}^{N-1} \omega_N^{xy} \vert x \rangle \langle y \vert$

Si vous n'êtes pas familier avec cette notation pour exprimer un opérateur quantique, ce n'est pas grave! Il s'agit d'une manière de représenter une matrice $N \times N$, où $x$ et $y$ indexent les colonnes et les lignes de la matrice, de $0$ à $N-1$, et $\omega_N^{xy}$ est la valeur de cette entrée particulière. Ainsi, l'entrée dans la 0e colonne et la 2e ligne, par exemple, serait simplement $\omega_N^{0,2} = e^{2 \pi i \frac{0 \times 2}{N}} = 1$.

Dans cette représentation, chaque état de la base de calcul est associé à l'un des vecteurs de base :

Si vous souhaitez en savoir plus sur cette représentation, consultez la leçon de John Watrous sur les systèmes multiples dans le cours sur les bases de l'information quantique.

Essayons de construire la matrice pour la QFT $_4$. En utilisant la formule ci-dessus, nous trouvons que

$\text{QFT}_4 = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \\ \end{pmatrix}$

Pour mettre en œuvre cette matrice sur un ordinateur quantique, nous devrons déterminer quelle combinaison de portes appliquées à quels qubits nous donnera une transformation unitaire correspondant à la matrice ci-dessus. Nous connaissons déjà l'une des portes qui seront nécessaires : la porte Hadamard. Une autre porte dont nous aurons besoin est la porte à phase contrôlée, qui applique une phase relative $\alpha$ à l'état du qubit cible, tant que le qubit de contrôle est dans l'état $|1\rangle$. Sous forme de matrice, cela se présente comme suit :

$\text{CP}_\alpha = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & e^{i\alpha} \\ \end{pmatrix}$

Étant donné que seul l'état $|11\rangle$ est modifié, le qubit considéré comme le "contrôle" et celui considéré comme la "cible" n'ont pas d'importance Le résultat sera le même dans les deux cas.

Enfin, nous aurons également besoin de portes SWAP. Une porte SWAP permute les états de deux qubits. On dirait que.. :

$\text{SWAP}_\alpha = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ \end{pmatrix}$

La procédure de construction d'un circuit QFT $_{2^m}$ sur les qubits $m$ est itérative - vous appliquez d'abord la QFT $_{2^{m-1}}$ aux qubits $1$ à $m-1$, puis vous ajoutez des portes entre le qubit $0$ et les autres qubits $m-1$. Mais pour appliquer la QFT $_{2^{m-1}}$, il faut d'abord appliquer la QFT $_{2^{m-2}}$ aux qubits 2 à $m-1$, puis ajouter des portes entre le qubit 1 et les qubits restants $2$ à $m-1$. C'est comme une poupée russe gigogne : chaque poupée ajoute un facteur de deux à la dimension du circuit QFT, la plus petite poupée au centre étant QFT $_2$, ou la porte de Hadamard.

Pour mettre une poupée à l'intérieur de la poupée de taille immédiatement supérieure, augmentant ainsi la dimension de la QFT d'un facteur de deux, vous suivez toujours la même procédure :

1. Commencez par appliquer la QFT $_{2^{m-1}}$ aux qubits $m-1$ les plus bas. Il s'agit de la "petite poupée" du jeu de poupées russes gigognes que vous placerez bientôt à l'intérieur de la plus grande poupée suivante.
2. Utilisez le qubit suivant comme contrôle et appliquez des portes de phase contrôlées à chacun des qubits inférieurs ( $m-1$ ), avec des phases aux états de base standard de chacun des qubits restants ( $m-1$ ).
3. Effectuez un Hadamard sur le même qubit supérieur qui a été utilisé comme contrôle dans les portes de phase.
4. Utilisez les portes SWAP pour permuter l'ordre des qubits de sorte que le bit le moins significatif (en haut) devienne le bit le plus significatif (en bas), et que tous les autres soient décalés d'une unité vers le haut.

Nous avons déjà utilisé la fonction QFTGate de la bibliothèque de circuits Qiskit, mais jetons maintenant un coup d'œil à l'intérieur de certaines de ces portes QFT pour vérifier la procédure ci-dessus. Nous pouvons le faire avec decompose().

qc = QuantumCircuit(1)
qc.compose(QFTGate(1), inplace=True)
qc.decompose().draw("mpl")

Output:

qc = QuantumCircuit(2)
qc.compose(QFTGate(2), inplace=True)
qc.decompose().draw("mpl")

Output:

qc = QuantumCircuit(3)
qc.compose(QFTGate(3), inplace=True)
qc.decompose().draw("mpl")

Output:

qc = QuantumCircuit(4)
qc.compose(QFTGate(4), inplace=True)
qc.decompose().draw("mpl")

Output:

J'espère qu'à partir des quatre premières QFT, vous pourrez commencer à voir comment chacune d'entre elles est imbriquée dans la plus grande suivante. Vous avez peut-être remarqué, cependant, que certaines des portes de phase ne sont pas exactement comme prescrites dans la procédure que nous avons décrite ci-dessus, et que les SWAP n'apparaissent pas après chaque sous-programme, mais plutôt à la toute fin de la QFT complète. Cela nous évite d'utiliser des portes inutiles, qui rendraient le circuit plus long et plus sujet aux erreurs. Au lieu d'implémenter le SWAP après chaque poupée imbriquée, le circuit garde une trace de l'endroit où chaque état de qubit doit se trouver et ajuste les qubits auxquels il applique les portes de phase en conséquence. Ensuite, une dernière série de SWAPs à la fin remet tout à sa place.

Appliquer la QFT : estimation de phase

Voyons comment la QFT peut être utilisée pour résoudre un problème utile en informatique quantique. Le calcul de la transformée de Fourier quantique inverse est une étape nécessaire dans un algorithme connu sous le nom d'estimation de phase quantique (QPE), qui est lui-même une sous-routine dans de nombreux autres algorithmes, y compris le "joyau de la couronne" des algorithmes quantiques, l'algorithme de factorisation de Shor.

L'objectif du QPE est d'estimer les valeurs propres d'un opérateur unitaire. Les opérateurs unitaires sont omniprésents dans l'informatique quantique et, souvent, la recherche des valeurs propres de leurs vecteurs propres associés est une étape nécessaire dans un algorithme plus large. Selon le problème, une valeur propre peut représenter l'énergie d'un hamiltonien dans un problème de type simulation, nous aider à trouver les facteurs premiers d'un nombre dans l'algorithme de Shor ou contenir d'autres informations essentielles. QPE est l'un des sous-programmes les plus importants et les plus largement utilisés en informatique quantique.

Quel est donc le rapport avec la transformée de Fourier quantique? Comme vous vous en souvenez peut-être, toute valeur propre $\lambda$ d'un opérateur unitaire a une magnitude $|\lambda| = 1$. Nous pouvons donc écrire chaque valeur propre comme un nombre complexe de magnitude un :

$\lambda = e^{2\pi i \theta}$

où $\theta$ est un nombre réel compris entre 0 et 1. Si vous souhaitez plus d'informations sur les matrices unitaires, consultez la leçon de John Watrous sur le sujet dans Principes de base de l'information quantique.

Notez que $\lambda$ est périodique dans $\theta$. Cela pourrait déjà vous suggérer qu'une QFT pourrait être impliquée, puisque nous avons vu à quel point les QFT sont utiles pour analyser les fonctions périodiques. Ci-dessous, nous allons parcourir l'algorithme et voir précisément comment la QFT entre en jeu.

Comment fonctionne QPE?

Nous commencerons par l'algorithme QPE le plus simple, qui estime grossièrement la phase avec une précision d'un seul chiffre binaire. En d'autres termes, cet algorithme peut faire la distinction entre $\theta = 0$ et $\theta = 1/2$, mais ne peut pas faire mieux. Voici le schéma du circuit :

Les qubits sont préparés dans l'état $|\pi_0\rangle = |\psi\rangle|0\rangle$, où le qubit $0$ est dans l'état $|0\rangle$ et les qubits restants sont dans l'état $|\psi\rangle$, qui est un état propre de $U$. Après le premier Hadamard, l'état du qubit devient :

$|\pi_1\rangle = \frac{1}{\sqrt{2}}|\psi\rangle (|0\rangle + |1\rangle)$

La porte suivante est une porte "contrôlée - $U$ ". Ceci applique l'opération unitaire $U$ aux qubits inférieurs qui sont dans l'état $|\psi\rangle$ si le qubit 0 est dans l'état $|1\rangle$, mais ne fait rien à $|\psi\rangle$ si le qubit 0 est dans l'état $|0\rangle$. Cela transforme les qubits en état :

$|\pi_2\rangle = \frac{1}{\sqrt{2}}( |\psi\rangle|0\rangle + e^{2\pi i \theta}|\psi\rangle|1\rangle)$ $= \frac{1}{\sqrt{2}}|\psi\rangle (|0\rangle + e^{2\pi i \theta}|1\rangle)$

Il vient de se passer quelque chose d'étrange : la porte contrôlée $U$ n'utilise que le qubit $0$ comme qubit de contrôle, de sorte que l'on pourrait penser que cette porte ne modifierait pas du tout l'état du qubit 0. Mais d'une manière ou d'une autre, c'est le cas! Même si l'opération a été appliquée aux qubits inférieurs, l'effet global de la porte est de changer la phase du qubit $0$. Ce mécanisme est connu sous le nom de "phase kickback" et est utilisé dans de nombreux algorithmes quantiques, y compris les algorithmes de Deutsch-Josza et de Grover. Si vous souhaitez en savoir plus sur le mécanisme de rétroaction en phase, consultez la leçon de John Watrous sur les algorithmes de requête quantique dans Fundamentals of quantum algorithms (principes de base des algorithmes quantiques).

Après le rebond de phase, nous appliquons une nouvelle fois la méthode de Hadamard au qubit $0$, ce qui donne l'état suivant :

$|\pi_3\rangle = |\psi\rangle ( \frac{1+e^{2\pi i \theta}}{2} |0\rangle + \frac{1 - e^{2\pi i \theta}}{2}|1\rangle) = |\psi\rangle ( \cos(\pi\theta) |0\rangle - i \sin(\pi\theta)|1\rangle)$

Ainsi, lorsque nous mesurons le qubit $0$ à la fin, nous mesurons $|0\rangle$ avec une certitude de 100 % si $\theta = 0$ et nous mesurons $|1\rangle$ avec une certitude de 100 % si $\theta = \frac{1}{2}$ (et si notre ordinateur quantique est parfait, sans bruit). Si $\theta$ est autre chose que cela, la mesure finale n'est que probabiliste et ne nous apprend que peu de choses.

QPE avec plus de précision : plus de qubits

Nous pouvons étendre ce concept simple à un algorithme plus compliqué avec une précision arbitraire. Si, au lieu d'utiliser uniquement le qubit $0$ pour mesurer la phase, nous utilisons les qubits $m$ $0$ à $m-1$, nous pourrons estimer la phase avec une précision de $m$ bits. Voyons comment cela fonctionne :

Ce circuit QPE plus précis commence de la même manière que la version à un seul bit : Des hadamards sont appliqués aux premiers qubits $m$, et les qubits restants sont préparés dans l'état $|\psi\rangle$, créant ainsi l'état :

$|\pi_1\rangle = \frac{1}{2^{m/2}}|\psi\rangle(|0\rangle+|1\rangle)(|0\rangle+|1\rangle)...(|0\rangle+|1\rangle)$

Les unités contrôlées sont maintenant appliquées. Qubit $0$ est le contrôle pour la même unité $U$ que précédemment. Mais maintenant, le qubit $1$ est le contrôle de l'unité $U^2$, qui est simplement $U$ appliqué deux fois. Ainsi, la valeur propre de $U^2$ est $e^{2*2\pi i \theta}$. En général, chaque qubit $k$ de 0 à $m-1$ sera le contrôle de l'unité $U^{2^k}$. Cela signifie que chacun de ces qubits subira un retour de phase de $e^{2^k*2\pi i \theta}$. Il en résulte l'état suivant :

$|\pi_2\rangle = |\psi\rangle \otimes \frac{1}{2^{m/2}} (|0\rangle+e^{2^{m-1}2\pi i \theta}|1\rangle)(|0\rangle+e^{2^{m-2}2\pi i \theta}|1\rangle)...(|0\rangle+e^{2\pi i \theta}|1\rangle)$

Ceci peut être réécrit comme une somme sur les états de la base de calcul :

$|\pi_2\rangle = |\psi\rangle \otimes \frac{1}{2^{m/2}} \sum_{k=0}^{2^{m}-1} e^{2\pi i k \theta} |k\rangle$

La somme vous semble-t-elle familière? C'est un QFT! Rappelons l'équation de la transformée de Fourier quantique :

$\text{QFT}_{2^m}| y \rangle = \frac{1}{\sqrt{2^m}}\sum_{x=0}^{2^m-1}\omega_{2^m}^{y x} \vert x \rangle$

Ainsi, si la phase $\theta = y/2^m$ pour un certain entier $y$ entre $0$ et $2^m-1$, alors la QFT inverse de cet état donnera l'état :

$|\pi_3\rangle = |\psi\rangle \otimes |y\rangle$

et de $|y\rangle$, nous pouvons déduire $\theta$.

Cependant, si $\theta/2^m$ n'est pas un multiple entier, la méthode de la TQC inverse n'approximera que $\theta$. Son approximation $\theta$ sera probabiliste, ce qui signifie que nous n'obtiendrons pas toujours la meilleure approximation, mais qu'elle en sera assez proche. Plus vous utiliserez de qubits $m$, meilleure sera l'approximation. Pour savoir comment quantifier cette approximation de $\theta$, consultez la leçon de John Watrous sur l' estimation de phase et la factorisation dans Fundamentals of quantum algorithms.

Conclusion

Ce module a donné un aperçu de ce qu'est une QFT, de la manière dont elle est mise en œuvre sur un ordinateur quantique et de son utilité pour résoudre des problèmes. Nous vous avons donné un aperçu de son utilité lorsque nous avons vu comment il peut être utilisé dans l'estimation de phase quantique pour connaître les valeurs propres d'une matrice unitaire.

Concepts essentiels

• La transformée de Fourier quantique est l'analogue quantique de la transformée de Fourier discrète.
• La QFT est un exemple de transformation de base.
• La procédure d'estimation de la phase quantique repose sur le mécanisme de rétroaction de phase des opérations unitaires contrôlées, ainsi que sur une QFT inverse.
• QFT et QPE sont tous deux des sous-programmes largement utilisés dans de nombreux algorithmes quantiques.

Questions

True/False

1. T/F La transformée de Fourier quantique est l'analogue quantique de la transformée de Fourier discrète (DFT) classique.
2. La T/F QFT peut être mise en œuvre en utilisant uniquement des portes Hadamard et CNOT.
3. T/F La QFT est un élément clé de l'algorithme de Shor.
4. T/F La sortie de l'estimation quantique de phase est un état quantique représentant le vecteur propre de l'opérateur.
5. T/F QPE nécessite l'utilisation de la transformée de Fourier quantique inverse (QFT $^\dag$ ).
6. T/F En QPE, si la phase $\phi$ est exactement représentable avec $n$ bits, l'algorithme donne un résultat correct avec une probabilité de 1.

Réponses courtes

1. Combien de qubits sont nécessaires pour réaliser une QFT sur un système avec $2^n$ points de données?
2. La QFT peut-elle être utilisée sur un état qui n'est pas un état de base de calcul? Dans l'affirmative, que se passe-t-il?
3. Comment le nombre de qubits de contrôle utilisés dans le QPE affecte-t-il la résolution de l'estimation de la phase résultante?

Incidents

1. Utilisez la multiplication matricielle pour vérifier que les étapes de l'algorithme QFT aboutissent bien à la matrice $\text{QFT}_4$ :

(Il n'est pas nécessaire de le faire à la main!)

Problèmes difficiles

1. Créez un état à quatre qubits qui est une superposition égale de toutes les bases de calcul impaires : $|\psi\rangle = |0001\rangle + |0011\rangle + |0101\rangle + |0111\rangle +|1001\rangle +|1011\rangle +|1101\rangle +|1111\rangle$. Effectuez ensuite une QFT sur cet état. Quel est l'état qui en résulte? Expliquez pourquoi votre résultat est logique, en utilisant vos connaissances sur les transformées de Fourier.