Algorithmes quantiques : Estimation de phase

remarque

Kento Ueda (15 mai 2024)

Ce notebook présente les concepts fondamentaux et l'implémentation de la Transformation de Fourier Quantique (QFT) et de l'Estimation de Phase Quantique (QPE).

Télécharger le PDF du cours original. Note que certains extraits de code peuvent être obsolètes car il s'agit d'images statiques.

Le temps QPU approximatif pour exécuter cette expérience est de 7 secondes.

1. Introduction

Transformation de Fourier Quantique (QFT)

La transformée de Fourier quantique est l'équivalent quantique de la transformée de Fourier discrète classique. C'est une transformation linéaire appliquée aux états quantiques, qui fait correspondre les bases computationnelles à leurs représentations dans la base de Fourier. La QFT joue un rôle clé dans de nombreux algorithmes quantiques, offrant une méthode efficace pour extraire les informations de périodicité des états quantiques. La QFT peut être implémentée avec $O(N^2)$ opérations à l'aide de portes quantiques telles que les portes Hadamard et les portes à phase contrôlée pour $N$ qubits, permettant une accélération exponentielle par rapport à la transformée de Fourier classique.

• Applications : Elle constitue la base d'algorithmes quantiques tels que l'algorithme de Shor pour la factorisation de grands entiers et le logarithme discret.

Estimation de Phase Quantique (QPE)

L'Estimation de Phase Quantique est un algorithme quantique utilisé pour estimer la phase associée à un vecteur propre d'un opérateur unitaire. Cet algorithme crée un pont entre les propriétés mathématiques abstraites des états quantiques et leurs applications computationnelles.

• Applications : Il permet de résoudre des problèmes tels que la recherche de valeurs propres de matrices unitaires et la simulation de systèmes quantiques.

Ensemble, la QFT et la QPE forment l'épine dorsale de nombreux algorithmes quantiques résolvant des problèmes infaisables pour les ordinateurs classiques. À la fin de ce notebook, tu comprendras comment ces techniques sont implémentées.

2. Bases de la Transformation de Fourier Quantique (QFT)

# Added by doQumentation — installs the packages this notebook needs if they are missing
import importlib.util

_needed = {"numpy": "numpy", "qiskit": "qiskit", "qiskit_aer": "qiskit-aer", "qiskit_ibm_runtime": "qiskit-ibm-runtime"}
_missing = [pip for module, pip in _needed.items()
            if importlib.util.find_spec(module) is None]
# One at a time, so a package that fails to install does not block the others
for _pip in _missing:
    %pip install -q {_pip}
if not _missing:
    print("\u2713 All required packages are installed")

from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit_aer import AerSimulator
from qiskit.visualization import plot_histogram, plot_bloch_multivector
from qiskit.quantum_info import Statevector
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager
from qiskit_ibm_runtime import Sampler

from numpy import pi

Par analogie avec la transformée de Fourier discrète, la QFT agit sur un état quantique $\vert X\rangle = \sum_{j=0}^{N-1} x_j \vert j \rangle$ pour $N$ qubits et le transforme en l'état quantique $\vert Y\rangle = \sum_{k=0}^{N-1} y_k \vert k \rangle$.

$$QFT_{N}: \vert j \rangle \mapsto \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}\omega_N^{jk} \vert k \rangle$$

où $\omega_N^{jk} = e^{2\pi i \frac{jk}{N}}$.

Ou la représentation matricielle unitaire :

$$U_{QFT} = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} \sum_{k=0}^{N-1} \omega_N^{jk} \vert k \rangle \langle j \vert$$

2.1. Intuition

La transformée de Fourier quantique (QFT) opère une transformation entre deux bases : la base computationnelle (Z) et la base de Fourier. Mais que signifie la base de Fourier dans ce contexte ? Tu te rappelles probablement que la transformée de Fourier $F(\omega)$ d'une fonction $f(x)$ décrit la convolution de $f(x)$ sur une fonction sinusoïdale de fréquence $\omega$. En termes simples : la transformée de Fourier est une fonction qui décrit quelle quantité de chaque fréquence $\omega$ est nécessaire pour construire une fonction $f(x)$ à partir de fonctions sinus (ou cosinus). Pour mieux comprendre ce que signifie la QFT dans ce contexte, observe les images pas à pas ci-dessous qui montrent un nombre encodé en binaire à l'aide de quatre qubits :

