Trasformata di Fourier quantistica

Per questo modulo Qiskit in Classrooms, gli studenti devono avere un ambiente Python funzionante con i seguenti pacchetti installati:

• qiskit v2.1.0 o versione più recente
• qiskit-ibm-runtime v0.40.1 o versione più recente
• qiskit-aer v0.17.0 o versione più recente
• qiskit.visualization
• numpy
• pylatexenc

Per configurare e installare i pacchetti sopra indicati, consulta la guida Installa Qiskit. Per eseguire job su computer quantistici reali, gli studenti dovranno creare un account con IBM Quantum® seguendo i passaggi nella guida Configura il tuo account IBM Cloud.

Questo modulo è stato testato e ha utilizzato 13 secondi di tempo QPU. Si tratta di una stima in buona fede; l'utilizzo effettivo può variare.

# Added by doQumentation — required packages for this notebook
!pip install -q numpy qiskit qiskit-aer qiskit-ibm-runtime

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

Introduzione

La trasformata di Fourier è uno strumento onnipresente con applicazioni in matematica, fisica, elaborazione del segnale, compressione dei dati e innumerevoli altri campi. Una versione quantistica della trasformata di Fourier, opportunamente denominata trasformata di Fourier quantistica, costituisce la base di alcuni dei più importanti algoritmi quantistici.

Oggi, dopo un ripasso della trasformata di Fourier classica, parleremo di come implementiamo la trasformata di Fourier quantistica su un computer quantistico. Quindi discuteremo una delle applicazioni della trasformata di Fourier quantistica a un algoritmo chiamato algoritmo di stima di fase. La stima di fase quantistica è una subroutine nel famoso algoritmo di fattorizzazione di Shor, talvolta definito il "gioiello della corona" dell'informatica quantistica. Questo modulo è propedeutico a un altro modulo dedicato all'algoritmo di Shor, ma è anche pensato per essere autonomo. La trasformata di Fourier quantistica è un algoritmo affascinante e utile di per sé!

La trasformata di Fourier classica

Prima di addentrarci nella trasformata di Fourier quantistica, ricordiamo innanzitutto la versione classica. La trasformata di Fourier è un metodo per passare da una cosiddetta "base" a un'altra. Puoi pensare a due basi come a diverse prospettive dello stesso problema: sono entrambi modi validi per esprimere una funzione, ma una o l'altra potrebbe essere più illuminante, a seconda del problema in esame. Alcuni esempi di coppie di basi collegate dalla trasformata di Fourier sono posizione e momento, e tempo e frequenza.

Vediamo un esempio di come la trasformata di Fourier potrebbe aiutarci a capire quale nota suona uno strumento in base alla sua forma d'onda audio. In genere, le forme d'onda sono rappresentate nella base temporale, ovvero l'ampiezza dell'onda è espressa come funzione del tempo.

Possiamo applicare la trasformata di Fourier a questa forma d'onda per passare dalla base temporale alla base delle frequenze:

Nella base delle frequenze, possiamo vedere chiaramente un picco netto a circa 260 Hz. È un Do centrale!

Potresti essere riuscito a determinare che veniva suonato un Do centrale senza l'uso di una trasformata di Fourier, ma cosa succede se vengono suonate più note contemporaneamente? In quel caso la forma d'onda diventa più complessa quando la rappresentiamo nella base temporale:

Ma lo spettro di frequenza identifica chiaramente tre picchi:

Questo era un accordo di Do maggiore, con le note Do, Mi e Sol.

Questo tipo di analisi di Fourier può aiutarci a estrarre le componenti di frequenza di qualsiasi tipo di segnale complesso.

Trasformata di Fourier discreta

