La trasformata di Fourier quantistica è esponenzialmente più veloce di una trasformata classica? Ed è per questo che può rendere risolvibili problemi difficili con un computer quantistico?

/ / Pubblicato in Informazioni quantistiche, Fondamenti di informazione quantistica EITC/QI/QIF, Trasformata quantistica di Fourier, Proprietà della trasformata quantistica di Fourier

La trasformata di Fourier quantistica (QFT) occupa un ruolo centrale nella teoria dell'informazione quantistica e nel calcolo quantistico. La sua progettazione e implementazione hanno profonde implicazioni per l'efficienza degli algoritmi quantistici, in particolare in problemi in cui si ritiene che gli approcci classici siano inefficienti. Per stabilire se la QFT sia esponenzialmente più veloce della sua controparte classica e se questo sia alla base del vantaggio quantistico nella risoluzione di alcuni problemi computazionalmente complessi, è essenziale esaminare sia la struttura matematica che la complessità computazionale della QFT e confrontarle con gli algoritmi classici più noti.

## La trasformata di Fourier discreta classica (DFT)

La trasformata di Fourier discreta classica (DFT) è un'operazione matematica che mappa un vettore di numeri complessi su un altro vettore della stessa dimensione, che rappresenta le componenti di frequenza del vettore originale. La DFT di un Nvettore -dimensionale x = (x_0, x_1, ..., x_{N-1}) è dato da:

    \[ \tilde{x}_k = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} x_j e^{2\pi i jk/N}, \quad k = 0, 1, ..., N-1 \]

L'implementazione ingenua del DFT richiede O(N^2) tempo perché ogni elemento di output comporta una somma su tutti N elementi di input, e ci sono N uscite.

Tuttavia, la trasformata di Fourier veloce (FFT), un algoritmo classico, riduce questa complessità a O(N \log N) scomponendo ricorsivamente la DFT in DFT più piccole. La FFT è uno degli algoritmi più celebrati nella scienza computazionale, alla base di applicazioni che vanno dall'elaborazione dei segnali all'analisi numerica.

## La trasformata di Fourier quantistica (QFT): definizione e complessità del circuito

La trasformata di Fourier quantistica è l'analogo quantistico della DFT classica, che agisce sugli stati quantistici. Per un n-sistema qubit, dove N = 2^n, la QFT è l'operatore lineare definito da:

    \[ |x\rangle \mapsto \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} e^{2\pi i xk/N} |k\rangle \]

per x in 0, 1, ..., N-1.

L'implementazione della QFT come circuito quantistico è particolarmente efficiente. Può essere scomposta in una sequenza di porte di Hadamard e porte a sfasamento controllato. La profondità e le dimensioni del circuito sono entrambe O (n ^ 2), Cioè, O((\log N)^2)Durante la serata, n è il numero di qubit e N = 2^n è la dimensione dello spazio di Hilbert.

Descrizione dettagliata del circuito

Per un n-registro qubit, il circuito QFT è in genere costituito da:

1. Una porta di Hadamard sul qubit più significativo.
2. Spostamenti di fase controllati tra il qubit più significativo e ciascun qubit meno significativo, con fase e^{2\pi i/2^k} per l' kcontrollo.
3. Ricorsione sul rimanente n-1 qubit.
4. Un'inversione finale dell'ordine dei qubit (porte di scambio).

Il conteggio totale delle porte per un QFT esatto è O (n ^ 2)Tuttavia, se un piccolo errore è tollerabile (che è spesso sufficiente per gli algoritmi quantistici), è possibile approssimare la QFT con precisione \epsilon utilizzando solo O(n \log n + \log n \log(1/\epsilon)) cancelli, riducendo ulteriormente il fabbisogno di risorse.

Confronto della complessità computazionale

- FFT classica: O(N \log N) = O(2^nn)
- QFT quantistica: O (n ^ 2) cancelli

Traducendo queste complessità nelle stesse unità, la QFT opera in O(\log^2 N) porte quantistiche, mentre la FFT richiede O(N \log N) operazioni classiche. Si tratta di un miglioramento esponenziale nel numero di operazioni di base richieste, almeno in relazione alla dimensione dell'input misurata in bit (n = \log N).

## La QFT da sola è esponenzialmente più veloce?

