Algoritmi quantistici: Stima della fase

nota

Kento Ueda (15 maggio 2024)

Questo notebook fornisce i concetti fondamentali e l'implementazione della Trasformata di Fourier Quantistica (QFT) e della Stima della Fase Quantistica (QPE).

Scarica il pdf della lezione originale. Nota che alcuni frammenti di codice potrebbero risultare deprecati poiché si tratta di immagini statiche.

Il tempo QPU approssimativo per eseguire questo esperimento è di 7 secondi.

1. Introduzione

Trasformata di Fourier Quantistica (QFT)

La Trasformata di Fourier Quantistica è l'equivalente quantistico della trasformata di Fourier discreta classica. È una trasformazione lineare applicata agli stati quantistici, che mappa le basi computazionali nelle loro rappresentazioni nella base di Fourier. La QFT svolge un ruolo chiave in molti algoritmi quantistici, offrendo un metodo efficiente per estrarre informazioni di periodicità dagli stati quantistici. La QFT può essere implementata con $O(N^2)$ operazioni tramite gate quantistici come i gate di Hadamard e i gate di fase controllata per $N$ qubit, consentendo un'accelerazione esponenziale rispetto alla trasformata di Fourier classica.

• Applicazioni: È una componente fondamentale in algoritmi quantistici come l'algoritmo di Shor per la fattorizzazione di interi grandi e il logaritmo discreto.

Stima della Fase Quantistica (QPE)

La Stima della Fase Quantistica è un algoritmo quantistico utilizzato per stimare la fase associata a un autovettore di un operatore unitario. Questo algoritmo fornisce un ponte tra le proprietà matematiche astratte degli stati quantistici e le loro applicazioni computazionali.

• Applicazioni: Può risolvere problemi come il calcolo degli autovalori di matrici unitarie e la simulazione di sistemi quantistici.

Insieme, QFT e QPE costituiscono la spina dorsale essenziale di molti algoritmi quantistici che risolvono problemi impossibili per i computer classici. Al termine di questo notebook, avrai acquisito una comprensione di come queste tecniche vengono implementate.

2. Basi della Trasformata di Fourier Quantistica (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

Per analogia con la trasformata di Fourier discreta, la QFT agisce su uno stato quantistico $\vert X\rangle = \sum_{j=0}^{N-1} x_j \vert j \rangle$ per $N$ qubit e lo mappa nello stato quantistico $\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$$

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

Oppure nella rappresentazione matriciale unitaria:

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

La trasformata quantistica di Fourier (QFT) trasforma tra due basi, la base computazionale (Z) e la base di Fourier. Ma cosa significa la base di Fourier in questo contesto? Probabilmente ricorderai che la trasformata di Fourier $F(\omega)$ di una funzione $f(x)$ descrive la convoluzione di $f(x)$ su una funzione sinusoidale con frequenza $\omega$. In parole semplici: la trasformata di Fourier è una funzione che descrive quanto di ogni frequenza $\omega$ avremmo bisogno per costruire una funzione $f(x)$ a partire da funzioni seno (o coseno). Per farti un'idea migliore di cosa significhi la QFT in questo contesto, considera le immagini a gradini sottostanti che mostrano un numero codificato in binario, usando quattro qubit:

Nella base computazionale, memorizziamo i numeri in binario usando gli stati $|0\rangle$ e $|1\rangle$.

Nota la frequenza con cui i diversi qubit cambiano; il qubit più a sinistra si inverte a ogni incremento del numero, il successivo ogni 2 incrementi, il terzo ogni 4 incrementi, e così via.

Se applichiamo una trasformata quantistica di Fourier a questi stati, mappiamo

$$|\text{State in Computational Basis}\rangle \quad \xrightarrow[]{\text{QFT}} \quad |\text{State in Fourier Basis}\rangle$$ $$\text{QFT}|x\rangle = |\widetilde{x}\rangle$$

(Spesso indichiamo gli stati nella base di Fourier usando la tilde (~)).

Nella base di Fourier, memorizziamo i numeri usando diverse rotazioni attorno all'asse Z:

Nella base di Fourier, i numeri vengono memorizzati utilizzando diverse rotazioni attorno all'asse Z:

Il numero che vogliamo memorizzare determina l'angolo di rotazione di ciascun qubit attorno all'asse Z. Nello stato $|\widetilde{0}\rangle$, tutti i qubit sono nello stato $|{+}\rangle$. Come mostrato nell'esempio precedente, per codificare lo stato $|\widetilde{5}\rangle$ su 4 qubit, abbiamo ruotato il qubit più a sinistra di $\tfrac{5}{2^n} = \tfrac{5}{16}$ giri completi ($\tfrac{5}{16}\times 2\pi$ radianti). Il qubit successivo viene ruotato del doppio ($\tfrac{10}{16}\times 2\pi$ radianti, ovvero $10/16$ giri completi), questo angolo viene poi raddoppiato per il qubit successivo, e così via.

Ancora una volta, nota la frequenza con cui cambia ciascun qubit. Il qubit più a sinistra (qubit 0) in questo caso ha la frequenza più bassa, e quello più a destra la più alta.

2.2 Esempio: QFT a 1 qubit

Consideriamo il caso $N = 2^1 = 2$.

La matrice unitaria può essere scritta come:

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

Questa operazione è il risultato dell'applicazione del gate di Hadamard ($H$).

2.3 Rappresentazione a prodotto della QFT

Generalizziamo la trasformazione per $N = 2^n$, $QFT_{N}$ applicata allo stato $\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{since}\: \omega_N^{xy} = e^{2\pi i \frac{xy}{N}} \:\text{e}\: 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{rewriting in fractional binary notation}\: 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{after expanding the exponential of a sum to a product of exponentials,} \\ & = \frac{1}{\sqrt{N}} \bigotimes_{k=1}^n \left(\vert0\rangle + e^{2 \pi i x /2^k } \vert1\rangle \right) \:\text{after rearranging the sum and products, and expanding} \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 Esempio: Costruzione del circuito QFT a 3 qubit

Dalla descrizione precedente, potrebbe non essere immediatamente chiaro come costruire un circuito QFT. Per ora, nota semplicemente che ci aspettiamo che i tre qubit abbiano fasi che evolvono a "velocità" diverse. Capire esattamente come questo si traduca in un circuito è lasciato come esercizio al lettore. Nella dispensa in pdf sono presenti diversi diagrammi ed esempi. Ulteriori risorse includono questa lezione del corso sui Fondamenti degli algoritmi quantistici.

Dimostreremo la QFT usando solo simulatori, quindi non utilizzeremo il framework Qiskit patterns fino a quando non passeremo alla stima della fase quantistica.

# 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")

Proviamo ad applicare la QFT a $|5\rangle$ come esempio.

Per prima cosa, confermiamo la notazione binaria dell'intero 5 e creiamo il circuito che codifica lo stato 5:

bin(5)

'0b101'

qc = QuantumCircuit(3)

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

Verifichiamo gli stati quantistici usando il simulatore Aer:

statevector = Statevector(qc)
plot_bloch_multivector(statevector)

Infine, aggiungiamo la QFT e visualizziamo lo stato finale dei nostri qubit:

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)