La trasformata di Fourier è utile per qualsiasi numero di applicazioni di elaborazione del segnale. Ma nella maggior parte di queste applicazioni del mondo reale (incluso l'esempio musicale usato sopra), vogliamo trasformare un insieme discreto di $N$ punti dati, non una funzione continua. In questo caso, usiamo la trasformata di Fourier discreta. La trasformata di Fourier discreta (DFT) agisce su un vettore $(x_0, ..., x_{N-1})$ e lo mappa al vettore $(y_0, ..., y_{N-1})$ secondo la formula:

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

dove prendiamo $\omega_N^{jk} = e^{2\pi i \frac{jk}{N}}$. (Nota che esistono altre convenzioni con un segno meno nell'esponente, quindi fai attenzione quando incontri la DFT nella pratica.) Ricorda che $e^{2\pi i \frac{jk}{N}}$ è una funzione periodica, con periodo $\frac{N}{k}$. Quindi, moltiplicando per questa funzione, la trasformata di Fourier è essenzialmente un modo per scomporre la funzione (discreta) $\{x_{j}\}$ in una combinazione lineare delle sue funzioni periodiche costituenti, ciascuna con periodo $\frac{N}{k}$.

La trasformata di Fourier quantistica

Abbiamo appena visto come la trasformata di Fourier viene usata per rappresentare una funzione come combinazione lineare di un nuovo insieme di cosiddette "funzioni di base". Le trasformazioni di base vengono eseguite regolarmente anche sugli stati dei qubit. Ad esempio, lo stato di un singolo qubit $|\psi\rangle$ può essere espresso nella base computazionale $|\psi\rangle = c_0 |0\rangle + c_1 |1\rangle$, con stati di base $|0\rangle$ e $|1\rangle$, oppure nella base $X$ $|\psi\rangle = c_+ |+\rangle + c_- |-\rangle$ con stati di base $|+\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |1\rangle)$ e $|-\rangle = \frac{1}{\sqrt{2}} (|0\rangle - |1\rangle)$. Entrambe sono ugualmente valide, ma una potrebbe essere più naturale dell'altra a seconda del tipo di problema che stai cercando di risolvere.

Gli stati dei qubit possono anche essere espressi nella base di Fourier, dove uno stato è espresso in termini di combinazione lineare degli stati della base di Fourier $|\phi_y\rangle$, anziché dei soliti stati della base computazionale $|x\rangle$. Per fare ciò, è necessario applicare una trasformata di Fourier quantistica (QFT):

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

con $\omega_N^{yx} = e^{\frac{2\pi i y x}{N}}$ come sopra, e $N$ è il numero di stati di base nel tuo sistema quantistico. Nota che, poiché stiamo lavorando con i qubit, $m$ qubit ti danno $2^m$ stati di base, quindi $N=2^m$. Qui, gli stati di base sono scritti come un singolo numero $|x\rangle$ dove $x$ varia da $0$ a $N-1$, ma potresti più tipicamente vedere gli stati di base espressi come $|00...00\rangle$, $|00...01\rangle$, $|00...11\rangle$, ..., $|11...11\rangle$, dove ogni cifra binaria rappresenta lo stato del qubit 0 attraverso $m-1$, da destra a sinistra. Esiste un modo semplice per convertire questi stati binari in un singolo numero: trattali semplicemente come numeri binari! Quindi, $|00...00\rangle = |0\rangle$, $|00...01\rangle = |1\rangle$, $|00...10\rangle = |2\rangle$, $|00...11\rangle = |3\rangle$, e così via, fino a $|11...11\rangle = |2^m -1\rangle = |N-1\rangle$.

Costruire intuizione per gli stati della base di Fourier

Abbiamo appena esaminato cosa sono gli stati della base computazionale e come sono ordinati: sono l'insieme degli stati in cui ogni qubit è in $0$ o $1$, e li ordiniamo dallo stato in cui tutti i qubit sono $0$, $|00...00\rangle$, allo stato in cui sono tutti $1$, $|11...11\rangle$.

Ma come possiamo dare senso agli stati della base di Fourier? Tutti gli stati della base di Fourier sono sovrapposizioni uguali di tutti gli stati della base computazionale, ma ogni stato differisce dagli altri nella periodicità della fase delle componenti. Per capire questo in modo più concreto, esaminiamo i quattro stati della base di Fourier di un sistema a due qubit. Il più basso stato di Fourier è quello la cui fase non varia affatto:

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

Possiamo visualizzare questo stato tracciando l'ampiezza complessa di ciascuno dei termini. La linea rossa guida l'occhio per mostrare come la fase di questa ampiezza si avvolge nel piano complesso in funzione dello stato della base computazionale. Per $|\phi_0\rangle$, la fase rimane costante:

Il successivo stato della base di Fourier è quello le cui fasi delle componenti si avvolgono da $0$ a $2\pi$ una sola volta:

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

E possiamo vedere questo avvolgimento nel grafico dell'ampiezza complessa rispetto allo stato della base computazionale:

Quindi, ogni stato ha una fase che è $2\pi/4$ radianti più alta dello stato precedente quando sono ordinati nel modo standard, poiché in questo esempio abbiamo quattro stati di base ($N=4$). Il successivo stato di base si avvolge da 0 a 2$\pi$ due volte:

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

Infine, la componente di Fourier più alta è quella con la fase a variazione più rapida. Per il nostro esempio con due qubit, è quella le cui fasi si avvolgono da 0 a $2\pi$ tre volte:

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

In generale, per uno stato a $m$ qubit, ci saranno $2^m$ stati della base di Fourier, la cui frequenza nella variazione di fase va da costante, per $|\phi_0\rangle$, a rapidamente variante per $|\phi_{2^m-1}\rangle$, completando $2^m-1$ avvolgimenti attorno a $2\pi$ sulla sovrapposizione degli stati. Quindi, quando prendiamo una QFT di uno stato quantistico, stiamo essenzialmente eseguendo la stessa analisi di base che abbiamo fatto per la forma d'onda musicale nell'Introduzione. Stiamo determinando le componenti di frequenza di Fourier che contribuiscono a creare lo stato quantistico di interesse.

Prova alcuni esempi di QFT

Proviamo a continuare a costruire la nostra intuizione per la trasformata di Fourier quantistica creando uno stato nella base computazionale, poi vedendo cosa succede quando applichiamo la QFT. Per ora, tratteremo la QFT come una scatola nera che applichiamo usando QFTGate dalla libreria di circuit Qiskit. Più avanti, daremo un'occhiata sotto il cofano per vedere come è implementata.

Iniziamo caricando i pacchetti necessari e selezionando un dispositivo su cui eseguire il nostro circuit:

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

# Load the Qiskit Runtime 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)

ibm_pinguino2

Se non hai tempo disponibile nel tuo account o vuoi usare un simulatore per qualsiasi motivo, puoi eseguire la cella sottostante per configurare un simulatore che imita il dispositivo quantistico che abbiamo selezionato sopra:

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

Singolo stato della base computazionale

Prima, proviamo a trasformare un singolo stato della base computazionale. Inizieremo creando un stato computazionale casuale:

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

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

Ora, applichiamo la trasformata di Fourier a questo stato con QFTGate:

# Step 1: Map

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

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

Come puoi vedere, misuriamo le popolazioni di ciascuno stato come più o meno uguali, a parte del rumore sperimentale e statistico. Quindi, se prendi la QFT di un singolo stato della base computazionale, il risultato è una sovrapposizione uguale di tutti gli stati. Se hai familiarità con le trasformate di Fourier, questo probabilmente non ti sorprende. Un principio di base che può aiutarci a costruire una connessione intuitiva tra una funzione e la sua trasformata di Fourier è che la larghezza di una funzione è inversamente proporzionale alla larghezza della sua trasformata di Fourier. Quindi, qualcosa che è molto localizzato nel tempo, come un impulso molto breve, richiederà un ampio intervallo di frequenze per generare quell'impulso. Quel segnale sarà molto ampio nello spazio di Fourier.

Questo fatto è in realtà correlato all'incertezza quantistica! Il principio di indeterminazione di Heisenberg è tipicamente enunciato come $\Delta x \Delta p \ge \hbar / 2$. Quindi, se l'incertezza in $x$ ($\Delta x$) è piccola, l'incertezza nel momento ($\Delta p$) deve essere grande, e viceversa. Si scopre che passare dalla base della posizione $x$ alla base del momento $p$ si realizza tramite una trasformata di Fourier.

Nota: Tieni presente che stiamo misurando le popolazioni in ciascuno degli stati di base, quindi perdiamo informazioni sulle fasi relative tra le varie parti della sovrapposizione. Quindi, mentre la QFT di qualsiasi singolo stato della base computazionale produrrà la stessa distribuzione uniforme di popolazione su tutti gli stati di base, le fasi non saranno necessariamente le stesse.

Due stati della base computazionale

Ora vediamo cosa succede quando prepariamo una sovrapposizione di stati della base computazionale. Come pensi che sarà la trasformata di Fourier in questo caso?

Scegliamo la sovrapposizione:

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

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

Ora, applichiamo la trasformata di Fourier a questo stato con QFTGate:

# Step 1: Map

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

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

Questo potrebbe essere un po' più sorprendente. Sembra che la QFT dello stato $|\psi\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |N/2\rangle)$ sia una sovrapposizione di tutti gli stati di base pari. Ma se torniamo alla nostra visualizzazione di ogni stato di base $|\phi_y\rangle$, e di come la fase di ogni componente si avvolge $2\pi$ $y$ volte, allora il motivo per cui otteniamo questo risultato potrebbe diventare chiaro.

Verifica la tua comprensione

Leggi la/le domanda/e di seguito, rifletti sulla tua risposta, poi clicca sul triangolo per rivelare la soluzione.

Usando il suggerimento precedente, spiega perché il risultato che abbiamo ottenuto per la QFT di $|\psi\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |N/2\rangle)$ è atteso.