Sebbene la QFT possa essere implementata esponenzialmente più velocemente della FFT classica quando si misurano le risorse in base al numero di porte quantistiche di base rispetto alle operazioni classiche, è importante analizzare cosa ciò significhi per il calcolo pratico. L'accelerazione esponenziale si riferisce alla complessità del circuito interno: la QFT mappa un'intera sovrapposizione di N ampiezze utilizzando solo O (n ^ 2) porte. Tuttavia, la misurazione quantistica riduce lo stato quantistico a un singolo risultato, limitando l'estrazione diretta di tutte le ampiezze di output.

Se uno è interessato a calcolare tutto N ampiezze di output di una QFT, questa non sarebbe più veloce su un computer quantistico perché è possibile osservare un solo risultato di misurazione per ogni esecuzione e ricostruire l'intero spettro richiederebbe un numero esponenzialmente elevato di ripetizioni. Pertanto, l'accelerazione esponenziale non risiede nel calcolo di *tutti* i valori di output, ma nella trasformazione delle informazioni quantistiche all'interno di un algoritmo quantistico.

## Il ruolo della QFT negli algoritmi quantistici

La QFT è una subroutine chiave in diversi algoritmi quantistici che forniscono accelerazioni esponenziali o superpolinomiali rispetto ai più noti algoritmi classici. L'esempio più importante è l'algoritmo di Shor per la fattorizzazione degli interi.

Algoritmo di Shor

L'algoritmo di Shor utilizza la teoria quantistica quantistica (QFT) per calcolare il periodo di una funzione (ricerca del periodo), che viene poi utilizzato per fattorizzare numeri interi grandi. L'algoritmo procede come segue:

1. Preparare una sovrapposizione uniforme su N stati.
2. Calcola una funzione f(x) = a^x \mod N in sovrapposizione.
3. Misurare il secondo registro, riducendo lo stato a una sovrapposizione di input che vengono tutti mappati sull'output misurato.
4. Applicare la QFT al primo registro, che trasforma la struttura periodica in una sovrapposizione in cui la misurazione fornisce informazioni sul periodo.
5. Utilizzare il risultato misurato e la post-elaborazione classica (frazioni continue) per recuperare il periodo e scomporre in fattori l'intero.

La QFT è esponenzialmente più veloce della FFT classica in termini di numero di operazioni di base per la trasformazione. Questa efficienza è *importante* per le prestazioni in tempo polinomiale dell'algoritmo di Shor.

Problemi di sottogruppi nascosti

La trasformata di Fourier quantistica è anche fondamentale per la classe dei problemi di sottogruppo nascosto (HSP), dove l'obiettivo è determinare un sottogruppo nascosto H di un gruppo G data una funzione che è costante sulle classi laterali di H e distinti su diversi lati laterali. Molti problemi di notevole interesse, come i logaritmi discreti e alcuni problemi di isomorfismo dei grafi, possono essere espressi in questa forma. La QFT consente l'estrazione della struttura dei sottogruppi dagli stati quantistici, consentendo soluzioni efficienti laddove gli algoritmi classici non sono praticabili.

## Limitazioni e idee sbagliate

È importante riconoscere le sottigliezze nell'affermazione secondo cui la QFT è esponenzialmente più veloce della FFT classica:

- Trasformazione efficiente, non campionamento efficiente: La QFT trasforma in modo efficiente lo stato quantistico, ma un computer quantistico non può restituire l'intero stato trasformato. La misurazione produce un campione dalla distribuzione di probabilità definita dalle ampiezze al quadrato. Per molte applicazioni, questo è sufficiente, poiché l'algoritmo quantistico è progettato per rendere elevata la probabilità di misurare una risposta utile.
- Ricostruzione dell'output classico: Se l'obiettivo è calcolare e produrre tutti N I coefficienti di Fourier sono classici, ma la QFT non è di aiuto; è possibile ottenere solo un campione quantistico per ogni esecuzione. Pertanto, l'efficienza esponenziale della QFT è utile all'interno degli algoritmi quantistici, non per il calcolo classico diretto di tutti i valori di trasformata.
- Non tutti i problemi: La QFT di per sé non rende trattabili tutti i problemi classicamente difficili. La sua utilità è specifica per classi di problemi in cui la coerenza quantistica e l'interferenza, in combinazione con la QFT, consentono l'estrazione efficiente di proprietà globali (come il periodo).