Dans la base computationnelle, les nombres sont stockés en binaire en utilisant les états $|0\rangle$ et $|1\rangle$.

Remarque la fréquence à laquelle les différents qubits changent ; le qubit le plus à gauche bascule à chaque incrément du nombre, le suivant tous les 2 incréments, le troisième tous les 4 incréments, et ainsi de suite.

Si l'on applique une transformée de Fourier quantique à ces états, on obtient la correspondance

$$|\text{État dans la base computationnelle}\rangle \quad \xrightarrow[]{\text{QFT}} \quad |\text{État dans la base de Fourier}\rangle$$ $$\text{QFT}|x\rangle = |\widetilde{x}\rangle$$

(On note souvent les états dans la base de Fourier avec un tilde (~)).

Dans la base de Fourier, les nombres sont stockés en utilisant différentes rotations autour de l'axe Z :

IFRAME

Le nombre que l'on souhaite stocker dicte l'angle auquel chaque qubit est tourné autour de l'axe Z. Dans l'état $|\widetilde{0}\rangle$, tous les qubits sont dans l'état $|{+}\rangle$. Comme vu dans l'exemple ci-dessus, pour encoder l'état $|\widetilde{5}\rangle$ sur 4 qubits, le qubit le plus à gauche a été tourné de $\tfrac{5}{2^n} = \tfrac{5}{16}$ tours complets ($\tfrac{5}{16}\times 2\pi$ radians). Le qubit suivant est tourné du double ($\tfrac{10}{16}\times 2\pi$ radians, soit $10/16$ tours complets), cet angle est ensuite doublé pour le qubit suivant, et ainsi de suite.

De nouveau, note la fréquence à laquelle chaque qubit change. Le qubit le plus à gauche (qubit 0) a dans ce cas la fréquence la plus basse, et le plus à droite la plus haute.

2.2 Exemple : QFT à 1 qubit

Considérons le cas $N = 2^1 = 2$.

La matrice unitaire peut s'écrire :

$$\begin{aligned} U_{QFT} & = \frac{1}{\sqrt{2}} \sum_{j=0}^{1} \sum_{k=0}^{1} \omega_2^{jk} \vert k \rangle \langle j \vert \\ & = \frac{1}{\sqrt{2}} (\omega_2^{0} \vert 0 \rangle \langle 0 \vert + \omega_2^{0} \vert 0 \rangle \langle 1 \vert + \omega_2^{0} \vert 1 \rangle \langle 0 \vert + \omega_2^{1} \vert 1 \rangle \langle 1 \vert) \\ & = \frac{1}{\sqrt{2}} (\vert 0 \rangle \langle 0 \vert + \vert 0 \rangle \langle 1 \vert + \vert 1 \rangle \langle 0 \vert - \vert 1 \rangle \langle 1 \vert) \\ & = H \end{aligned}$$

Cette opération est le résultat de l'application de la porte Hadamard ($H$).

2.3 Représentation en produit de la QFT

Généralisons la transformation pour $N = 2^n$, $QFT_{N}$ agissant sur l'état $\vert x \rangle = \vert x_1\ldots x_n \rangle$.