Risposta:

Lo stato originale ha una fase relativa di 0 (o un multiplo intero di $2\pi$) tra le due parti della sovrapposizione. Quindi, sappiamo che questo stato ha componenti di Fourier le cui fasi corrispondono in quel modo: quelle che hanno uno sfasamento di fase 0 tra il termine |0000> e il termine |1000>. Ogni stato della base di Fourier $|\phi_y\rangle$ è composto da termini la cui fase si accumula a una velocità di $2\pi y/N$, il che significa che, ordinati nel modo solito, ogni termine nella sovrapposizione ha una fase di $2\pi y/N$ maggiore del termine precedente. Quindi, al punto intermedio $N/2$, vogliamo che la fase $2\pi y/N \cdot N/2$ sia un multiplo intero di $2\pi$. Questo accade quando $y$ è pari.

Quale sovrapposizione di stati computazionali corrisponderebbe a una QFT con picchi su ogni numero binario dispari?

Risposta:

Se prendessi la QFT dello stato $\psi = |0\rangle - |N/2\rangle$, vedresti i picchi su ogni stato numerato binario dispari.

Analisi dell'algoritmo QFT

Ora che abbiamo acquisito maggiore intuizione sulla relazione tra gli stati dei qubit nella base computazionale e nella base di Fourier, approfondiamo l'algoritmo QFT vero e proprio. In altre parole, quali gate implementiamo concretamente sul quantum computer per realizzare questa trasformata?