## Esempio: Ricerca dell'ordine e periodicità

Consideriamo il problema della ricerca del periodo, che è alla base dell'algoritmo di Shor:

Supponiamo che venga data una funzione f: \mathbb{Z}_N \to S che è periodico con periodo r, Cioè, f(x) = f(x + r) per tutti xL'obiettivo è determinare r.

Classicamente, trovare r richiede O(\qrt{N}) valutazioni di f nel caso peggiore (per funzioni generali). Quantisticamente, il processo comporta:

1. Preparazione di una sovrapposizione uniforme \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} |x\rangle.
2. Informatica f (x) in sovrapposizione: \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} |x\rangle|f(x)\rangle.
3. La misurazione del secondo registro produce un valore y, aggrovigliando il primo registro al sottoinsieme di x con f(x) = y: \sum_{j} |x_0 + jr\rangle.
4. L'applicazione della QFT trasforma questo in una sovrapposizione con un picco netto a multipli di N/rMisurazione delle rese k così k/N approssima un numero razionale con denominatore r.
5. La post-elaborazione classica consente il recupero di r.

In questo caso, l'efficienza esponenziale della QFT è fondamentale: la trasformazione dalla periodicità nel dominio del tempo ai picchi nel dominio della frequenza viene realizzata con un numero polinomiale di porte quantistiche, mentre una ricerca classica richiederebbe un tempo esponenziale nel numero di bit di input.

## Trasformata di Fourier quantistica approssimativa

Nelle applicazioni pratiche, soprattutto con l'aumento del numero di qubit, è spesso sufficiente utilizzare una QFT approssimativa. Omettendo le porte a fase controllata con angoli molto piccoli, la QFT può essere implementata con un numero significativamente inferiore di porte, mantenendo al contempo un'elevata fedeltà. Ciò è particolarmente utile per i dispositivi NISQ (Noisy Intermediate-Scale Quantum), in cui la riduzione del numero di porte contribuisce a mitigare gli effetti del rumore e della decoerenza.

## Ulteriori implicazioni

L'impatto della QFT si estende oltre gli algoritmi specifici già menzionati. Nella stima di fase quantistica, una subroutine fondamentale per gli algoritmi che risolvono problemi come la stima degli autovalori per le hamiltoniane, la QFT è ancora una volta un elemento chiave. L'algoritmo utilizza la QFT per estrarre informazioni di fase codificate nelle ampiezze di uno stato quantistico, consentendo la stima degli autovalori esponenzialmente più veloce di quanto le controparti classiche possano ottenere per determinati problemi.

Inoltre, la QFT è fondamentalmente legata alla struttura dell'elaborazione delle informazioni quantistiche, sottolineando la capacità degli algoritmi quantistici di sfruttare proprietà globali e simmetrie inaccessibili al calcolo classico. Ciò è particolarmente evidente nella chimica quantistica e negli algoritmi di simulazione, dove la QFT viene utilizzata per passare in modo efficiente dalla rappresentazione della posizione a quella della quantità di moto.

## Osservazioni conclusive

La trasformata di Fourier quantistica è esponenzialmente più efficiente della trasformata di Fourier veloce classica in termini di numero di porte quantistiche richieste rispetto alla dimensione dell'input espressa in qubit. Questa efficienza, tuttavia, è significativa nel contesto degli algoritmi quantistici, dove la QFT consente l'estrazione di proprietà periodiche globali dagli stati quantistici utilizzando un numero di passi polinomiale rispetto al numero di qubit. Sebbene la QFT non consenta il calcolo efficiente di tutte le ampiezze di output come una lista classica, il suo ruolo all'interno degli algoritmi quantistici è quello di manipolare e rivelare in modo efficiente la struttura dell'informazione quantistica, portando ad accelerazioni quantistiche esponenziali o superpolinomiali in problemi come la fattorizzazione e l'identificazione di sottogruppi nascosti.

Altre domande e risposte recenti riguardanti Fondamenti di informazione quantistica EITC/QI/QIF:

Visualizza altre domande e risposte in EITC/QI/QIF Quantum Information Fundamentals

Altre domande e risposte:

Etichettato sotto: , , , , ,