Possiamo vedere che la nostra funzione QFT ha funzionato correttamente. Il qubit 0 è stato ruotato di $\tfrac{5}{8}$ di giro completo, il qubit 1 di $\tfrac{10}{8}$ giri completi (equivalente a $\tfrac{1}{4}$ di giro completo), e il qubit 2 di $\tfrac{20}{8}$ giri completi (equivalente a $\tfrac{1}{2}$ di giro completo).

2.5 Esercizio: QFT

(1) Implementa la QFT a 4 qubit.

##your code goes here##

(2) Applica la QFT a $|14\rangle$, simula e traccia il vettore di stato usando la sfera di Bloch.

##your code goes here##

Soluzione dell'esercizio: 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. Basi della Stima della Fase Quantistica (QPE)

Data un'operazione unitaria $U$, la QPE stima $\theta$ in $U\vert\psi \rangle =e^{\boldsymbol{2\pi i} \theta }|\psi \rangle$; poiché $U$ è unitario, tutti i suoi autovalori hanno norma 1.

3.1 Procedura

1. Configurazione

$\vert\psi\rangle$ si trova in un insieme di registri qubit. Un ulteriore insieme di $n$ qubit costituisce il registro di conteggio in cui memorizzeremo il valore $2^n\theta$:

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

2. Sovrapposizione

Applica un'operazione di gate di Hadamard a $n$ bit $H^{\otimes n}$ sul registro di conteggio:

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

3. Operazioni unitarie controllate

Dobbiamo introdurre l'unitario controllato $CU$ che applica l'operatore unitario $U$ al registro target solo se il corrispondente bit di controllo è $|1\rangle$. Poiché $U$ è un operatore unitario con autovettore $|\psi\rangle$ tale che $U|\psi \rangle =e^{\boldsymbol{2\pi i} \theta }|\psi \rangle$, questo implica:

$$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 Esempio: QPE con il gate T

Usiamo il gate $T$ come esempio di QPE e stimiamo la sua fase $\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$$

Ci aspettiamo di trovare:

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

dove

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

Inizializziamo $\vert\psi\rangle = \vert1\rangle$ dell'autovettore del Gate $T$ applicando un Gate $X$:

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

Successivamente, applichiamo i Gate di Hadamard ai qubit di conteggio:

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

Eseguiamo le operazioni unitarie controllate:

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

Applichiamo la trasformata quantistica di Fourier inversa per convertire lo stato del registro di conteggio, poi misuriamo il registro di conteggio:

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

Possiamo simulare usando il simulatore 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)

Vediamo che otteniamo un risultato (001) con certezza, che si traduce nel decimale: 1. Dobbiamo ora dividere il nostro risultato (1) per $2^n$ per ottenere $\theta$:

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

L'algoritmo di Shor ci permette di fattorizzare un numero costruendo un circuito con $\theta$ sconosciuto e ottenendo $\theta$.

3.3 Esercizio

Stima $\theta = 1/3$ usando 3 qubit per il conteggio e un qubit per un autovettore.

$P|1\rangle = e^{i\lambda}|1\rangle$. Poiché vogliamo implementare $U|1\rangle = e^{2\pi i \tfrac{1}{3}}|1\rangle$, dobbiamo impostare $\lambda = \tfrac{2 \pi}{3}$.

##your code goes here##

Soluzione dell'esercizio: $\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. Esecuzione con la primitiva Sampler di IBM Quantum

Eseguiremo la QPE usando un dispositivo quantistico reale e seguiremo i 4 passi dei pattern Qiskit.

1. Mappa il problema in un formato nativo quantistico

2. Ottimizza i circuiti

3. Esegui il circuito target

4. Post-elabora i risultati

from qiskit_ibm_runtime import QiskitRuntimeService
from qiskit_ibm_runtime import Sampler

# Loading your IBM Quantum® account(s)

service = QiskitRuntimeService()

4.1 Passo 1: Mappa il problema in circuiti e operatori quantistici

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 Passo 2: Ottimizza per l'hardware target

# 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 Passo 3: Esegui sull'hardware target

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 Passo 4: Post-elabora i risultati

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'