Partiamo in piccolo, con un singolo qubit. Questo significa che avremo due stati della base. QFT$_2$ trasforma gli stati della base computazionale $|0\rangle$ e $|1\rangle$ negli stati della base di Fourier $\phi_0$ e $\phi_1$:

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

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

Verifica la tua comprensione

Leggi la/le domanda/e qui sotto, pensa alla risposta, poi clicca sul triangolo per vedere la soluzione.

Usa l'equazione della QFT nella sezione precedente per verificare questi due stati della base di Fourier.

Risposta:

La formula generale della QFT è:

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

Per un singolo qubit ($n=1$), $N=2^n=2$, e $\omega_N^{xy} = e^{2\pi i \frac {y x}{2}}$. Quindi:

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

Osserva le due equazioni. Potresti già conoscere un gate quantistico che può essere usato per implementare questa trasformata. In altre parole, esiste un gate che trasforma gli stati della base computazionale $|0\rangle$ e $|1\rangle$ nei rispettivi stati della base di Fourier $|\phi_0\rangle$ e $|\phi_1\rangle$. È il gate di Hadamard! Questo diventa ancora più chiaro se introduciamo una rappresentazione matriciale dell'operazione 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$

Se non hai familiarità con questa notazione per esprimere un operatore quantistico, non preoccuparti! È un modo per rappresentare una matrice $N \times N$, dove $x$ e $y$ indicizzano le colonne e le righe della matrice da $0$ a $N-1$, e $\omega_N^{xy}$ è il valore di quella particolare cella. Ad esempio, la cella nella colonna 0 e nella riga 2 sarebbe semplicemente $\omega_N^{0,2} = e^{2 \pi i \frac{0 \times 2}{N}} = 1$.

In questa rappresentazione, ciascuno degli stati della base computazionale è associato a uno dei vettori di base:

$$\begin{pmatrix} 1 \\ 0 \\ \vdots \\ 0 \end{pmatrix}, |1\rangle = \begin{pmatrix} 0 \\ 1 \\ \vdots \\ 0 \end{pmatrix}, |N-1\rangle = \begin{pmatrix} 0 \\ 0 \\ \vdots \\ 1 \end{pmatrix}.$$

Se vuoi approfondire questa rappresentazione, consulta la lezione di John Watrous sui sistemi multipli nel corso Basics of quantum information.

Proviamo a costruire la matrice per QFT$_4$. Usando la formula precedente, troviamo che

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

Per implementare questa matrice su un quantum computer, dobbiamo capire quale combinazione di gate applicati a quali qubit produce una trasformazione unitaria che corrisponde alla matrice precedente. Sappiamo già che uno dei gate necessari è l'Hadamard. Un altro gate di cui avremo bisogno è il gate di fase controllata (controlled-phase), che applica una fase relativa $\alpha$ allo stato del qubit target, a condizione che il qubit di controllo si trovi nello stato $|1\rangle$. In forma matriciale si presenta così:

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

Poiché solo lo stato $|11\rangle$ viene modificato, non importa quale qubit sia considerato il "controllo" e quale il "target". Il risultato sarà lo stesso in entrambi i casi.

Infine, avremo bisogno anche di alcuni gate SWAP. Un gate SWAP scambia gli stati di due qubit. Si presenta così:

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

La procedura per costruire un circuito QFT$_{2^m}$ su $m$ qubit è iterativa: si applica prima QFT$_{2^{m-1}}$ ai qubit da $1$ a $m-1$, poi si aggiungono alcuni gate tra il qubit $0$ e gli altri $m-1$ qubit. Ma per applicare QFT$_{2^{m-1}}$, occorre prima applicare QFT$_{2^{m-2}}$ ai qubit da 2 a $m-1$, quindi aggiungere alcuni gate tra il qubit 1 e i qubit rimanenti da $2$ a $m-1$. È come una matrioska russa: ogni bambola aggiunge un fattore due alla dimensione del circuito QFT, con la bambola più piccola al centro, che è QFT$_2$, ovvero il gate di Hadamard.

Per inserire una bambola nella successiva più grande — aumentando così la dimensione della QFT di un fattore due — si segue sempre la stessa procedura:

1. Prima di tutto, applica QFT$_{2^{m-1}}$ agli $m-1$ qubit più in basso. Questa è la tua "bambola più piccola" dell'insieme di matrioske, che stai per inserire nella bambola successiva più grande.
2. Usa il qubit immediatamente più in alto come controllo e applica gate di fase controllata a ciascuno degli $m-1$ qubit in basso, con fasi sugli stati della base standard di ciascuno dei rimanenti $m-1$ qubit.
3. Applica un Hadamard allo stesso qubit più in alto usato come controllo nei gate di fase.
4. Usa gate SWAP per permutare l'ordine dei qubit in modo che il bit meno significativo (in alto) diventi il più significativo (in basso), e tutti gli altri si spostino di uno verso l'alto.

Abbiamo già usato la funzione QFTGate della circuit library di Qiskit, ma ora guardiamo all'interno di alcuni di questi gate QFT per verificare la procedura descritta. Possiamo farlo con decompose().

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

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

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

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

Quindi, guardando le prime quattro QFT, dovresti iniziare a vedere come ciascuna sia annidata all'interno della successiva. Potresti aver notato, però, che alcuni gate di fase non corrispondono esattamente a quanto prescritto dalla procedura descritta, e che gli SWAP non appaiono dopo ogni subroutine, ma solo alla fine della QFT completa. Questo ci risparmia gate inutili, che allungherebbero l'esecuzione del circuito e lo renderebbero più soggetto a errori. Invece di implementare gli SWAP dopo ogni bambola annidata, il circuito tiene traccia di dove ogni stato dei qubit dovrebbe trovarsi e regola di conseguenza i qubit a cui applicare i gate di fase. Poi, un set finale di SWAP alla fine mette tutto al suo posto.

Applicare la QFT: la stima di fase

Vediamo come la QFT può essere usata per risolvere un problema utile nel quantum computing. Il calcolo della trasformata quantistica di Fourier inversa è un passaggio necessario in un algoritmo noto come Quantum Phase Estimation (QPE), che è a sua volta una subroutine in molti altri algoritmi, tra cui il "gioiello della corona" degli algoritmi quantistici: l'algoritmo di fattorizzazione di Shor.

