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 più recente
• qiskit-ibm-runtime v0.40.1 o più recente
• qiskit-aer v0.17.0 o più recente
• qiskit.visualization
• numpy
• pylatexenc

Per configurare e installare i pacchetti di cui sopra, consultare la guida Installare Qiskit. Per poter eseguire i lavori su computer quantistici reali, gli studenti dovranno configurare un account su IBM Quantum® seguendo i passaggi della guida Set up your IBM Cloud account.

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

# 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 dei segnali, compressione dei dati e in innumerevoli altri campi. Una versione quantistica della trasformata di Fourier, giustamente chiamata trasformata di Fourier quantistica, costituisce la base di alcuni dei più importanti algoritmi quantistici.

Oggi, dopo aver ricordato la trasformata di Fourier classica, parleremo di come implementare la trasformata di Fourier quantistica su un computer quantistico. Poi, 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 del famoso algoritmo di fattorizzazione di Shor, talvolta definito il "gioiello della corona" dell'informatica quantistica. Questo modulo si basa su un altro modulo dedicato all'algoritmo di Shor, ma è anche pensato per essere indipendente. 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 la versione classica. La trasformata di Fourier è un metodo di trasformazione da una cosiddetta "base" a un'altra. Si può pensare a due basi come a prospettive diverse dello stesso problema: sono entrambi modi validi per esprimere una funzione, ma l'uno o l'altro potrebbero essere più illuminanti, a seconda del problema in questione. Alcuni esempi di coppie di basi collegate dalla trasformata di Fourier sono la posizione e la quantità di moto e il tempo e la frequenza.

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

Possiamo trasformare questa forma d'onda di Fourier per passare dalla base temporale alla base di frequenza:

Nella base di frequenza, si può facilmente notare un chiaro picco a circa 260 Hz. Questo è un do centrale!

Ora, si potrebbe essere in grado di determinare che è stato suonato un do centrale senza l'uso di una trasformata di Fourier, ma cosa succede se vengono suonate più note contemporaneamente? La forma d'onda diventa più complicata quando la tracciamo sulla base del tempo:

Ma lo spettro di frequenza identifica chiaramente tre picchi:

Si trattava di 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 complicato.

Trasformata discreta di Fourier

La trasformata di Fourier è utile per numerose applicazioni di elaborazione dei segnali. Ma nella maggior parte di queste applicazioni reali (compreso l'esempio della musica che abbiamo usato sopra), vogliamo trasformare un insieme discreto di punti di dati $N$ - non una funzione continua. In questo caso, si utilizza la trasformata discreta di Fourier. La trasformata discreta di Fourier (DFT) agisce su un vettore $(x_0, ..., x_{N-1})$ e lo mappa nel 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}}$. (Si noti che esistono altre convenzioni che prevedono il segno meno nell'esponenziale, quindi fate attenzione quando vedete la DFT in giro) Ricordiamo 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 costitutive, ciascuna con periodo $\frac{N}{k}$.

La trasformata di Fourier quantistica

Abbiamo quindi visto come la trasformata di Fourier viene utilizzata per rappresentare una funzione come combinazione lineare di un nuovo insieme di cosiddette "funzioni base" Le trasformazioni di base vengono effettuate 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 gli stati base $|0\rangle$ e $|1\rangle$, oppure nella base $X$ $|\psi\rangle = c_+ |+\rangle + c_- |-\rangle$ con gli stati 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 si sta cercando di risolvere.

Gli stati dei Qubit possono anche essere espressi nella base di Fourier, dove uno stato è espresso in termini di una combinazione lineare degli stati della base di Fourier $|\phi_y\rangle$, piuttosto che degli stati della base usuale, 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 vostro sistema quantistico. Si noti che, poiché ora stiamo lavorando con i qubit, $m$ qubit forniscono $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 più comunemente si vedono 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 da 0 a $m-1$, da destra a sinistra. Esiste un modo semplice per convertire questi stati binari in un unico numero: basta trattarli 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$.

Sviluppare l'intuizione per gli stati di base di Fourier

Abbiamo appena spiegato quali sono gli stati della base computazionale e come sono ordinati: sono l'insieme degli stati in cui ogni qubit si trova o in $0$ o in $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 un 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 dall'altro per la periodicità della fase dei componenti. Per capire più concretamente questo concetto, esaminiamo i quattro stati della base di Fourier di un sistema a due qubit. Lo stato di Fourier più basso è 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 snoda sul piano complesso in funzione dello stato della base computazionale. Per $|\phi_0\rangle$, la fase rimane costante:

Lo stato successivo in base di Fourier è quello le cui fasi delle componenti si snodano 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 base computazionale:

Quindi, ogni stato ha una fase che è $2\pi/4$ superiore a quella dello stato che lo precede quando sono ordinati in modo standard, poiché in questo esempio abbiamo quattro stati base ( $N=4$ ). Lo stato base successivo si snoda 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 variazione di fase più rapida. Nel nostro esempio con due qubit, è quello le cui fasi si avvolgono da 0 a $2\pi$ per 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 qubit $m$, ci saranno stati di base di Fourier $2^m$, la cui frequenza nella variazione di fase varia da costante, per $|\phi_0\rangle$, a rapidamente variabile per $|\phi_{2^m-1}\rangle$, completando $2^m-1$ avvolgimenti attorno a $2\pi$ sulla sovrapposizione di stati. Quindi, quando prendiamo una QFT di uno stato quantistico, stiamo essenzialmente facendo 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 alla creazione dello stato quantistico di interesse.

Prova alcuni esempi di QFT

Cerchiamo di continuare a costruire la nostra intuizione per la trasformata di Fourier quantistica creando uno stato nella base computazionale e vedendo cosa succede quando applichiamo la QFT ad esso. Per ora, tratteremo la QFT come una scatola nera che applicheremo utilizzando il sito QFTGate della libreria di circuiti Qiskit. Più tardi, daremo un'occhiata sotto il cofano per vedere come viene implementato.

Iniziamo caricando i pacchetti necessari e selezionando un dispositivo su cui far girare il nostro circuito:

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

Se non avete tempo a disposizione sul vostro account o volete usare un simulatore per qualsiasi motivo, potete eseguire la cella qui sotto per impostare un simulatore che imiti 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)

Stato di base computazionale singolo

Per prima cosa, proviamo a trasformare un singolo stato di base computazionale. Inizieremo con la creazione di uno 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")

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:

Trasformiamo ora questo stato di Fourier con 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:

Come si può vedere, le popolazioni di ogni stato sono più o meno uguali, con o senza un po' di rumore sperimentale e statistico. Quindi, se si prende la QFT di un singolo stato base computazionale, il risultato è una sovrapposizione uguale di tutti gli stati. Se avete familiarità con le trasformate di Fourier, questo probabilmente non vi sorprenderà. Un principio di base che può aiutarci a costruire un collegamento intuitivo tra una funzione e la sua trasformata di Fourier è che l'ampiezza di una funzione è inversamente proporzionale all'ampiezza della sua trasformata di Fourier. Quindi, qualcosa che è molto localizzato nel tempo, ad esempio un impulso molto breve, richiederà un'ampia gamma di frequenze per generare quell'impulso. Il segnale sarà molto ampio nello spazio di Fourier.

Questo fatto è in realtà legato all'incertezza quantistica! Il principio di indeterminazione di Heisenberg è tipicamente espresso come $\Delta x \Delta p \ge \hbar / 2$. Quindi, se l'incertezza in $x$ ( $\Delta x$ ) è piccola, l'incertezza nella quantità di moto ( $\Delta p$ ) deve essere grande, e viceversa. Si scopre che la trasformazione dalla base di posizione $x$ alla base di quantità di moto $p$ avviene attraverso una trasformata di Fourier.

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

Due stati di base computazionali

Vediamo ora cosa succede quando prepariamo una sovrapposizione di stati base computazionali. Come pensate 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")

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:

Trasformiamo ora questo stato di Fourier con 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:

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 base pari. Ma se ripensiamo alla nostra visualizzazione di ogni stato base $|\phi_y\rangle$, e a come la fase di ogni componente si snoda intorno a $2\pi$ $y$ volte, allora il motivo per cui otteniamo questo risultato potrebbe diventare chiaro.

Verifica la tua comprensione

Sulla base del suggerimento riportato sopra, spiega perché il risultato ottenuto per la teoria quantistica dei campi dell’ $|\psi\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |N/2\rangle)$ e è quello previsto.

