{
"cells": [
{
"cell_type": "markdown",
"id": "b4addac2",
"metadata": {},
"source": [
"---\n",
"title: \"La procedura di stima della fase\"\n",
"description: \"Corso gratuito \\\" IBM \\\" sull'informazione e il calcolo quantistico\"\n",
"---\n",
"\n",
"{/* cspell:ignore mapsto */}\n",
"\n",
"\n",
"\n",
"# Procedura di stima della fase\n",
"\n",
"Successivamente, discuteremo la *procedura di stima della fase*, che è un algoritmo quantistico per risolvere il problema della stima della fase.\n",
"\n",
"Inizieremo con un riscaldamento a bassa precisione, che spiega alcune delle intuizioni di base del metodo.\n",
"Parleremo poi della *trasformata di Fourier quantistica*, un'importante operazione quantistica utilizzata nella procedura di stima di fase, e della sua implementazione nei circuiti quantistici.\n",
"Una volta ottenuta la trasformata di Fourier quantistica, descriveremo la procedura di stima della fase in tutta la sua generalità e ne analizzeremo le prestazioni.\n",
"\n",
"\n",
"\n",
"## Riscaldamento: approssimazione delle fasi con bassa precisione\n",
"\n",
"Inizieremo con un paio di versioni semplici della procedura di stima della fase che forniscono soluzioni di bassa precisione al problema della stima della fase.\n",
"Questo è utile per spiegare l'intuizione alla base della procedura generale che vedremo più avanti nella lezione.\n",
"\n",
"\n",
"\n",
"### Utilizzo del contraccolpo di fase\n",
"\n",
"Un approccio semplice al problema della stima della fase, che ci permette di imparare qualcosa sul valore $\\theta$ che cerchiamo, si basa sul fenomeno del *kick-back di fase*.\n",
"Come vedremo, si tratta essenzialmente di una versione a un solo qubit della procedura generale di stima della fase che verrà discussa più avanti nella lezione.\n",
"\n",
"Come parte dell'input per il problema di stima di fase, abbiamo un circuito quantistico unitario per l'operazione $U$ . Possiamo usare la descrizione di questo circuito per creare un circuito per un'operazione *controllata* - $U$ , che può essere rappresentata come suggerisce questa figura (con l'operazione $U$ , vista come una porta quantistica, a sinistra e un'operazione controllata $U$ a destra).\n",
"\n",
"\n",
"\n",
"Possiamo creare un circuito quantistico per un’operazione di tipo “controlled- $U$ ” aggiungendo innanzitutto un qubit di controllo al circuito per $U$, e poi sostituendo ogni gate del circuito per $U$ con una versione controllata di quel gate — in modo che il nostro unico nuovo qubit di controllo controlli effettivamente ogni singolo gate del circuito per $U$.\n",
"Ciò richiede che disponiamo di una versione controllata di ogni gate del nostro circuito, ma possiamo sempre costruire circuiti per queste operazioni controllate nel caso in cui non siano incluse nel nostro insieme di gate.\n",
"\n",
"Consideriamo ora il seguente circuito, in cui lo stato di ingresso $\\vert\\psi\\rangle$ di tutti i qubit tranne quello in cima è l'autovettore dello stato quantistico di $U$.\n",
"\n",
"\n",
"\n",
"Le probabilità dei risultati di misura per questo circuito dipendono dall'autovalore di $U$ corrispondente all'autovettore $\\vert\\psi\\rangle$.\n",
"Analizziamo il circuito in dettaglio per capire esattamente in che modo.\n",
"\n",
"\n",
"\n",
"Lo stato iniziale del circuito è\n",
"\n",
"$$\n",
"\\vert\\pi_0\\rangle = \\vert\\psi\\rangle \\vert 0\\rangle\n",
"$$\n",
"\n",
"e la prima porta di Hadamard trasforma questo stato in\n",
"\n",
"$$\n",
"\\vert\\pi_1\\rangle = \\vert\\psi\\rangle \\vert +\\rangle\n",
"= \\frac{1}{\\sqrt{2}} \\vert\\psi\\rangle \\vert 0\\rangle + \\frac{1}{\\sqrt{2}} \\vert\\psi\\rangle \\vert 1\\rangle.\n",
"$$\n",
"\n",
"Successivamente, viene eseguita l'operazione controllata $U$, che dà come risultato lo stato\n",
"\n",
"$$\n",
"\\vert\\pi_2\\rangle\n",
"= \\frac{1}{\\sqrt{2}} \\vert\\psi\\rangle \\vert 0\\rangle + \\frac{1}{\\sqrt{2}} \\bigl(U \\vert\\psi\\rangle\\bigr) \\vert 1\\rangle.\n",
"$$\n",
"\n",
"Partendo dal presupposto che $\\vert\\psi\\rangle$ sia un vettore proprio di $U$ con autovalore $\\lambda = e^{2\\pi i\\theta}$,\n",
"possiamo esprimere questo stato in alternativa come segue.\n",
"\n",
"$$\n",
"\\vert\\pi_2\\rangle\n",
"= \\frac{1}{\\sqrt{2}} \\vert\\psi\\rangle \\vert 0\\rangle + \\frac{e^{2\\pi i \\theta}}{\\sqrt{2}} \\vert\\psi\\rangle \\vert 1\\rangle = \\vert\\psi\\rangle \\otimes \\left( \\frac{1}{\\sqrt{2}} \\vert 0\\rangle + \\frac{e^{2\\pi i \\theta}}{\\sqrt{2}} \\vert 1\\rangle\\right)\n",
"$$\n",
"\n",
"Qui si osserva il fenomeno del contraccolpo di fase.\n",
"Questa volta è leggermente diverso rispetto all'algoritmo di Deutsch e all'algoritmo di Deutsch-Jozsa, perché non stiamo lavorando con un query gate, ma l'idea è simile.\n",
"\n",
"Infine, viene eseguito il secondo gate di Hadamard. Dopo una piccola semplificazione, otteniamo questa espressione per questo stato.\n",
"\n",
"$$\n",
"\\vert\\pi_3\\rangle\n",
"= \\vert\\psi\\rangle \\otimes \\left( \\frac{1+ e^{2\\pi i \\theta}}{2} \\vert 0\\rangle + \\frac{1 - e^{2\\pi i \\theta}}{2} \\vert 1\\rangle\\right)\n",
"$$\n",
"\n",
"La misurazione produce quindi i risultati $0$ e $1$ con queste probabilità:\n",
"\n",
"$$\n",
"\\begin{aligned}\n",
"p_0 &= \\left\\vert \\frac{1+ e^{2\\pi i \\theta}}{2} \\right\\vert^2 = \\cos^2(\\pi\\theta)\\\\[1mm]\n",
"p_1 &= \\left\\vert \\frac{1- e^{2\\pi i \\theta}}{2} \\right\\vert^2 = \\sin^2(\\pi\\theta).\n",
"\\end{aligned}\n",
"$$\n",
"\n",
"Ecco un grafico delle probabilità relative ai due possibili esiti, $0$ e $1$, in funzione di $\\theta$.\n",
"\n",
"\n",
"\n",
"Naturalmente, la somma delle due probabilità è sempre pari a $1$.\n",
"Si noti che quando $\\theta = 0$, il risultato della misurazione è sempre $0$, e quando $\\theta = 1/2$, il risultato della misurazione è sempre $1$.\n",
"Quindi, sebbene il risultato della misurazione non riveli esattamente quale sia $\\theta$, ci fornisce comunque alcune informazioni al riguardo — e se ci venisse garantito che vale $\\theta = 0$ oppure $\\theta = 1/2$, potremmo dedurre dal circuito quale delle due affermazioni sia corretta senza commettere errori.\n",
"\n",
"Intuitivamente, si può pensare che il risultato della misurazione del circuito sia un'ipotesi per $\\theta$ con \"un bit di precisione\"\n",
"In altre parole, se scrivessimo $\\theta$ in notazione binaria e lo arrotondassimo a un bit, avremmo un numero come questo:\n",
"\n",
"$$\n",
"0.a = \\begin{cases}\n",
"0 & a = 0\\\\\n",
"\\frac{1}{2} & a = 1.\n",
"\\end{cases}\n",
"$$\n",
"\n",
"Il risultato della misurazione può essere considerato come un'ipotesi relativa al bit $a$.\n",
"Quando $\\theta$ non è né $0$ né $1/2$, esiste una probabilità diversa da zero che l'ipotesi sia errata — ma la\n",
"probabilità di commettere un errore diventa sempre più piccola man mano che ci avviciniamo a $0$ o $1/2$.\n",
"\n",
"È naturale chiedersi quale sia il ruolo delle due porte di Hadamard in questa procedura:\n",
"\n",
"* La prima porta di Hadamard imposta il qubit di controllo su una sovrapposizione uniforme di $\\vert 0\\rangle$ e $\\vert 1\\rangle$, in modo che, quando si verifica il kickback di fase, questo avvenga per lo stato $\\vert 1\\rangle$ e non per lo stato $\\vert 0\\rangle$, creando una differenza di fase *relativa* che influenza i risultati della misurazione. Se non lo facessimo e il contraccolpo di fase producesse una fase *globale*, ciò non avrebbe alcun effetto sulle probabilità di ottenere esiti di misura diversi.\n",
"\n",
"* La seconda porta di Hadamard ci permette di imparare qualcosa sul numero $\\theta$ attraverso il fenomeno dell' *interferenza*. Prima del secondo cancello di Hadamard, lo stato del qubit superiore è\n",
"\n",
"$$\n",
"\\frac{1}{\\sqrt{2}} \\vert 0\\rangle + \\frac{e^{2\\pi i \\theta}}{\\sqrt{2}} \\vert 1\\rangle,\n",
"$$\n",
"\n",
"e se dovessimo misurare questo stato, otterremmo $0$ e $1$, ciascuno con probabilità $1/2$, senza che ciò ci fornisca alcuna informazione su $\\theta$. Eseguendo il secondo gate di Hadamard, tuttavia, facciamo sì che il numero $\\theta$ influenzi le probabilità di uscita.\n",
"\n",
"\n",
"\n",
"### Raddoppiare la fase\n",
"\n",
"Il circuito di cui sopra utilizza il fenomeno del contraccolpo di fase per approssimare $\\theta$ con una precisione di un singolo bit.\n",
"In alcune situazioni può essere sufficiente un po' di precisione, ma per il factoring avremo bisogno di molta più precisione.\n",
"Una domanda naturale è: come possiamo imparare di più su $\\theta?$\n",
"\n",
"Una cosa molto semplice da fare è sostituire l'operazione controllata $U$ nel nostro circuito con *due copie* di questa operazione, come in questo circuito:\n",
"\n",
"\n",
"\n",
"Due copie di un'operazione di tipo \"controlled- $U$ \" equivalgono a un'operazione di tipo \"controlled- $U^2$ \".\n",
"Se $\\vert\\psi\\rangle$ è un vettore proprio di $U$ con autovalore $\\lambda = e^{2\\pi i \\theta}$, allora questo stato è anche un vettore proprio di $U^2$, questa volta con autovalore $\\lambda^2 = e^{2\\pi i (2\\theta)}$.\n",
"\n",
"Quindi, se eseguiamo questa versione del circuito, stiamo effettivamente effettuando lo stesso calcolo di prima, con la sola differenza che il numero $\\theta$ viene sostituito da $2\\theta$.\n",
"Ecco un grafico che illustra le probabilità di uscita man mano c $\\theta$ varia da $0$ a $1$.\n",
"\n",
"\n",
"\n",
"In questo modo possiamo infatti ottenere alcune informazioni aggiuntive su $\\theta$.\n",
"Se la rappresentazione binaria di $\\theta$ è\n",
"\n",
"$$\n",
"\\theta = 0.a_1 a_2 a_3\\cdots\n",
"$$\n",
"\n",
"allora il raddoppio di $\\theta$ sposta effettivamente il punto binario di una posizione a destra:\n",
"\n",
"$$\n",
"2\\theta = a_1. a_2 a_3\\cdots\n",
"$$\n",
"\n",
"E poiché, muovendoci lungo il cerchio unitario, equipariamo $\\theta = 1$ a $\\theta = 0$, vediamo che il bit $a_1$ non influisce sulle nostre probabilità e, arrotondando $\\theta$ a due bit, otteniamo di fatto una stima del *secondo* bit dopo la virgola binaria.\n",
"Ad esempio, se sapessimo in anticipo che $\\theta$ è o $0$ o $1/4$, potremmo fidarci ciecamente del risultato della misurazione per capire quale dei due sia.\n",
"\n",
"Non è però immediatamente chiaro come questa stima debba essere conciliata con quanto abbiamo appreso dal circuito originale (non raddoppiato) di kickback di fase, in modo da ottenere informazioni il più accurate possibile sull' $\\theta$ e.\n",
"Facciamo quindi un passo indietro e valutiamo come procedere.\n",
"\n",
"\n",
"\n",
"### Stima di fase a due qubit\n",
"\n",
"Invece di considerare le due opzioni descritte sopra separatamente, combiniamole in un unico circuito in questo modo.\n",
"\n",
"\n",
"\n",
"Le porte di Hadamard, dopo che le operazioni controllate sono state rimosse, e qui non ci sono ancora misurazioni.\n",
"Aggiungeremo altri elementi al percorso man mano che valuteremo le varie opzioni per approfondire il più possibile la nostra conoscenza di “ $\\theta$ ”.\n",
"\n",
"Se eseguiamo questo circuito quando $\\vert\\psi\\rangle$ è un vettore proprio di $U$, lo stato dei qubit inferiori rimarrà $\\vert\\psi\\rangle$ per tutta la durata del circuito, e le fasi verranno \"spinte\" nello stato dei due qubit superiori.\n",
"Analizziamo attentamente il circuito, con l'ausilio della figura seguente.\n",
"\n",
"\n",
"\n",
"Possiamo scrivere lo stato $\\vert\\pi_1\\rangle$ in questo modo:\n",
"\n",
"$$\n",
"\\vert\\pi_1\\rangle = \\vert \\psi\\rangle \\otimes \\frac{1}{2} \\sum_{a_0 = 0}^1 \\sum_{a_1 = 0}^1 \\vert a_1 a_0 \\rangle.\n",
"$$\n",
"\n",
"Quando viene eseguita la prima operazione controllata $U$, l’autovalore $\\lambda = e^{2\\pi i\\theta}$ viene spinto nella fase in cui $a_0$ (il qubit superiore) è uguale a $1$, ma non quando è $0$.\n",
"Pertanto, possiamo esprimere lo stato risultante in questo modo:\n",
"\n",
"$$\n",
"\\vert\\pi_2\\rangle\n",
"= \\vert\\psi\\rangle \\otimes \\frac{1}{2} \\sum_{a_0=0}^1 \\sum_{a_1=0}^1 e^{2 \\pi i a_0 \\theta} \\vert a_1 a_0 \\rangle.\n",
"$$\n",
"\n",
"Il secondo e il terzo gate controllato $U$ funzionano in modo simile, tranne per il fatto che $a_1$ sostituisce $a_0$ e $\\theta$ viene sostituito da $2\\theta$.\n",
"Possiamo esprimere lo stato risultante in questo modo:\n",
"\n",
"$$\n",
"\\vert\\pi_3\\rangle\n",
"= \\vert\\psi\\rangle\\otimes\\frac{1}{2}\\sum_{a_0 = 0}^1 \\sum_{a_1 = 0}^1\n",
"e^{2\\pi i (2 a_1 + a_0)\\theta} \\vert a_1 a_0 \\rangle.\n",
"$$\n",
"\n",
"Se consideriamo la stringa binaria $a_1 a_0$ come rappresentazione di un numero intero $x \\in \\{0,1,2,3\\}$ in notazione binaria, ovvero $x = 2 a_1 + a_0$, possiamo esprimere questo stato anche nel modo seguente.\n",
"\n",
"$$\n",
"\\vert\\pi_3\\rangle = \\vert \\psi\\rangle \\otimes \\frac{1}{2} \\sum_{x = 0}^3 e^{2\\pi i x \\theta} \\vert x \\rangle\n",
"$$\n",
"\n",
"Il nostro obiettivo è estrarre da questo stato quante più informazioni possibili su $\\theta$.\n",
"\n",
"A questo punto prenderemo in esame un caso particolare, in cui ci viene garantito che $\\theta = \\frac{y}{4}$ per un certo numero intero $y\\in\\{0,1,2,3\\}$.\n",
"In altre parole, abbiamo $\\theta\\in \\{0, 1/4, 1/2, 3/4\\}$, quindi possiamo esprimere questo numero in modo esatto utilizzando la notazione binaria a due bit come. $00$,. $01$,. $10$, oppure. $11$.\n",
"In generale, $\\theta$ potrebbe non essere uno di questi quattro valori, ma riflettere su questo caso particolare ci aiuterà a capire come estrarre nel modo più efficace le informazioni relative a $\\theta$ in generale.\n",
"\n",
"Per prima cosa definiremo un vettore di stato a due qubit per ciascun valore possibile di $y \\in \\{0, 1, 2, 3\\}$.\n",
"\n",
"$$\n",
"\\vert \\phi_y\\rangle = \\frac{1}{2} \\sum_{x = 0}^3 e^{2\\pi i x (\\frac{y}{4})} \\vert x \\rangle\n",
"= \\frac{1}{2} \\sum_{x = 0}^3 e^{2\\pi i \\frac{x y}{4}} \\vert x \\rangle\n",
"$$\n",
"\n",
"Dopo aver semplificato gli esponenziali, possiamo scrivere questi vettori come segue.\n",
"\n",
"$$\n",
"\\begin{aligned}\n",
"\\vert\\phi_0\\rangle & = \\frac{1}{2} \\vert 0 \\rangle + \\frac{1}{2} \\vert 1 \\rangle + \\frac{1}{2} \\vert 2 \\rangle + \\frac{1}{2} \\vert 3 \\rangle \\\\[3mm]\n",
"\\vert\\phi_1\\rangle & = \\frac{1}{2} \\vert 0 \\rangle + \\frac{i}{2} \\vert 1 \\rangle - \\frac{1}{2} \\vert 2 \\rangle - \\frac{i}{2} \\vert 3 \\rangle \\\\[3mm]\n",
"\\vert\\phi_2\\rangle & = \\frac{1}{2} \\vert 0 \\rangle - \\frac{1}{2} \\vert 1 \\rangle + \\frac{1}{2} \\vert 2 \\rangle - \\frac{1}{2} \\vert 3 \\rangle \\\\[3mm]\n",
"\\vert\\phi_3\\rangle & = \\frac{1}{2} \\vert 0 \\rangle - \\frac{i}{2} \\vert 1 \\rangle - \\frac{1}{2} \\vert 2 \\rangle + \\frac{i}{2} \\vert 3 \\rangle\n",
"\\end{aligned}\n",
"$$\n",
"\n",
"Questi vettori sono ortogonali: se ne scegliamo una coppia qualsiasi e calcoliamo il loro prodotto scalare, otteniamo $0$.\n",
"Ciascuno di essi è inoltre un vettore unitario, quindi $\\{\\vert\\phi_0\\rangle, \\vert\\phi_1\\rangle, \\vert\\phi_2\\rangle, \\vert\\phi_3\\rangle\\}$ costituisce una base ortonormale.\n",
"Sappiamo quindi fin da subito che esiste una misura in grado di distinguerli perfettamente — il che significa che, se ci viene presentato uno dei due senza che sappiamo quale, possiamo individuarne l'identità senza commettere errori.\n",
"\n",
"Per eseguire una tale discriminazione con un circuito quantistico, possiamo innanzitutto definire un'operazione unitaria $V$ che trasforma gli stati base standard nei quattro stati sopra elencati.\n",
"\n",
"$$\n",
"\\begin{aligned}\n",
"V \\vert 00 \\rangle & = \\vert\\phi_0\\rangle \\\\\n",
"V \\vert 01 \\rangle & = \\vert\\phi_1\\rangle \\\\\n",
"V \\vert 10 \\rangle & = \\vert\\phi_2\\rangle \\\\\n",
"V \\vert 11 \\rangle & = \\vert\\phi_3\\rangle\n",
"\\end{aligned}\n",
"$$\n",
"\n",
"Per rappresentare $V$ come una matrice di tipo $4\\times 4$, basta considerare le colonne di $V$ come gli stati $\\vert\\phi_0\\rangle,\\ldots,\\vert\\phi_3\\rangle$.\n",
"\n",
"$$\n",
"V =\n",
"\\frac{1}{2}\n",
"\\begin{pmatrix}\n",
"1 & 1 & 1 & 1\\\\[1mm]\n",
"1 & i & -1 & -i\\\\[1mm]\n",
"1 & -1 & 1 & -1\\\\[1mm]\n",
"1 & -i & -1 & i\n",
"\\end{pmatrix}\n",
"$$\n",
"\n",
"Si tratta di una matrice speciale, e probabilmente alcuni lettori l'avranno già incontrata in precedenza:\n",
"è la matrice associata alla *trasformata di Fourier discreta* di $4$ -dimensioni.\n",
"Alla luce di ciò, chiamiamola “ $\\mathrm{QFT}_4$ ” anziché “ $V$ ”.\n",
"Il nome “ $\\mathrm{QFT}$ ” è l’abbreviazione di *“quantum Fourier transform”* — che in sostanza non è altro che la trasformata di Fourier discreta, considerata come un’operazione unitaria.\n",
"Tra poco approfondiremo la trasformata di Fourier quantistica in modo più dettagliato e generale.\n",
"\n",
"$$\n",
"\\mathrm{QFT}_4 =\n",
"\\frac{1}{2}\n",
"\\begin{pmatrix}\n",
"1 & 1 & 1 & 1\\\\[1mm]\n",
"1 & i & -1 & -i\\\\[1mm]\n",
"1 & -1 & 1 & -1\\\\[1mm]\n",
"1 & -i & -1 & i\n",
"\\end{pmatrix}\n",
"$$\n",
"\n",
"Possiamo eseguire l'inversa di questa operazione per procedere in senso inverso, ovvero per trasformare gli stati $\\vert\\phi_0\\rangle,\\ldots,\\vert\\phi_3\\rangle$ negli stati della base standard $\\vert 0\\rangle,\\ldots,\\vert 3\\rangle$.\n",
"Se lo facciamo, possiamo effettuare una misurazione per determinare quale valore $y\\in\\{0,1,2,3\\}$ descriva $\\theta$ come $\\theta = y/4$.\n",
"Ecco un diagramma di un circuito quantistico che esegue questa operazione.\n",
"\n",
"\n",
"\n",
"Riassumendo, se si esegue questo circuito quando $\\theta = y/4$ per $y\\in\\{0,1,2,3\\}$, lo stato immediatamente precedente alle misurazioni sarà $\\vert \\psi\\rangle \\vert y\\rangle$ (per $y$ codificato come stringa binaria a due bit), quindi le misurazioni riveleranno il valore $y$ senza errori.\n",
"\n",
"Questo circuito nasce dal caso particolare in cui $\\theta \\in \\{0,1/4,1/2,3/4\\}$ — ma possiamo eseguirlo per qualsiasi scelta di $U$ e $\\vert \\psi\\rangle$, e quindi per qualsiasi valore di $\\theta$, a nostra discrezione.\n",
"Ecco un grafico delle probabilità di uscita generate dal circuito per scelte arbitrarie di $\\theta$.\n",
"\n",
"\n",
"\n",
"Si tratta di un netto miglioramento rispetto alla variante a singolo qubit descritta in precedenza in questa lezione.\n",
"Non è perfetto — può darci la risposta sbagliata — ma la risposta è fortemente sbilanciata verso i valori di $y$ per i quali $y/4$ è vicino a $\\theta$.\n",
"In particolare, il risultato più probabile corrisponde sempre al valore di $y/4$ più vicino a $\\theta$ (equiparando $\\theta = 0$ e $\\theta = 1$ come in precedenza), e dal grafico sembra che questo valore più vicino per $x$ compaia sempre con una probabilità appena superiore a $40\\%$.\n",
"Quando $\\theta$ si trova esattamente a metà strada tra due di questi valori, come ad esempio $\\theta = 0.375$, i due valori ugualmente vicini di $y$ hanno la stessa probabilità.\n",
"\n",
"\n",
"\n",
"### Preparazione alla generalizzazione a molti qubit\n",
"\n",
"Dato il miglioramento appena ottenuto utilizzando due qubit di controllo anziché uno, insieme all'inverso della trasformata di Fourier quantistica $4$ -dimensionale, è naturale pensare di generalizzarlo ulteriormente, aggiungendo altri qubit di controllo.\n",
"Facendo ciò, otteniamo la *procedura generale di stima della fase*.\n",
"Vedremo a breve come funziona, ma per descriverlo con precisione dovremo discutere la trasformata di Fourier quantistica in modo più generale, per vedere come viene definita per altre dimensioni e per vedere come possiamo implementarla (o la sua inversa) con un circuito quantistico.\n",
"\n",
"\n",
"\n",
"## Trasformata di Fourier quantistica\n",
"\n",
"La trasformata di Fourier quantistica è un’operazione unitaria che può essere definita per qualsiasi dimensione intera positiva $N$.\n",
"In questa sezione vedremo come viene definita questa operazione e come può essere implementata con un circuito quantistico su $m$ qubit con costo $O(m^2)$ quando $N = 2^m$.\n",
"\n",
"Le matrici che descrivono la trasformata di Fourier quantistica sono derivate da un'operazione analoga su vettori $N$ -dimensionali nota come *trasformata di Fourier discreta.*\n",
"Questa operazione può essere pensata in diversi modi.\n",
"Per esempio, possiamo pensare alla trasformata discreta di Fourier in termini puramente astratti e matematici come a una mappatura lineare.\n",
"Oppure possiamo pensarla in termini computazionali, dove ci viene dato un vettore $N$ -dimensionale di numeri complessi (usando la notazione binaria per codificare le parti reali e immaginarie delle voci, supponiamo) e l'obiettivo è calcolare il vettore $N$ -dimensionale ottenuto applicando la trasformata discreta di Fourier.\n",
"La nostra attenzione si concentrerà sulla terza via, che consiste nel considerare questa trasformazione come un'operazione unitaria che può essere eseguita su un sistema quantistico.\n",
"\n",
"Esiste un algoritmo efficiente per calcolare la trasformata di Fourier discreta su un dato vettore di ingresso, noto come *trasformata di Fourier veloce.*\n",
"Ha applicazioni nell'elaborazione dei segnali e in molte altre aree ed è considerato da molti uno degli algoritmi più importanti mai scoperti.\n",
"Come si è visto, l'implementazione della trasformata di Fourier quantistica quando $N$ è una potenza di 2 che studieremo si basa proprio sulla stessa struttura di base che rende possibile la trasformata di Fourier veloce.\n",
"\n",
"\n",
"\n",
"### Definizione della trasformata di Fourier quantistica\n",
"\n",
"Per definire la trasformata di Fourier quantistica, definiremo innanzitutto un numero complesso $\\omega_N$, per ogni numero intero positivo $N$, nel modo seguente:\n",
"\n",
"$$\n",
"\\omega_N = e^{\\frac{2\\pi i}{N}} = \\cos\\left(\\frac{2\\pi}{N}\\right) + i \\sin\\left(\\frac{2\\pi}{N}\\right).\n",
"$$\n",
"\n",
"È il numero sul cerchio complesso unitario che si ottiene partendo da $1$ e muovendosi in senso antiorario di un angolo di $2\\pi/N$ radianti, ovvero una frazione di $1/N$ della circonferenza del cerchio. Ecco alcuni esempi:\n",
"\n",
"$$\n",
"\\begin{gathered}\n",
"\\omega_1 = 1\\\\[1mm]\n",
"\\omega_2 = -1\\\\[1mm]\n",
"\\omega_3 = -\\frac{1}{2} + \\frac{\\sqrt{3}}{2} i\\\\[2mm]\n",
"\\omega_4 = i\\\\[1mm]\n",
"\\omega_8 = \\frac{1+i}{\\sqrt{2}}\\\\[3mm]\n",
"\\omega_{16} = \\frac{\\sqrt{2 + \\sqrt{2}}}{2} + \\frac{\\sqrt{2 - \\sqrt{2}}}{2} i\\\\[2mm]\n",
"\\omega_{100} \\approx 0.998 + 0.063 i\n",
"\\end{gathered}\n",
"$$\n",
"\n",
"Ora possiamo definire la trasformata di Fourier quantistica di dimensione $N$, descritta da una matrice $N\\times N$ le cui righe e colonne sono associate agli stati della base standard $\\vert 0\\rangle,\\ldots,\\vert N-1\\rangle$.\n",
"Avremo bisogno di questa operazione solo quando $N = 2^m$ è una potenza di $2$ per la stima della fase, ma l'operazione può essere definita per qualsiasi numero intero positivo $N$.\n",
"\n",
"$$\n",
"\\mathrm{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\n",
"$$\n",
"\n",
"Come già detto, si tratta della matrice associata alla *trasformata discreta di Fourier* $N$ -dimensionale.\n",
"Spesso il fattore primo di $1/\\sqrt{N}$ non è incluso nella definizione di questa matrice, ma è necessario includerlo per ottenere una matrice unitaria.\n",
"\n",
"Ecco la trasformata di Fourier quantistica, espressa sotto forma di matrice, per alcuni valori piccoli di $N$.\n",
"\n",
"$$\n",
"\\mathrm{QFT}_1 = \\begin{pmatrix} 1 \\end{pmatrix}\n",
"$$\n",
"\n",
"$$\n",
"\\mathrm{QFT}_2 =\n",
"\\frac{1}{\\sqrt{2}} \\begin{pmatrix} 1 & 1\\\\[1mm] 1 & -1 \\end{pmatrix}\n",
"$$\n",
"\n",
"$$\n",
"\\mathrm{QFT}_3 =\n",
"\\frac{1}{\\sqrt{3}}\n",
"\\begin{pmatrix}\n",
" 1 & 1 & 1\\\\[2mm]\n",
" 1 & \\frac{-1 + i\\sqrt{3}}{2} & \\frac{-1 - i\\sqrt{3}}{2}\\\\[2mm]\n",
" 1 & \\frac{-1 - i\\sqrt{3}}{2} & \\frac{-1 + i\\sqrt{3}}{2}\n",
"\\end{pmatrix}\n",
"$$\n",
"\n",
"$$\n",
"\\mathrm{QFT}_4 =\n",
"\\frac{1}{2}\n",
"\\begin{pmatrix}\n",
"1 & 1 & 1 & 1\\\\[1mm]\n",
"1 & i & -1 & -i\\\\[1mm]\n",
"1 & -1 & 1 & -1\\\\[1mm]\n",
"1 & -i & -1 & i\n",
"\\end{pmatrix}\n",
"$$\n",
"\n",
"$$\n",
"\\mathrm{QFT}_8 =\n",
"\\frac{1}{2\\sqrt{2}}\n",
"\\begin{pmatrix}\n",
" 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\\\[2mm]\n",
" 1 & \\frac{1+i}{\\sqrt{2}} & i & \\frac{-1+i}{\\sqrt{2}} & -1 & \\frac{-1-i}{\\sqrt{2}} & -i & \\frac{1-i}{\\sqrt{2}}\\\\[2mm]\n",
" 1 & i & -1 & -i & 1 & i & -1 & -i\\\\[2mm]\n",
" 1 & \\frac{-1+i}{\\sqrt{2}} & -i & \\frac{1+i}{\\sqrt{2}} & -1 & \\frac{1-i}{\\sqrt{2}} & i & \\frac{-1-i}{\\sqrt{2}}\\\\[2mm]\n",
" 1 & -1 & 1 & -1 & 1 & -1 & 1 & -1\\\\[2mm]\n",
" 1 & \\frac{-1-i}{\\sqrt{2}} & i & \\frac{1-i}{\\sqrt{2}} & -1 & \\frac{1+i}{\\sqrt{2}} & -i & \\frac{-1+i}{\\sqrt{2}}\\\\[2mm]\n",
" 1 & -i & -1 & i & 1 & -i & -1 & i\\\\[2mm]\n",
" 1 & \\frac{1-i}{\\sqrt{2}} & -i & \\frac{-1-i}{\\sqrt{2}} & -1 & \\frac{-1+i}{\\sqrt{2}} & i & \\frac{1+i}{\\sqrt{2}}\\\\[2mm]\n",
"\\end{pmatrix}\n",
"$$\n",
"\n",
"Si noti, in particolare, che $\\mathrm{QFT}_2$ è un altro nome per un'operazione di Hadamard.\n",
"\n",
"\n",
"\n",
"### Unitarità\n",
"\n",
"Verifichiamo che $\\mathrm{QFT}_N$ sia unitaria, per qualsiasi scelta di $N$.\n",
"Un modo per farlo è dimostrare che le sue colonne formano una base ortonormale.\n",
"Possiamo definire un vettore corrispondente alla colonna numero $y$, a partire da $y = 0$ fino a $y = N-1$, in questo modo:\n",
"\n",
"$$\n",
"\\vert\\phi_y\\rangle = \\frac{1}{\\sqrt{N}} \\sum_{x = 0}^{N-1} \\omega_N^{xy} \\vert x \\rangle.\n",
"$$\n",
"\n",
"Prendendo il prodotto interno tra due vettori qualsiasi si ottiene questa espressione:\n",
"\n",
"$$\n",
"\\langle \\phi_z \\vert \\phi_y \\rangle = \\frac{1}{N} \\sum_{x = 0}^{N-1} \\omega_N^{x (y - z)}\n",
"$$\n",
"\n",
"Possiamo valutare somme come questa utilizzando la seguente formula per la somma dei primi $N$ termini di una serie geometrica.\n",
"\n",
"$$\n",
"1 + \\alpha + \\alpha^2 + \\cdots + \\alpha^{N-1} =\n",
"\\begin{cases}\n",
"\\frac{\\alpha^N - 1}{\\alpha - 1} & \\text{if } \\alpha\\neq 1\\\\[2mm]\n",
"N & \\text{if } \\alpha=1\n",
"\\end{cases}\n",
"$$\n",
"\n",
"In particolare, possiamo utilizzare questa formula quando $\\alpha = \\omega_N^{y-z}$.\n",
"Quando $y = z$, abbiamo $\\alpha = 1$; quindi, applicando la formula e dividendo per $N$, si ottiene\n",
"\n",
"$$\n",
"\\langle \\phi_y \\vert \\phi_y \\rangle = 1.\n",
"$$\n",
"\n",
"Quando $y\\neq z$, si ha che $\\alpha \\neq 1$, quindi la formula rivela quanto segue:\n",
"\n",
"$$\n",
"\\langle \\phi_z \\vert \\phi_y \\rangle = \\frac{1}{N} \\frac{\\omega_N^{N(y-z)} - 1}{\\omega_N^{y-z} - 1}\n",
"= \\frac{1}{N} \\frac{1 - 1}{\\omega_N^{y-z} - 1} = 0.\n",
"$$\n",
"\n",
"Ciò accade perché $\\omega_N^N = e^{2\\pi i} = 1$, quindi $\\omega_N^{N(y-z)} = 1^{y-z} = 1$, rendendo il numeratore pari a zero, mentre il denominatore è diverso da zero poiché $\\omega_N^{y-z} \\neq 1$.\n",
"Intuitivamente, ciò che stiamo facendo è sommare una serie di punti distribuiti lungo il cerchio unitario, che si annullano a vicenda e, una volta sommati, danno come risultato $0$.\n",
"\n",
"Abbiamo quindi stabilito che $\\{\\vert\\phi_0\\rangle,\\ldots,\\vert\\phi_{N-1}\\rangle\\}$ è un insieme ortonormale,\n",
"\n",
"$$\n",
"\\langle \\phi_z \\vert \\phi_y \\rangle =\n",
"\\begin{cases}\n",
"1 & y=z\\\\\n",
"0 & y\\neq z,\n",
"\\end{cases}\n",
"$$\n",
"\n",
"che rivela che $\\mathrm{QFT}_N$ è unitario.\n",
"\n",
"\n",
"\n",
"### Gate a fase controllata\n",
"\n",
"Per implementare la trasformata di Fourier quantistica con un circuito quantistico, dovremo fare uso di porte *a fase controllata*.\n",
"Ricordiamo che un' *operazione di fase* è un'operazione unitaria a singolo qubit della forma\n",
"\n",
"$$\n",
"P_{\\alpha} =\n",
"\\begin{pmatrix}\n",
"1 & 0\\\\[1mm]\n",
"0 & e^{i\\alpha}\n",
"\\end{pmatrix}\n",
"$$\n",
"\n",
"per ogni numero reale $\\alpha$.\n",
"Una versione controllata di questa porta presenta la seguente matrice:\n",
"\n",
"$$\n",
"CP_{\\alpha} =\n",
"\\begin{pmatrix}\n",
"1 & 0 & 0 & 0\\\\[1mm]\n",
"0 & 1 & 0 & 0\\\\[1mm]\n",
"0 & 0 & 1 & 0\\\\[1mm]\n",
"0 & 0 & 0 & e^{i\\alpha}\n",
"\\end{pmatrix}\n",
"$$\n",
"\n",
"Per questo gate controllato, non ha importanza quale qubit sia il controllo e quale il bersaglio, perché le due possibilità sono equivalenti.\n",
"Per rappresentare questa porta nei diagrammi dei circuiti quantistici possiamo utilizzare uno dei seguenti simboli.\n",
"\n",
"\n",
"\n",
"Per la terza forma, l'etichetta $\\alpha$ viene talvolta collocata anche a lato della linea di controllo o sotto il controllo inferiore, quando è conveniente.\n",
"\n",
"Per eseguire la trasformata di Fourier quantistica quando $N = 2^m$ e $m\\geq 2$, dovremo eseguire un’operazione su $m$ qubit, la cui azione sugli stati in base standard può essere descritta come\n",
"\n",
"$$\n",
"\\vert y \\rangle \\vert a \\rangle \\mapsto \\omega_{2^m}^{ay} \\vert y \\rangle \\vert a \\rangle,\n",
"$$\n",
"\n",
"dove $a$ è un bit e $y \\in \\{0,\\ldots,2^{m-1} - 1\\}$ è un numero codificato in notazione binaria come stringa di $m-1$ bit.\n",
"Ciò può essere realizzato utilizzando porte a fase controllata, generalizzando il seguente esempio, per il quale si ha che $m=5$.\n",
"\n",
"\n",
"\n",
"In generale, per una scelta arbitraria di $m\\geq 2$, il qubit superiore corrispondente al bit $a$ può essere considerato come il controllo, con i gate di fase $P_{\\alpha}$ che vanno da\n",
"$\\alpha = \\pi/2^{m-1}$ sul qubit corrispondente al bit meno significativo di $y$ a $\\alpha = \\frac{\\pi}{2}$ sul qubit corrispondente al bit più significativo di $y$.\n",
"Questi gate di fase controllati commutano tutti tra loro e potrebbero essere eseguiti in qualsiasi ordine.\n",
"\n",
"\n",
"\n",
"### Implementazione circuitale del QFT\n",
"\n",
"Ora vedremo come implementare la trasformata di Fourier quantistica con un circuito quando la dimensione $N = 2^m$ è una potenza di $2$.\n",
"Esistono, infatti, diversi modi per implementare la trasformata di Fourier quantistica, ma questo è probabilmente il metodo più semplice che si conosca.\n",
"Una volta che sappiamo come implementare la trasformata di Fourier quantistica con un circuito quantistico, è semplice implementarne l’inversa: possiamo sostituire ogni gate con il suo inverso (o, equivalentemente, con la sua trasposta coniugata) e applicare i gate in ordine inverso.\n",
"Ogni circuito quantistico composto esclusivamente da porte unitarie può essere invertito in questo modo.\n",
"\n",
"L'implementazione è di natura ricorsiva, quindi è così che si descrive in modo più naturale.\n",
"Il caso base è quello di un sistema a una sola parte ( $m=1$ ); in tal caso, la trasformata di Fourier quantistica è un’operazione di Hadamard.\n",
"\n",
"Per eseguire la trasformata di Fourier quantistica su $m$ qubit quando $m \\geq 2$, possiamo seguire i seguenti passaggi, le cui operazioni descriveremo per stati in base standard della forma $\\vert x \\rangle \\vert a\\rangle$, dove $x\\in\\{0,\\ldots,2^{m-1} - 1\\}$ è un numero intero codificato come $m-1$ bit utilizzando la notazione binaria e $a$ è un singolo bit.\n",
"\n",
"1. Applicare prima la trasformata di Fourier quantistica $2^{m-1}$ -dimensionale ai qubit in basso/più a sinistra $m-1$ per ottenere questo stato:\n",
"\n",
"$$\n",
"\\Bigl(\\mathrm{QFT}_{2^{m-1}} \\vert x \\rangle\\Bigr) \\vert a\\rangle\n",
"= \\frac{1}{\\sqrt{2^{m-1}}} \\sum_{y = 0}^{2^{m-1} - 1} \\omega_{2^{m-1}}^{xy} \\vert y \\rangle \\vert a \\rangle.\n",
"$$\n",
"\n",
"Ciò avviene applicando ricorsivamente il metodo descritto per un qubit in meno, utilizzando l'operazione Hadamard su un singolo qubit come caso base su un singolo qubit come caso base.\n",
"\n",
"2. Usare il qubit superiore/destro come controllo per iniettare la fase $\\omega_{2^m}^y$ per ogni stato di base standard $\\vert y\\rangle$ dei restanti $m-1$ qubit (come descritto sopra) per ottenere questo stato:\n",
"\n",
"$$\n",
"\\frac{1}{\\sqrt{2^{m-1}}} \\sum_{y = 0}^{2^{m-1} - 1} \\omega_{2^{m-1}}^{xy}\n",
"\\omega_{2^m}^{ay} \\vert y \\rangle \\vert a \\rangle.\n",
"$$\n",
"\n",
"3. Eseguire un cancello di Hadamard sul qubit in alto a destra per ottenere questo stato:\n",
"\n",
"$$\n",
"\\frac{1}{\\sqrt{2^{m}}} \\sum_{y = 0}^{2^{m-1} - 1} \\sum_{b=0}^1\n",
"(-1)^{ab} \\omega_{2^{m-1}}^{xy} \\omega_{2^m}^{ay}\n",
"\\vert y \\rangle \\vert b \\rangle.\n",
"$$\n",
"\n",
"4. Permutare l'ordine dei qubit in modo che il bit meno significativo diventi il bit più significativo, con tutti gli altri spostati verso l'alto o verso destra tutti gli altri spostati verso l'alto o verso destra:\n",
"\n",
"$$\n",
"\\frac{1}{\\sqrt{2^{m}}} \\sum_{y = 0}^{2^{m-1} - 1} \\sum_{b=0}^1\n",
"(-1)^{ab} \\omega_{2^{m-1}}^{xy} \\omega_{2^m}^{ay}\n",
"\\vert b \\rangle \\vert y \\rangle.\n",
"$$\n",
"\n",
"Ad esempio, ecco il circuito che otteniamo per $N = 32 = 2^5$.\n",
"In questo diagramma, per maggiore chiarezza, ai qubit sono stati assegnati nomi che corrispondono ai vettori di base standard $\\vert x\\rangle \\vert a\\rangle$ (per l’input) e $\\vert b\\rangle \\vert y\\rangle$ (per l’output).\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"### Analisi\n",
"\n",
"La formula chiave che ci serve per verificare che il circuito appena descritto implementa la trasformata di Fourier quantistica $2^m$ è questa:\n",
"\n",
"$$\n",
"(-1)^{ab}\n",
"\\omega_{2^{m-1}}^{xy}\n",
"\\omega_{2^m}^{ay}\n",
"=\n",
"\\omega_{2^m}^{(2x+ a)(2^{m-1}b + y)}.\n",
"$$\n",
"\n",
"Questa formula vale per qualsiasi scelta di numeri interi $a$, $b$, $x$ e $y$, ma ci servirà solo per\n",
"$a,b\\in\\{0,1\\}$ e $x,y\\in\\{0,\\ldots,2^{m-1}-1\\}$.\n",
"È possibile verificarla sviluppando il prodotto nell'esponente sul lato destro,\n",
"\n",
"$$\n",
" \\omega_{2^m}^{(2x+ a)(2^{m-1}b + y)}\n",
" = \\omega_{2^m}^{2^m xb} \\omega_{2^m}^{2xy} \\omega_{2^m}^{2^{m-1}ab} \\omega_{2^m}^{ay}\n",
" = (-1)^{ab} \\omega_{2^{m-1}}^{xy} \\omega_{2^m}^{ay},\n",
"$$\n",
"\n",
"dove la seconda uguaglianza sfrutta l'osservazione che\n",
"\n",
"$$\n",
"\\omega_{2^m}^{2^m xb} = \\bigl(\\omega_{2^m}^{2^m}\\bigr)^{xb} = 1^{xb} = 1.\n",
"$$\n",
"\n",
"La trasformata di Fourier quantistica a -dimensioni di $2^m$ è definita come segue per ogni $u\\in\\{0,\\ldots,2^m - 1\\}$.\n",
"\n",
"$$\n",
"\\mathrm{QFT}_{2^m} \\vert u\\rangle = \\frac{1}{\\sqrt{2^m}}\n",
"\\sum_{v = 0}^{2^m - 1} \\omega_{2^m}^{uv} \\vert v\\rangle\n",
"$$\n",
"\n",
"Se scriviamo $u$ e $v$ come\n",
"\n",
"$$\n",
"\\begin{aligned}\n",
"u & = 2x + a\\\\\n",
"v & = 2^{m-1}b + y\n",
"\\end{aligned}\n",
"$$\n",
"\n",
"per $a,b\\in\\{0,1\\}$ e $x,y\\in\\{0,\\ldots,2^{m-1} - 1\\}$, si ottiene\n",
"\n",
"$$\n",
"\\begin{aligned}\n",
"\\mathrm{QFT}_{2^m} \\vert 2x + a\\rangle\n",
"& =\n",
"\\frac{1}{\\sqrt{2^m}}\n",
"\\sum_{y = 0}^{2^{m-1} - 1}\n",
"\\sum_{b=0}^1\n",
"\\omega_{2^m}^{(2x+ a)(2^{m-1}b + y)} \\vert b 2^{m-1} + y\\rangle\\\\[2mm]\n",
"& =\n",
"\\frac{1}{\\sqrt{2^m}}\n",
"\\sum_{y = 0}^{2^{m-1} - 1}\n",
"\\sum_{b=0}^1\n",
"(-1)^{ab}\n",
"\\omega_{2^{m-1}}^{xy}\n",
"\\omega_{2^m}^{ay}\n",
"\\vert b 2^{m-1} + y\\rangle.\n",
"\\end{aligned}\n",
"$$\n",
"\n",
"Infine, considerando gli stati della base standard $\\vert x \\rangle \\vert a\\rangle$ e $\\vert b \\rangle \\vert y \\rangle$ come codifiche binarie di numeri interi nell'intervallo $\\{0,\\ldots,2^m-1\\}$,\n",
"\n",
"$$\n",
"\\begin{aligned}\n",
"\\vert x \\rangle \\vert a\\rangle & = \\vert 2x + a \\rangle\\\\\n",
"\\vert b \\rangle \\vert y \\rangle & = \\vert 2^{m-1}b + y\\rangle,\n",
"\\end{aligned}\n",
"$$\n",
"\n",
"vediamo che il circuito di cui sopra implementa l'operazione richiesta.\n",
"Se questo metodo per eseguire la trasformata di Fourier quantistica sembra notevole, è perché lo è: è essenzialmente la trasformata di Fourier veloce sotto forma di circuito quantistico.\n",
"\n",
"Infine, contiamo quante porte sono utilizzate nel circuito appena descritto.\n",
"I gate a fase controllata non fanno parte dell'insieme di gate standard di cui abbiamo parlato nella lezione precedente, ma per cominciare ignoreremo questo fatto e considereremo ciascuno di essi come un singolo gate.\n",
"\n",
"Indichiamo con $s_m$ il numero di porte necessarie per ogni possibile scelta di $m$.\n",
"Se $m=1$, la trasformata di Fourier quantistica è semplicemente un’operazione di Hadamard, quindi\n",
"\n",
"$$\n",
"s_1 = 1.\n",
"$$\n",
"\n",
"Se $m\\geq 2$, allora nel circuito sopra riportato occorrono $s_{m-1}$ porte per la trasformata di Fourier quantistica su $m-1$ qubit, più $m-1$ porte di fase controllata, più una porta di Hadamard, più $m-1$ porte di scambio, quindi\n",
"\n",
"$$\n",
"s_m = s_{m-1} + (2m - 1).\n",
"$$\n",
"\n",
"Possiamo ottenere un'espressione in forma chiusa mediante la somma:\n",
"\n",
"$$\n",
"s_m = \\sum_{k = 1}^m (2k - 1) = m^2.\n",
"$$\n",
"\n",
"In realtà non abbiamo bisogno di un numero di porte di swap così elevato come descritto nel metodo.\n",
"Se riorganizziamo leggermente le porte, possiamo spostare tutte le porte di scambio verso destra e ridurre il numero di porte di scambio necessarie a $\\lfloor m/2\\rfloor$.\n",
"Da un punto di vista asintotico, non si tratta di un miglioramento significativo: otteniamo comunque circuiti di dimensione $O(m^2)$ per eseguire l' $\\mathrm{QFT}_{2^m}$.\n",
"\n",
"Se vogliamo implementare la trasformata di Fourier quantistica usando solo porte del nostro set di porte standard, dobbiamo costruire o approssimare ciascuna delle porte a fase controllata con porte del nostro set.\n",
"Il numero necessario dipende dalla precisione richiesta, ma in funzione di $m$ il costo totale rimane quadratico.\n",
"\n",
"È infatti possibile approssimare la trasformata quantistica di Fourier con un numero sub-quadratico di porte, sfruttando il fatto che $P_{\\alpha}$ è molto vicino all'operazione di identità quando $\\alpha$ è molto piccolo - il che significa che possiamo semplicemente escludere la maggior parte delle porte a fase controllata senza subire una perdita eccessiva in termini di precisione.\n",
"\n",
"\n",
"\n",
"## Procedura generale e analisi\n",
"\n",
"Esaminiamo ora la procedura di stima delle fasi in generale.\n",
"L'idea è di estendere la versione a due qubit della stima di fase che abbiamo considerato in precedenza nel modo naturale suggerito dal diagramma seguente.\n",
"\n",
"\n",
"\n",
"Si noti che, per ogni nuovo qubit di controllo aggiunto in cima, *raddoppiamo* il numero di volte in cui viene eseguita l'operazione unitaria $U$.\n",
"Questo è indicato nel diagramma dai poteri su $U$ per ciascuna delle operazioni controllate-unitarie.\n",
"\n",
"Il modo più semplice per implementare un’operazione di tipo “controlled- $U^k$ ” per una data scelta di $k$ consiste semplicemente nel ripetere un’operazione di tipo “controlled- $U$ ” $k$ volte.\n",
"Se questa è effettivamente la metodologia utilizzata, occorre riconoscere che l’aggiunta di qubit di controllo incide in modo significativo sulle dimensioni del circuito: se disponiamo di $m$ qubit di controllo, come illustrato nel diagramma, sono necessarie in totale $2^m - 1$ copie dell’operazione “controlled- $U$ ”.\n",
"Ciò significa che, all’aumentare di `$m$`, si registra un costo computazionale significativo; tuttavia, come vedremo, ciò porta anche a un’approssimazione significativamente più accurata di `$\\theta$`.\n",
"\n",
"È importante notare, tuttavia, che per *alcune* scelte di $U$ potrebbe essere possibile creare un circuito che implementi l'operazione $U^k$ per valori elevati di $k$ in modo più efficiente rispetto alla semplice ripetizione $k$ volte del circuito per $U$.\n",
"Vedremo un esempio specifico di ciò nel contesto della fattorizzazione dei numeri interi più avanti nella lezione, dove l'algoritmo efficiente per *l'esponenziazione modulare* discusso nella lezione precedente viene in nostro soccorso.\n",
"\n",
"Analizziamo ora il circuito appena descritto.\n",
"Lo stato immediatamente precedente alla trasformata quantistica inversa di Fourier si presenta così:\n",
"\n",
"$$\n",
"\\frac{1}{\\sqrt{2^m}} \\sum_{x = 0}^{2^m - 1} \\bigl( U^x \\vert\\psi\\rangle \\bigr) \\vert x\\rangle\n",
"= \\vert\\psi\\rangle \\otimes \\frac{1}{\\sqrt{2^m}} \\sum_{x = 0}^{2^m - 1} e^{2\\pi i x\\theta} \\vert x\\rangle.\n",
"$$\n",
"\n",
"\n",
"\n",
"### Un caso speciale\n",
"\n",
"Analogamente a quanto fatto nel caso di “ $m=2$ ”, considereremo innanzitutto il caso particolare in cui\n",
"$\\theta = y/2^m$ per $y\\in\\{0,\\ldots,2^m-1\\}$.\n",
"In questo caso, lo stato precedente alla trasformata di Fourier quantistica inversa può essere scritto in alternativa in questo modo:\n",
"\n",
"$$\n",
"\\vert\\psi\\rangle \\otimes \\frac{1}{\\sqrt{2^m}} \\sum_{x = 0}^{2^m - 1} e^{2\\pi i \\frac{xy}{2^m}} \\vert x\\rangle\n",
"= \\vert\\psi\\rangle \\otimes \\frac{1}{\\sqrt{2^m}} \\sum_{x = 0}^{2^m - 1} \\omega_{2^m}^{xy} \\vert x\\rangle\n",
"= \\vert\\psi\\rangle \\otimes \\mathrm{QFT}_{2^m} \\vert y\\rangle.\n",
"$$\n",
"\n",
"Quindi, quando si applica la trasformata quantistica inversa di Fourier, lo stato diventa\n",
"\n",
"$$\n",
"\\vert\\psi\\rangle \\vert y\\rangle\n",
"$$\n",
"\n",
"e le misure rivelano $y$ (codificato in binario).\n",
"\n",
"\n",
"\n",
"### Limitare le probabilità\n",
"\n",
"Per altri valori di $\\theta$, ovvero quelli che non assumono la forma $y/2^m$ per un numero intero $y$, i risultati della misurazione non saranno certi, ma possiamo dimostrare l'esistenza di limiti alle probabilità dei diversi risultati.\n",
"Proseguendo, consideriamo una scelta arbitraria di $\\theta$ tale che $0\\leq \\theta < 1$.\n",
"\n",
"Dopo l'esecuzione della trasformata quantistica inversa di Fourier, lo stato del circuito è questo:\n",
"\n",
"$$\n",
"\\vert \\psi \\rangle \\otimes\n",
"\\frac{1}{2^m} \\sum_{y=0}^{2^m - 1} \\sum_{x=0}^{2^m-1} e^{2\\pi i x (\\theta - y/2^m)} \\vert y\\rangle.\n",
"$$\n",
"\n",
"Quindi, quando vengono eseguite le misure sui qubit superiori $m$, vediamo che ogni risultato $y$ con probabilità\n",
"\n",
"$$\n",
"p_y =\n",
"\\left\\vert \\frac{1}{2^m} \\sum_{x=0}^{2^m - 1} e^{2\\pi i x (\\theta - y/2^m)} \\right\\vert^2.\n",
"$$\n",
"\n",
"Per capire meglio queste probabilità, utilizzeremo la stessa formula che abbiamo visto prima, per la somma della parte iniziale di una serie geometrica.\n",
"\n",
"$$\n",
"1 + \\alpha + \\alpha^2 + \\cdots + \\alpha^{N-1} =\n",
"\\begin{cases}\n",
"\\frac{\\alpha^N - 1}{\\alpha - 1} & \\text{if } \\alpha\\neq 1\\\\[2mm]\n",
"N & \\text{if } \\alpha=1\n",
"\\end{cases}\n",
"$$\n",
"\n",
"Possiamo semplificare la somma che compare nella formula per l' $p_y$ e, ponendo $\\alpha = e^{2\\pi i (\\theta - y/2^m)}$.\n",
"Ecco cosa otteniamo.\n",
"\n",
"$$\n",
"\\sum_{x=0}^{2^m - 1} e^{2\\pi i x (\\theta - y/2^m)}\n",
"=\n",
"\\begin{cases}\n",
"2^m & \\theta = y/2^m\\\\[2mm]\n",
"\\frac{e^{2\\pi i (2^m \\theta - y)} - 1}{e^{2\\pi i (\\theta - y/2^m)} - 1}\n",
"& \\theta\\neq y/2^m\n",
"\\end{cases}\n",
"$$\n",
"\n",
"Quindi, nel caso in cui $\\theta = y/2^m$, si ha che $p_y = 1$ (come già sapevamo dall’analisi di questo caso particolare),\n",
"e nel caso in cui $\\theta \\neq y/2^m$, si ha che\n",
"\n",
"$$\n",
"p_y = \\frac{1}{2^{2m}} \\left\\vert \\frac{e^{2\\pi i (2^m \\theta - y)} - 1}{e^{2\\pi i (\\theta - y/2^m)} - 1}\\right\\vert^2.\n",
"$$\n",
"\n",
"Possiamo approfondire la comprensione di queste probabilità riflettendo sulla relazione tra le lunghezze degli archi e quelle delle corde sul cerchio unitario.\n",
"Ecco una figura che illustra le relazioni di cui abbiamo bisogno per ogni numero reale $\\delta\\in \\bigl[ -\\frac{1}{2},\\frac{1}{2}\\bigr]$.\n",
"\n",
"\n",
"\n",
"Innanzitutto, la lunghezza della corda (disegnata in blu) non può essere maggiore della lunghezza dell'arco (disegnata in viola):\n",
"\n",
"$$\n",
"\\bigl\\vert e^{2\\pi i \\delta} - 1\\bigr\\vert \\leq 2\\pi\\vert\\delta\\vert.\n",
"$$\n",
"\n",
"Mettendo in relazione queste lunghezze nell’altra direzione, si osserva che il rapporto tra la lunghezza dell’arco e la lunghezza della corda è massimo quando $\\delta = \\pm 1/2$, e in questo caso il rapporto è pari alla metà della circonferenza del cerchio divisa per il diametro, ovvero $\\pi/2$.\n",
"Pertanto, si ha\n",
"\n",
"$$\n",
"\\frac{2\\pi\\vert\\delta\\vert}{\\bigl\\vert e^{2\\pi i \\delta} - 1\\bigr\\vert} \\leq \\frac{\\pi}{2},\n",
"$$\n",
"\n",
"e così\n",
"\n",
"$$\n",
"\\bigl\\vert e^{2\\pi i \\delta} - 1\\bigr\\vert \\geq 4\\vert\\delta\\vert.\n",
"$$\n",
"\n",
"Un'analisi basata su queste relazioni rivela i due fatti seguenti.\n",
"\n",
"1. Supponiamo che $\\theta$ sia un numero reale e che $y\\in \\{0,\\ldots,2^m-1\\}$ soddisfi\n",
"\n",
"$$\n",
"\\Bigl\\vert \\theta - \\frac{y}{2^m}\\Bigr\\vert \\leq 2^{-(m+1)}.\n",
"$$\n",
"\n",
"Ciò significa che $y/2^m$ è o la migliore approssimazione a $m$ -bit di $\\theta$, oppure si trova esattamente a metà strada tra $y/2^m$ e $(y-1)/2^m$ o $(y+1)/2^m$, quindi è una delle due migliori approssimazioni di $\\theta$.\n",
"\n",
"Dimostreremo che, in questo caso, $p_y$ deve essere piuttosto grande.\n",
"In base all'ipotesi che stiamo considerando, ne consegue che $\\vert 2^m \\theta - y \\vert \\leq 1/2$; possiamo quindi utilizzare la seconda osservazione sopra riportata, che mette in relazione le lunghezze dell’arco e della corda, per concludere che\n",
"\n",
"$$\n",
"\\left\\vert e^{2\\pi i (2^m \\theta - y)} - 1\\right\\vert\n",
"\\geq 4 \\vert 2^m \\theta - y \\vert = 4 \\cdot 2^m \\cdot \\Bigl\\vert \\theta - \\frac{y}{2^m}\\Bigr\\vert.\n",
"$$\n",
"\n",
"Possiamo anche utilizzare la prima osservazione sulle lunghezze degli archi e delle corde per concludere che\n",
"\n",
"$$\n",
"\\left\\vert e^{2\\pi i (\\theta - y/2^m)} - 1\\right\\vert \\leq 2\\pi \\Bigl\\vert \\theta - \\frac{y}{2^m}\\Bigr\\vert.\n",
"$$\n",
"\n",
"Utilizzando queste due disuguaglianze su $p_y$ si scopre che\n",
"\n",
"$$\n",
"p_y \\geq \\frac{1}{2^{2m}} \\frac{16 \\cdot 2^{2m}}{4 \\pi^2} = \\frac{4}{\\pi^2} \\approx 0.405.\n",
"$$\n",
"\n",
"Ciò spiega la nostra osservazione secondo cui, nella versione “ $m=2$ ” della stima di fase discussa in precedenza, il risultato migliore si verifica con una probabilità superiore a $40\\%$.\n",
"In realtà non è proprio il 40%, ma un $4/\\pi^2$ e; infatti, questo limite vale per qualsiasi scelta di $m$.\n",
"\n",
"2. Supponiamo ora che $y\\in \\{0,\\ldots,2^m-1\\}$ soddisfi\n",
"\n",
"$$\n",
"2^{-m} \\leq \\Bigl\\vert \\theta - \\frac{y}{2^m}\\Bigr\\vert \\leq \\frac{1}{2}.\n",
"$$\n",
"\n",
"Ciò significa che esiste un'approssimazione migliore $z/2^m$ rispetto a $\\theta$, compresa tra $\\theta$ e $y/2^m$.\n",
"\n",
"Questa volta dimostreremo che $p_y$ non può essere troppo grande.\n",
"Possiamo iniziare con la semplice osservazione che\n",
"\n",
"$$\n",
"\\left\\vert e^{2\\pi i (2^m \\theta - y)} - 1\\right\\vert \\leq 2,\n",
"$$\n",
"\n",
"ciò deriva dal fatto che due punti qualsiasi sul cerchio unitario possono differire in valore assoluto al massimo di $2$.\n",
"\n",
"Possiamo anche utilizzare la seconda osservazione sulle lunghezze degli archi e delle corde di cui sopra, questa volta lavorando con il denominatore di $p_y$ anziché con il numeratore, per concludere che\n",
"\n",
"$$\n",
"\\left\\vert e^{2\\pi i (\\theta - y/2^m)} - 1\\right\\vert \\geq 4\\Bigl\\vert \\theta - \\frac{y}{2^m}\\Bigr\\vert\n",
"\\geq 4 \\cdot 2^{-m}.\n",
"$$\n",
"\n",
"Mettendo insieme le due disuguaglianze si ottiene\n",
"\n",
"$$\n",
"p_y \\leq \\frac{1}{2^{2m}} \\frac{4}{16 \\cdot 2^{-2m}} = \\frac{1}{4}.\n",
"$$\n",
"\n",
"Si noti che, sebbene questo limite sia sufficiente ai nostri fini, è piuttosto approssimativo: la probabilità è solitamente molto inferiore a $1/4$.\n",
"\n",
"Il punto fondamentale che emerge da questa analisi è che è probabile che si verifichino approssimazioni molto vicine a $\\theta$ — otterremo un’approssimazione ottimale di $m$ bit con probabilità superiore a $40\\%$ — mentre è meno probabile che si verifichino approssimazioni con uno scarto superiore a $2^{-m}$, con probabilità limitata superiormente da $25\\%$.\n",
"\n",
"Date queste garanzie, è possibile aumentare la nostra confidenza ripetendo più volte la procedura di stima di fase, al fine di raccogliere prove statistiche su $\\theta$.\n",
"È importante notare che lo stato $\\vert\\psi\\rangle$ dell’insieme inferiore di qubit rimane inalterato dalla procedura di stima di fase, pertanto può essere utilizzato per eseguire la procedura tutte le volte che si desidera.\n",
"In particolare, ogni volta che eseguiamo il circuito, otteniamo un’approssimazione “best $m$ -bit” di $\\theta$ con probabilità superiore a $40\\%$, mentre la probabilità di uno scostamento superiore a $2^{-m}$ è limitata da $25\\%$.\n",
"Se eseguiamo il circuito più volte e prendiamo il risultato che ricorre più frequentemente tra le esecuzioni, è quindi estremamente probabile che il risultato che ricorre più frequentemente non sia uno di quelli che si verifica al massimo $25\\%$ delle volte.\n",
"Di conseguenza, è molto probabile che otteniamo un'approssimazione $y/2^m$ che rientri nell'intervallo $1/2^m$ rispetto al valore $\\theta$.\n",
"Infatti, la probabilità, già di per sé bassa, che l'errore superi $1/2^m$ diminuisce in modo esponenziale al crescere del numero di volte in cui viene eseguita la procedura.\n",
"\n",
"Di seguito sono riportati due grafici che mostrano le probabilità relative a tre valori consecutivi di $y$ quando $m = 3$ e $m=4$, in funzione di $\\theta$.\n",
"(Per maggiore chiarezza, vengono mostrati solo tre risultati. Le probabilità relative ad altri esiti si ottengono spostando ciclicamente la stessa funzione di base.)\n",
"\n",
"\n",
"\n",
"\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"id": "a1b8767d",
"source": "© IBM Corp., 2017-2026"
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3"
}
},
"nbformat": 4,
"nbformat_minor": 5
}