L'obiettivo della QPE è stimare gli autovalori di un operatore unitario. Gli operatori unitari sono onnipresenti nel quantum computing, e spesso trovare gli autovalori dei rispettivi autovettori è un passaggio necessario in un algoritmo più grande. A seconda del problema, un autovalore può rappresentare l'energia di un Hamiltoniano in un problema di simulazione, può aiutarci a trovare i fattori primi di un numero nell'algoritmo di Shor, oppure può contenere altre informazioni essenziali. La QPE è una delle subroutine più importanti e ampiamente usate nel quantum computing.

Quindi, cosa c'entra tutto questo con la trasformata quantistica di Fourier? Bene, come forse ricordi, ogni autovalore $\lambda$ di un operatore unitario ha modulo $|\lambda| = 1$. Possiamo quindi scrivere ogni autovalore come un numero complesso di modulo uno:

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

dove $\theta$ è un numero reale compreso tra 0 e 1. Se vuoi approfondire le matrici unitarie, consulta la lezione di John Watrous sull'argomento nel corso Basics of quantum information.

Nota che $\lambda$ è periodico in $\theta$. Già questo potrebbe suggerirti che potrebbe essere coinvolta una QFT, dato che abbiamo visto quanto siano utili le QFT per analizzare funzioni periodiche. Di seguito, percorreremo l'algoritmo e vedremo con precisione come entra in gioco la QFT.

Come funziona la QPE

Per prima cosa, partiamo dall'algoritmo QPE più semplice, che stima la fase con una singola cifra binaria di precisione. In altre parole, questo algoritmo riesce a distinguere tra $\theta = 0$ e $\theta = 1/2$, ma non va oltre. Ecco il diagramma del circuito:

I qubit vengono preparati nello stato $|\pi_0\rangle = |\psi\rangle|0\rangle$, dove il qubit $0$ è nello stato $|0\rangle$ e i qubit rimanenti sono nello stato $|\psi\rangle$, che è un autostato di $U$. Dopo il primo Hadamard, lo stato dei qubit diventa:

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

Il gate successivo è un gate "controlled-$U$". Questo applica l'operazione unitaria $U$ ai qubit inferiori che si trovano nello stato $|\psi\rangle$ se il qubit 0 è nello stato $|1\rangle$, ma non fa nulla a $|\psi\rangle$ se il qubit 0 è nello stato $|0\rangle$. Questo trasforma i qubit nello stato:

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

È successa una cosa strana: il gate controlled-$U$ usa solo il qubit $0$ come qubit di controllo, quindi si potrebbe pensare che questo gate non cambi affatto lo stato del qubit 0. Eppure lo fa! Anche se l'operazione è stata applicata ai qubit inferiori, l'effetto complessivo del gate è di cambiare la fase del qubit $0$. Questo fenomeno è noto come "meccanismo di phase kickback" ed è usato in molti algoritmi quantistici, tra cui gli algoritmi di Deutsch-Josza e di Grover. Se vuoi saperne di più sul meccanismo di phase kickback, consulta la lezione di John Watrous sugli Algoritmi di query quantistici nel corso Fundamentals of quantum algorithms.

Dopo il phase kickback, applichiamo un altro Hadamard al qubit $0$, che porta allo stato:

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

Quindi, quando misuriamo il qubit $0$ alla fine, misureremo $|0\rangle$ con certezza del 100% se $\theta = 0$ e misureremo $|1\rangle$ con certezza del 100% se $\theta = \frac{1}{2}$ (ammesso che il nostro quantum computer sia perfetto, privo di rumore). Se $\theta$ è diverso da questi valori, la misurazione finale è solo probabilistica e ci dice solo così tanto.

QPE con maggiore precisione: più qubit

Possiamo estendere questo semplice concetto a un algoritmo più complesso con precisione arbitraria. Se invece di usare solo il qubit $0$ per misurare la fase, usiamo $m$ qubit da $0$ a $m-1$, saremo in grado di stimare la fase con $m$ bit di precisione. Vediamo come funziona:

Questo circuito QPE più preciso parte allo stesso modo della versione a un singolo bit: gli Hadamard vengono applicati ai primi $m$ qubit, e i qubit rimanenti vengono preparati nello stato $|\psi\rangle$, creando lo stato:

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