• Risposta

  Lo stato originale ha una fase relativa di 0 (o un multiplo intero di $2\pi$ ) tra le due parti della sovrapposizione. Sappiamo quindi che questo stato ha componenti di Fourier le cui fasi coincidono in questo modo: quelle che hanno uno spostamento di fase pari a 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 al ritmo di $2\pi y/N$, il che significa che, ordinati nel modo consueto, ogni termine della sovrapposizione ha una fase di $2\pi y/N$ maggiore del termine che lo precede. Quindi, a metà strada $N/2$, vogliamo che la fase $2\pi y/N * N/2$ sia un multiplo intero di $2\pi$. Questo accade quando $y$ è pari.

Quale sovrapposizione di stati computazionale corrisponderebbe a una teoria quantistica dei campi con picchi su ogni numero binario dispari?

• Risposta

  Se si prendesse la QFT dello stato $\psi = |0\rangle - |N/2\rangle$, si vedrebbero dei picchi su ogni stato dispari con numero binario.

Scomporre l'algoritmo QFT

Ora che abbiamo acquisito una maggiore intuizione della relazione tra gli stati dei qubit nella base computazionale e nella base di Fourier, analizziamo l'algoritmo QFT stesso. In altre parole, quali porte implementare nel computer quantistico per ottenere questa trasformazione?

Cominciamo in piccolo, con un singolo qubit. Ciò significa che avremo due stati base. La QFT $_2$ trasforma gli stati base computazionali $|0\rangle$ e $|1\rangle$ in stati 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

Utilizza l'equazione della teoria quantistica dei campi (QFT) riportata nella sezione precedente per verificare questi due stati di base di Fourier sopra indicati.

• 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, si ha

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

Date un'occhiata a queste due equazioni. Forse conoscete già una porta quantica che può essere utilizzata per implementare questa trasformazione. Esiste cioè un gate che trasforma gli stati base computazionali $|0\rangle$ e $|1\rangle$ nei rispettivi stati base di Fourier $|\phi_0\rangle$ e $|\phi_1\rangle$. È un gate di Hadamard! Ciò 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 avete familiarità con questa notazione per esprimere un operatore quantistico, non c'è problema! È 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 voce. Quindi, la voce nella 0a colonna e nella 2a riga, ad esempio, sarà semplicemente $\omega_N^{0,2} = e^{2 \pi i \frac{0 \times 2}{N}} = 1$.

In questa rappresentazione, ciascuno degli stati base computazionali è associato a uno dei vettori base:

Se volete approfondire questa rappresentazione, consultate la lezione di John Watrous sui sistemi multipli nel corso Fondamenti di informazione quantistica.

Proviamo a costruire la matrice per la QFT $_4$. Utilizzando 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 computer quantistico, dovremo capire quale combinazione di gate applicata a quali qubit ci darà una trasformazione unitaria che corrisponde alla matrice di cui sopra. Conosciamo già una delle porte che saranno necessarie: l'Hadamard. Un altro gate di cui avremo bisogno è il gate a fase controllata, che applica una fase relativa $\alpha$ allo stato del qubit di destinazione, finché il qubit di controllo si trova nello stato $|1\rangle$. In forma di matrice si presenta come:

$\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é viene modificato solo lo stato $|11\rangle$, non ha importanza quale qubit sia considerato il "controllo" e quale il "bersaglio" Il risultato sarà lo stesso in entrambi i casi.

Infine, avremo bisogno anche di alcune porte SWAP. Un gate SWAP scambia gli stati di due qubit. Sembra che:

$\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}$ sui qubit $m$ è iterativa: si applica prima la QFT $_{2^{m-1}}$ ai qubit da $1$ a $m-1$, poi si aggiungono alcuni gate tra il qubit $0$ e gli altri qubit $m-1$. Ma per applicare la QFT $_{2^{m-1}}$, bisogna prima applicare la QFT $_{2^{m-2}}$ ai qubit da 2 a $m-1$, poi aggiungere alcuni gate tra il qubit 1 e i restanti qubit da $2$ a $m-1$. È come una matrioska russa: ogni bambola aggiunge un fattore di due alla dimensione del circuito QFT, con la bambola più piccola al centro, che è la QFT $_2$, o la porta di Hadamard.

Per mettere una bambola all'interno di una bambola di dimensioni immediatamente superiori, aumentando quindi la dimensione della QFT di un fattore due, si segue sempre la stessa procedura:

1. Per prima cosa, applicare la QFT $_{2^{m-1}}$ ai qubit più bassi $m-1$. Questa è la "bambola più piccola" della matrioska russa, che presto verrà inserita nella bambola più grande.
2. Usare il qubit successivo come controllo e applicare porte di fase controllate a ciascuno dei qubit inferiori $m-1$, con fasi agli stati base standard di ciascuno dei qubit rimanenti $m-1$.
3. Eseguire un Hadamard sullo stesso qubit più in alto che è stato usato come controllo nelle porte di fase.
4. Utilizzare le porte SWAP per modificare l'ordine dei qubit in modo che il bit meno significativo (in alto) diventi il bit più significativo (in basso) e tutti gli altri si spostino di uno.

Abbiamo già utilizzato la funzione QFTGate della libreria di circuiti Qiskit, ma ora diamo un'occhiata all'interno di alcune di queste porte QFT per verificare la procedura sopra descritta. Possiamo farlo con 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:

Quindi, si spera che dalle prime quattro QFT si possa iniziare a vedere come ognuna di esse sia annidata all'interno della successiva più grande. Avrete notato, tuttavia, che alcune delle porte di fase non sono esattamente come prescritto nella procedura che abbiamo illustrato sopra, e che gli SWAP non compaiono dopo ogni subroutine, ma solo alla fine dell'intera QFT. In questo modo si risparmiano gate non necessari, che richiederebbero più tempo al circuito e sarebbero più soggetti a errori. Invece di implementare lo SWAP dopo ogni bambola annidata, il circuito tiene traccia dello stato di ogni qubit e regola di conseguenza i qubit a cui applica le porte di fase. Alla fine, un'ultima serie di SWAP rimette tutto al suo posto.

Applicare il QFT: stima di fase

Vediamo come la QFT può essere utilizzata per risolvere un problema utile nell'informatica quantistica. Il calcolo della trasformata quantistica inversa di Fourier è un passo necessario in un algoritmo noto come Quantum Phase Estimation (QPE), che è a sua volta una subroutine in molti altri algoritmi, compreso 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 nell'informatica quantistica e spesso la ricerca degli autovalori dei loro autovalori associati è un passo necessario in un algoritmo più ampio. A seconda del problema, un autovalore può rappresentare l'energia di un'hamiltoniana in un problema di simulazione, può aiutarci a trovare i fattori primi di un numero nell'algoritmo di Shor o può contenere altre informazioni essenziali. QPE è una delle subroutine più importanti e più utilizzate nell'informatica quantistica.

Cosa c'entra tutto questo con la trasformata di Fourier quantistica? Come si ricorderà, ogni autovalore $\lambda$ di un operatore unitario ha una grandezza $|\lambda| = 1$. Quindi possiamo scrivere ogni autovalore come un numero complesso di magnitudine uno:

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

dove $\theta$ è un numero reale compreso tra 0 e 1. Per maggiori informazioni sulle matrici unitarie, consultare la lezione di John Watrous sull'argomento in Fondamenti dell'informazione quantistica.

Si noti che $\lambda$ è periodico in $\theta$. Già questo potrebbe far pensare a una QFT, visto che abbiamo visto quanto siano utili le QFT per analizzare le funzioni periodiche. Di seguito illustreremo l'algoritmo e vedremo come entra in gioco la QFT.

Come funziona QPE

Per prima cosa, inizieremo con l'algoritmo QPE più semplice, che stima approssimativamente la fase con una singola cifra binaria di precisione. In altre parole, questo algoritmo può distinguere tra $\theta = 0$ e $\theta = 1/2$, ma non può fare di meglio. Ecco lo schema del circuito:

I qubit sono 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 cancello successivo è un cancello "controllato $U$ ". Questo applica l'operazione unitaria $U$ ai qubit inferiori che sono 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 controllato $U$ utilizza solo il qubit $0$ come qubit di controllo, per cui si potrebbe pensare che questo gate non cambi affatto lo stato del qubit 0. Ma in qualche modo, lo fa! Anche se l'operazione è stata applicata ai qubit inferiori, l'effetto complessivo del gate è quello di cambiare la fase del qubit $0$. Questo meccanismo è noto come "meccanismo di contraccolpo di fase" ed è utilizzato in molti algoritmi quantistici, tra cui gli algoritmi di Deutsch-Josza e Grover. Se volete saperne di più sul meccanismo phase-kickback, consultate la lezione di John Watrous sugli algoritmi di interrogazione quantistica in Fundamentals of quantum algorithms.