$$\begin{aligned} QFT_N\vert x \rangle & = \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1}\omega_N^{xy} \vert y \rangle \\ & = \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1} e^{2 \pi i xy / 2^n} \vert y \rangle ~\text{puisque}\: \omega_N^{xy} = e^{2\pi i \frac{xy}{N}} \:\text{et}\: N = 2^n \\ & = \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1} e^{2 \pi i \left(\sum_{k=1}^n y_k/2^k\right) x} \vert y_1 \ldots y_n \rangle \:\text{en réécrivant en notation binaire fractionnaire}\: y = y_1\ldots y_n, y/2^n = \sum_{k=1}^n y_k/2^k \\ & = \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1} \prod_{k=1}^n e^{2 \pi i x y_k/2^k } \vert y_1 \ldots y_n \rangle \:\text{après développement de l'exponentielle d'une somme en produit d'exponentielles,} \\ & = \frac{1}{\sqrt{N}} \bigotimes_{k=1}^n \left(\vert0\rangle + e^{2 \pi i x /2^k } \vert1\rangle \right) \:\text{après réarrangement de la somme et des produits, et développement de} \sum_{y=0}^{N-1} = \sum_{y_1=0}^{1}\sum_{y_2=0}^{1}\ldots\sum_{y_n=0}^{1} \\ & = \frac{1}{\sqrt{N}} \left(\vert0\rangle + e^{\frac{2\pi i}{2}x} \vert1\rangle\right) \otimes \left(\vert0\rangle + e^{\frac{2\pi i}{2^2}x} \vert1\rangle\right) \otimes \ldots \otimes \left(\vert0\rangle + e^{\frac{2\pi i}{2^{n-1}}x} \vert1\rangle\right) \otimes \left(\vert0\rangle + e^{\frac{2\pi i}{2^n}x} \vert1\rangle\right) \end{aligned}$$

2.4 Exemple : Construction du circuit QFT à 3 qubits

D'après la description ci-dessus, la façon de construire un circuit QFT n'est peut-être pas évidente. Pour l'instant, remarque simplement que l'on attend de trois qubits des phases qui évoluent à des « vitesses » différentes. Comprendre exactement comment cela se traduit en circuit est laissé à titre d'exercice au lecteur. Des diagrammes et des exemples multiples se trouvent dans le PDF du cours. Des ressources supplémentaires incluent cette leçon du cours Fondamentaux des algorithmes quantiques.

Nous démontrerons la QFT en utilisant uniquement des simulateurs, et nous n'utiliserons donc pas le framework Qiskit patterns jusqu'à ce que nous passions à l'estimation de phase quantique.

# Prepare for 3 qubits circuit
qr = QuantumRegister(3)
cr = ClassicalRegister(3)
qc = QuantumCircuit(qr, cr)

qc.h(2)
qc.cp(pi / 2, 1, 2)  # Controlled-phase gate from qubit 1 to qubit 2
qc.cp(pi / 4, 0, 2)  # Controlled-phase gate from qubit 0 to qubit 2
qc.draw(output="mpl")

qc.h(1)
qc.cp(pi / 2, 0, 1)  # Controlled-phase gate from qubit 0 to qubit 1

qc.draw(output="mpl")

qc.h(0)

qc.draw(output="mpl")

qc.swap(0, 2)

qc.draw(output="mpl")

Appliquons, à titre d'exemple, la QFT à $|5\rangle$.

Tout d'abord, nous confirmons la notation binaire de l'entier 5 et créons le circuit encodant l'état 5 :

bin(5)

'0b101'

qc = QuantumCircuit(3)

qc.x(0)
qc.x(2)
qc.draw(output="mpl")

Nous vérifions les états quantiques à l'aide du simulateur Aer :

statevector = Statevector(qc)
plot_bloch_multivector(statevector)

Enfin, nous ajoutons la QFT et observons l'état final de nos qubits :

qc.h(2)
qc.cp(pi / 2, 1, 2)
qc.cp(pi / 4, 0, 2)

qc.h(1)
qc.cp(pi / 2, 0, 1)

qc.h(0)

qc.swap(0, 2)

qc.draw(output="mpl")

statevector = Statevector(qc)
plot_bloch_multivector(statevector)

On peut voir que notre fonction QFT a fonctionné correctement. Le qubit 0 a été tourné de $\tfrac{5}{8}$ d'un tour complet, le qubit 1 de $\tfrac{10}{8}$ tours complets (équivalent à $\tfrac{1}{4}$ d'un tour complet), et le qubit 2 de $\tfrac{20}{8}$ tours complets (équivalent à $\tfrac{1}{2}$ d'un tour complet).

2.5 Exercice : QFT

(1) Implémente la QFT à 4 qubits.

##your code goes here##

(2) Applique la QFT à $|14\rangle$, simule et trace le vecteur d'état à l'aide de la sphère de Bloch.

##your code goes here##

Solution de l'exercice : QFT

(1)

qr = QuantumRegister(4)
cr = ClassicalRegister(4)
qc = QuantumCircuit(qr, cr)

qc.h(3)
qc.cp(pi / 2, 2, 3)
qc.cp(pi / 4, 1, 3)
qc.cp(pi / 8, 0, 3)

qc.h(2)
qc.cp(pi / 2, 1, 2)
qc.cp(pi / 4, 0, 2)

qc.h(1)
qc.cp(pi / 2, 0, 1)

qc.h(0)

qc.swap(0, 3)
qc.swap(1, 2)

qc.draw(output="mpl")

(2)

bin(14)

'0b1110'

qc = QuantumCircuit(4)

qc.x(1)
qc.x(2)
qc.x(3)
qc.draw("mpl")

qc.h(3)
qc.cp(pi / 2, 2, 3)
qc.cp(pi / 4, 1, 3)
qc.cp(pi / 8, 0, 3)

qc.h(2)
qc.cp(pi / 2, 1, 2)
qc.cp(pi / 4, 0, 2)

qc.h(1)
qc.cp(pi / 2, 0, 1)
qc.h(0)

qc.swap(0, 3)
qc.swap(1, 2)

qc.draw(output="mpl")

statevector = Statevector(qc)
plot_bloch_multivector(statevector)

3. Bases de l'Estimation de Phase Quantique (QPE)

Étant donné une opération unitaire $U$, la QPE estime $\theta$ dans $U\vert\psi \rangle =e^{\boldsymbol{2\pi i} \theta }|\psi \rangle$ ; puisque $U$ est unitaire, toutes ses valeurs propres ont une norme de 1.

3.1 Procédure

1. Initialisation

$\vert\psi\rangle$ se trouve dans un ensemble de registres de qubits. Un ensemble supplémentaire de $n$ qubits forme le registre de comptage dans lequel nous stockerons la valeur $2^n\theta$ :

$$|\psi_0\rangle = \lvert 0 \rangle^{\otimes n} \lvert \psi \rangle$$

2. Superposition

Applique une porte de Hadamard sur $n$ qubits, $H^{\otimes n}$, au registre de comptage :

$$|\psi_1\rangle = {\frac {1}{2^{\frac {n}{2}}}}\left(|0\rangle +|1\rangle \right)^{\otimes n} \lvert \psi \rangle$$

3. Opérations unitaires contrôlées

Nous devons introduire l'unitaire contrôlé $CU$ qui applique l'opérateur unitaire $U$ sur le registre cible uniquement si son bit de contrôle correspondant est $|1\rangle$. Puisque $U$ est un opérateur unitaire avec vecteur propre $|\psi\rangle$ tel que $U|\psi \rangle =e^{\boldsymbol{2\pi i} \theta }|\psi \rangle$, cela signifie :

$$U^{2^{j}}|\psi \rangle =U^{2^{j}-1}U|\psi \rangle =U^{2^{j}-1}e^{2\pi i\theta }|\psi \rangle =\cdots =e^{2\pi i2^{j}\theta }|\psi \rangle$$

3.2 Exemple : QPE avec la porte T

Utilisons la porte $T$ comme exemple de QPE et estimons sa phase $\theta$.

$$T|1\rangle = \begin{pmatrix} 1 & 0\\ 0 & e^\frac{i\pi}{4}\\ \end{pmatrix} \begin{pmatrix} 0\\ 1\\ \end{pmatrix} = e^\frac{i\pi}{4}|1\rangle$$

On s'attend à trouver :

$$\theta = \frac{1}{8}$$

où

$$T|1\rangle = e^{2i\pi\theta}|1\rangle$$

Nous initialisons $\vert\psi\rangle = \vert1\rangle$ du vecteur propre de la porte $T$ en appliquant une porte $X$ :

qpe = QuantumCircuit(4, 3)
qpe.x(3)
qpe.draw(output="mpl")

Ensuite, nous appliquons des portes Hadamard aux qubits de comptage :

for qubit in range(3):
    qpe.h(qubit)
qpe.draw(output="mpl")

Nous effectuons les opérations unitaires contrôlées :

repetitions = 1
for counting_qubit in range(3):
    for i in range(repetitions):
        qpe.cp(pi / 4, counting_qubit, 3)  # This is C-U
    repetitions *= 2
qpe.draw(output="mpl")

Nous appliquons la transformation de Fourier quantique inverse pour convertir l'état du registre de comptage, puis mesurons le registre de comptage :

from qiskit.circuit.library import QFT

# Apply inverse QFT
qpe.append(QFT(3, inverse=True), [0, 1, 2])
qpe.draw(output="mpl")

for n in range(3):
    qpe.measure(n, n)
qpe.draw(output="mpl")

Nous pouvons simuler en utilisant le simulateur Aer :

aer_sim = AerSimulator()
shots = 2048

pm = generate_preset_pass_manager(backend=aer_sim, optimization_level=1)
t_qpe = pm.run(qpe)

sampler = Sampler(mode=aer_sim)
job = sampler.run([t_qpe], shots=shots)
result = job.result()
answer = result[0].data.c.get_counts()

plot_histogram(answer)

Nous voyons que nous obtenons un résultat (001) avec certitude, ce qui se traduit en décimal par : 1. Nous devons maintenant diviser notre résultat (1) par $2^n$ pour obtenir $\theta$ :

$$\theta = \frac{1}{2^3} = \frac{1}{8}$$

L'algorithme de Shor nous permet de factoriser un nombre en construisant un circuit avec $\theta$ inconnu et en obtenant $\theta$.

3.3 Exercice

Estime $\theta = 1/3$ en utilisant 3 qubits pour le comptage et un qubit pour un vecteur propre.

$P|1\rangle = e^{i\lambda}|1\rangle$. Puisque nous voulons implémenter $U|1\rangle = e^{2\pi i \tfrac{1}{3}}|1\rangle$, nous devons poser $\lambda = \tfrac{2 \pi}{3}$.

##your code goes here##

Solution de l'exercice : $\theta = 1/3$

# Create and set up circuit
qpe = QuantumCircuit(4, 3)

# Apply H-Gates to counting qubits:
for qubit in range(3):
    qpe.h(qubit)

# Prepare our eigenstate |psi>:
qpe.x(3)

# Do the controlled-U operations:
angle = 2 * pi / 3
repetitions = 1
for counting_qubit in range(3):
    for i in range(repetitions):
        qpe.cp(angle, counting_qubit, 3)
    repetitions *= 2

# Do the inverse QFT:
qpe.append(QFT(3, inverse=True), [0, 1, 2])

for n in range(3):
    qpe.measure(n, n)

qpe.draw(output="mpl")

aer_sim = AerSimulator()
shots = 4096

pm = generate_preset_pass_manager(backend=aer_sim, optimization_level=1)
t_qpe = pm.run(qpe)

sampler = Sampler(mode=aer_sim)
job = sampler.run([t_qpe], shots=shots)
result = job.result()
answer = result[0].data.c.get_counts()

plot_histogram(answer)

4. Exécution avec la primitive Sampler IBM Quantum

Nous allons réaliser la QPE en utilisant un vrai dispositif quantique et suivre les 4 étapes des patterns Qiskit.

1. Formuler le problème dans un format natif quantique

2. Optimiser les circuits

3. Exécuter le circuit cible

4. Post-traiter les résultats

from qiskit_ibm_runtime import QiskitRuntimeService
from qiskit_ibm_runtime import Sampler

# Loading your IBM Quantum® account(s)

service = QiskitRuntimeService()

4.1 Étape 1 : Formuler le problème en circuits et opérateurs quantiques

qpe = QuantumCircuit(4, 3)
qpe.x(3)
for qubit in range(3):
    qpe.h(qubit)
repetitions = 1
for counting_qubit in range(3):
    for i in range(repetitions):
        qpe.cp(pi / 4, counting_qubit, 3)  # This is C-U
    repetitions *= 2
qpe.append(QFT(3, inverse=True), [0, 1, 2])
for n in range(3):
    qpe.measure(n, n)
qpe.draw(output="mpl")

backend = service.least_busy(simulator=False, operational=True, min_num_qubits=4)

print(backend)

<IBMBackend('ibm_strasbourg')>

4.2 Étape 2 : Optimiser pour le matériel cible

# Transpile the circuit into basis gates executable on the hardware
pm = generate_preset_pass_manager(backend=backend, optimization_level=2)
qc_compiled = pm.run(qpe)

qc_compiled.draw("mpl", idle_wires=False)

4.3 Étape 3 : Exécuter sur le matériel cible

real_sampler = Sampler(mode=backend)
job = real_sampler.run([qc_compiled], shots=1024)
job_id = job.job_id()
print("job id:", job_id)

job id: d13p4zb5z6q00087ag00

job = service.job(job_id)  # Input your job-id between the quotations
job.status()

'DONE'

result_real = job.result()
print(result_real)

PrimitiveResult([SamplerPubResult(data=DataBin(c=BitArray(<shape=(), num_shots=1024, num_bits=3>)), metadata={'circuit_metadata': {}})], metadata={'execution': {'execution_spans': ExecutionSpans([DoubleSliceSpan(<start='2025-06-09 22:39:00', stop='2025-06-09 22:39:00', size=1024>)])}, 'version': 2})

4.4 Étape 4 : Post-traiter les résultats

from qiskit.visualization import plot_histogram

plot_histogram(result_real[0].data.c.get_counts())

# See the version of Qiskit
import qiskit

qiskit.__version__

'2.0.2'