Ora vengono applicate le unitarie controllate. Il qubit $0$ è il controllo per la stessa unitaria $U$ di prima. Ma ora il qubit $1$ è il controllo per l'unitaria $U^2$, che è semplicemente $U$ applicata due volte. Quindi, l'autovalore di $U^2$ è $e^{2*2\pi i \theta}$. In generale, ogni qubit $k$ da 0 a $m-1$ sarà il controllo per l'unitaria $U^{2^k}$. Ciò significa che ciascuno di questi qubit sperimenterà un phase kickback di $e^{2^k*2\pi i \theta}$. Il risultato è lo stato:

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

Questo può essere riscritto come una somma sugli stati della base computazionale:

$|\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 somma ti sembra familiare? È una QFT! Ricorda l'equazione per la trasformata quantistica di Fourier:

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

Quindi, se la fase $\theta = y/2^m$ per qualche intero $y$ compreso tra $0$ e $2^m-1$, allora applicare la QFT inversa a questo stato darà come risultato lo stato:

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

e da $|y\rangle$ possiamo dedurre $\theta$.

Se $\theta/2^m$ non è però un multiplo intero, allora applicare la QFT inversa approssimerà solo $\theta$. La qualità dell'approssimazione di $\theta$ sarà probabilistica, il che significa che non otterremo sempre la migliore approssimazione, ma sarà abbastanza vicina; e più qubit $m$ si usano, migliore sarà l'approssimazione. Per sapere come quantificare questa approssimazione di $\theta$, consulta la lezione di John Watrous sulla Stima di fase e fattorizzazione nel corso Fundamentals of quantum algorithms.

Conclusione

Questo modulo ha fornito una panoramica di cosa sia una QFT, di come venga implementata su un quantum computer e di quanto possa essere utile per risolvere problemi. Abbiamo dato un assaggio della sua utilità vedendo come può essere impiegata nella stima di fase quantistica per apprendere gli autovalori di una matrice unitaria.

Concetti fondamentali

• La Trasformata Quantistica di Fourier è l'analogo quantistico della Trasformata di Fourier Discreta.
• La QFT è un esempio di trasformazione di base.
• La procedura di Quantum Phase Estimation si basa sul meccanismo di phase kickback delle operazioni unitarie controllate, nonché su una QFT inversa.
• La QFT e la QPE sono entrambe subroutine ampiamente utilizzate in numerosi algoritmi quantistici.

Domande

Vero/Falso

1. V/F La Trasformata Quantistica di Fourier è l'analogo quantistico della trasformata di Fourier discreta classica (DFT).
2. V/F La QFT può essere implementata usando solo gate Hadamard e CNOT.
3. V/F La QFT è un componente chiave dell'algoritmo di Shor.
4. V/F L'output della Quantum Phase Estimation è uno stato quantistico che rappresenta l'autovettore dell'operatore.
5. V/F La QPE richiede l'uso della Trasformata Quantistica di Fourier inversa (QFT$^\dag$).
6. V/F Nella QPE, se la fase $\phi$ è esattamente rappresentabile con $n$ bit, l'algoritmo fornisce il risultato corretto con probabilità 1.

Risposte brevi

1. Quanti qubit sono necessari per eseguire una QFT su un sistema con $2^n$ punti dati?
2. La QFT può essere applicata a uno stato che non è uno stato della base computazionale? In caso affermativo, cosa succede?
3. In che modo il numero di qubit di controllo usati nella QPE influisce sulla risoluzione della stima di fase risultante?

Problemi

1. Usa la moltiplicazione di matrici per verificare che i passi dell'algoritmo QFT portino effettivamente alla matrice $\text{QFT}_4$:

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

(Non è necessario farlo a mano!)

Problemi avanzati

1. Crea uno stato a quattro qubit che sia una sovrapposizione uguale di tutte le basi computazionali dispari: $|\psi\rangle = |0001\rangle + |0011\rangle + |0101\rangle + |0111\rangle +|1001\rangle +|1011\rangle +|1101\rangle +|1111\rangle$. Poi esegui una QFT sullo stato. Qual è lo stato risultante? Spiega perché il tuo risultato ha senso, usando la tua conoscenza delle trasformate di Fourier.