Dopo il phase-kickback, applichiamo un'altra Hadamard al qubit $0$, che dà come risultato lo 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 alla fine misuriamo il qubit $0$, misureremo $|0\rangle$ con il 100% di certezza se $\theta = 0$ e misureremo $|1\rangle$ con il 100% di certezza se $\theta = \frac{1}{2}$ (e se il nostro computer quantistico è perfetto, senza rumore). Se $\theta$ è qualcosa di diverso da questo, la misura finale è solo probabilistica e ci dice solo molto.

QPE con maggiore precisione: più qubit

Possiamo estendere questo semplice concetto a un algoritmo più complicato con precisione arbitraria. Se invece di utilizzare solo il qubit $0$ per misurare la fase, utilizziamo $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 inizia come la versione a singolo bit: Hadamard viene applicato 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 unità controllate. Qubit $0$ è il controllo per lo stesso $U$ unitario di prima. Ma ora il qubit $1$ è il controllo dell'unitario $U^2$, che è semplicemente $U$ applicato 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 dell'unitario $U^{2^k}$. Ciò significa che ognuno di questi qubit subirà un contraccolpo di fase di $e^{2^k*2\pi i \theta}$. Questo risulta nello 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 degli 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 vi sembra familiare? È un QFT! Ricordiamo l'equazione di una trasformata di Fourier quantistica:

$\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$ tra $0$ e $2^m-1$, allora prendendo la QFT inversa di questo stato si otterrà lo stato:

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

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

Se $\theta/2^m$ non è un multiplo di un intero, tuttavia, la QFT inversa approssimerà solo $\theta$. Il grado di approssimazione di $\theta$ sarà probabilistico, il che significa che non otterremo sempre l'approssimazione migliore, ma sarà piuttosto vicina, e più qubit $m$ si usano, migliore sarà l'approssimazione ottenuta. Per sapere come quantificare questa approssimazione di $\theta$, consultate la lezione di John Watrous sulla stima della fase e la fattorizzazione in Fundamentals of quantum algorithms.

Conclusione

Questo modulo ha fornito una panoramica di cos'è una QFT, di come viene implementata su un computer quantistico e di come può essere utile per risolvere i problemi. Abbiamo avuto un assaggio della sua utilità quando abbiamo visto come può essere utilizzato nella stima quantistica di fase per conoscere gli autovalori di una matrice unitaria.

Concetti fondamentali

• La trasformata di Fourier quantistica è l'analogo quantistico della trasformata di Fourier discreta.
• La QFT è un esempio di trasformazione di basi.
• La procedura di stima della fase quantistica si basa sul meccanismo di phase-kickback delle operazioni controllate-unitarie e su una QFT inversa.
• QFT e QPE sono entrambe subroutine ampiamente utilizzate in numerosi algoritmi quantistici.

Domande

True/False

1. T/F La trasformata quantistica di Fourier è l'analogo quantistico della trasformata discreta di Fourier (DFT) classica.
2. La QFT T/F può essere implementata utilizzando solo porte Hadamard e CNOT.
3. T/F La QFT è una componente chiave dell'algoritmo di Shor.
4. T/F L'uscita della stima di fase quantistica è uno stato quantistico che rappresenta l'autovettore dell'operatore.
5. T/F QPE richiede l'uso della Trasformata Quantistica di Fourier inversa (QFT $^\dag$ ).
6. T/F In 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 utilizzata su uno stato che non è uno stato base computazionale? Se sì, cosa succede?
3. In che modo il numero di qubit di controllo utilizzati nel QPE influisce sulla risoluzione della stima di fase risultante?

Problemi

1. Utilizzare la moltiplicazione matriciale per verificare che i passaggi dell'algoritmo QFT diano effettivamente come risultato la matrice $\text{QFT}_4$ :

(Non è necessario farlo a mano)

Problemi di sfida

1. Creare 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$. Quindi eseguire una QFT sullo stato. Qual è lo stato risultante? Spiegate perché il vostro risultato ha senso, utilizzando le vostre conoscenze sulle trasformate di Fourier.