Quantum Computing: Matematica e Teoria per Principianti

1. Introduzione e Struttura del Corso di Quantum Computing [0]

1. Quantum Computing (QC) usa la meccanica quantistica per elaborare informazioni velocemente. [0]
2. Questo corso offre una base solida, spiegando come funzionano gli algoritmi quantistici. [1]
3. Il corso è diviso in due sezioni principali: matematica essenziale e meccanica quantistica. [2]
4. QC è potente e trasformerà la tecnologia. [3]
5. Michael di Quantum Source ha creato il corso. [4]
6. Spiegazioni comuni usano analogie (es. qubit è 0 e 1 insieme) che non sono chiare. [5]
7. Questo corso insegna il funzionamento reale, senza analogie. [7]

1.1. Struttura Dettagliata del Corso [8]

1. Sezione 1: Matematica di base necessaria. [9]
   1. Introduzione ai numeri complessi. [9]
   2. Algebra lineare di base. [9]
2. Sezione successiva: Esplorazione del qubit e sua rappresentazione matematica. [9]
   1. Operazioni su singolo qubit e loro proprietà. [10]
3. Sezione 3: Rappresentazione matematica di qubit multipli. [11]
   1. Operazioni su qubit multipli. [11]
   2. Fenomeni quantistici: entanglement e phase kickback. [12]
4. Sezione finale: Analisi degli algoritmi quantistici. [13]
   1. Mostra la natura rivoluzionaria del QC. [14]

2. Matematica Fondamentale: Numeri Complessi [15]

2.1. Numeri Immaginari e Complessi [15]

1. Si inizia con le radici quadrate dei numeri. [15]
2. Se $x^2=4$, allora $x=\pm 2$. [16]
3. Se $x^2=-4$, si introducono i numeri immaginari. [17]
   1. Si definisce $i$ come la radice quadrata di $-1$. [18]
   2. $\sqrt{-4}$ diventa $\pm 2i$. [18]
   3. Un numero immaginario contiene un fattore di $\sqrt{-1}$. [19]
4. Si passa ai numeri complessi. [20]
   1. Un numero complesso è un numero reale più un numero immaginario. [21]
   2. La forma standard è $a+iB$, dove $A$ e $B$ sono reali. [22]
   3. $A$ è la parte reale. [22]
   4. $B$ è la parte immaginaria. [22]
5. Questi numeri saranno usati per modellare gli stati quantistici. [23]

2.2. Operazioni sui Numeri Complessi [24]

1. Addizione e sottrazione si fanno sommando/sottraendo parti reali e immaginarie. [24]
2. La moltiplicazione richiede di ricordare che $i^2=-1$. [25]
3. Il coniugato complesso si ottiene invertendo il segno della parte immaginaria. [26]
   1. È denotato da un asterisco (*). [27]
4. Proprietà: moltiplicare un complesso per il suo coniugato dà sempre un numero reale. [29]
   1. Esempio: $(2+3i)(2-3i)$ deve essere reale. [30]
5. Si può rappresentare un complesso come un vettore su un piano. [31]
   1. Asse orizzontale: Reale; Asse verticale: Immaginario. [31]
   2. Esempio: $-2+3i$ termina nel punto $(-2,3)$. [32]

2.3. Rappresentazioni Alternative dei Numeri Complessi [33]

1. La magnitudine è la distanza dall'origine (calcolata con Pitagora). [33]
   1. $|A+iB|=\sqrt{a^2+b^2}$. [34]
2. Rappresentazione tramite forma polare: magnitudine ($r$) e angolo ($\theta$). [36]
   1. Forma: $r(\cos \theta +i\sin \theta )$. [37]
   2. $\theta$ si trova con $\tan \theta =B/A$, quindi $\theta =\arctan (B/A)$. [38]
3. Forma esponenziale: $r{e}^{i\theta }$. [40]
4. In QC si usa quasi esclusivamente la forma esponenziale. [42]
   1. Cambiare $\theta$ ruota attorno a un cerchio. [43]
   2. Moltiplicare due numeri con magnitudine uno è una rotazione sul cerchio unitario. [43]
   3. Questa proprietà è utile per rappresentare gli stati quantistici. [44]

3. Matematica Fondamentale: Matrici [45]

3.1. Definizione e Operazioni Base su Matrici [45]

1. Una matrice è una disposizione bidimensionale di numeri. [45]
2. Una matrice $M\times N$ ha $M$ righe e $N$ colonne. [47]
   1. Una matrice data è una matrice $2\times 3$. [47]
3. Addizione/Sottrazione: Si sommano/sottraggono gli elementi corrispondenti. [49]
   1. Richiede che righe e colonne siano identiche per entrambe le matrici. [51]
4. Moltiplicazione per uno scalare: Ogni elemento è moltiplicato per lo scalare. [53]
5. Moltiplicazione tra matrici: Si usa un'operazione simile al prodotto scalare (dot product). [55]
   1. L'elemento $(r,c)$ è il prodotto scalare tra la riga $r$ della prima e la colonna $c$ della seconda. [55]
6. Condizione per la moltiplicazione: colonne della prima = righe della seconda. [58]

3.2. Vettori, Trasformazioni e Proprietà Speciali [59]

1. Una matrice $N\times 1$ è chiamata vettore colonna. [60]
2. I vettori colonna rappresentano uno stato nella computazione quantistica. [62]
3. Moltiplicare una matrice per un vettore colonna lo trasforma. [64]
   1. Le matrici agiscono come trasformazioni sui vettori. [65]
4. Matrice identità: Matrice diagonale con tutti uni; moltiplicandola si ottiene la matrice originale. [68]
5. Matrice inversa ($A^{-1}$): Moltiplicata per $A$ dà la matrice identità. [72]
   1. Applicare $A$ e poi $A^{-1}$ lascia il vettore invariato. [74]
6. Coniugato complesso di una matrice: Si inverte il segno delle componenti immaginarie. [76]
7. Trasposta ($A^T$): Si scambiano righe e colonne. [80]
8. Dagger ($A^{†}$): Coniugato complesso più trasposta. [82]
9. Matrici Unitari ($U$): $U{U}^{†}=I$ (l'inversa è il dagger). [84]
   1. Geometricamente, ruotano o ribaltano il vettore senza cambiarne la lunghezza. [86]
10. Matrici Ermitiane ($H$): $H=H^{†}$. [88]
11. Autovettore (Eigenvector): Vettore che rimane nella stessa direzione dopo la trasformazione. [91]
12. Autovalore (Eigenvalue): Lo scalare per cui l'autovettore viene allungato/compresso. [93]
    1. Esempio: Matrice $\left(\begin{array}{cc}2& 0\\ 1& 1\end{array}\right)$ ha autovalore 2 per l'autovettore $\left(\begin{array}{c}0\\ 3\end{array}\right)$. [94]

4. Fondamenti del Quantum Computing: Qubit e Misurazione [98]

4.1. Qubit e Sovrapposizione [98]

1. Computer classici usano bit (0 o 1). [98]
2. Computer quantistici usano qubit (0 e 1 contemporaneamente). [99]
3. Un qubit può essere una particella quantistica con due stati distinti (es. polarizzazione di un fotone). [102]
4. 0 e 1 sono definiti come vettori colonna: $|0⟩=\left(\begin{array}{c}1\\ 0\end{array}\right)$ e $|1⟩=\left(\begin{array}{c}0\\ 1\end{array}\right)$. [103]
   1. Le parentesi angolari sono la notazione di Dirac (ket). [104]
5. Superposizione: Una particella è in due stati contemporaneamente. [105]
   1. Un qubit è in sovrapposizione se ha valori non nulli per 0 e 1. [107]

4.2. Misurazione e Probabilità [115]

1. Misurare un sistema quantistico ne cambia lo stato alla misurazione. [115]
2. Se un qubit in sovrapposizione viene misurato, collassa in 0 o 1. [117]
3. Non si misura quanto è in stato 0 o 1. [122]
4. I numeri nella rappresentazione vettoriale indicano la probabilità di misurare 0 o 1. [124]
   1. Probabilità di misurare 0: modulo quadro dell'ampiezza dello stato 0. [125]
   2. Probabilità di misurare 1: modulo quadro dell'ampiezza dello stato 1. [125]
5. Esempio: stato $\left(\begin{array}{c}\sqrt{3}/2\\ 1/2\end{array}\right)$ ha 75% di probabilità di misurare 0. [125]
6. La somma delle probabilità deve essere 1 (es. $\left(\begin{array}{c}1\\ 0\end{array}\right)$ è sempre misurato come 0). [127]
7. La misurazione cambia permanentemente lo stato al risultato ottenuto. [131]

4.3. Notazione di Dirac e Sfera di Bloch [132]

1. Si usa la notazione di Dirac (ket) per stati quantistici, poiché le matrici diventano grandi con più qubit. [132]
2. Conversione di $\left(\begin{array}{c}\alpha \\ \beta \end{array}\right)$ in Dirac: $\alpha |0⟩+\beta |1⟩$. [133]
   1. Le parentesi $⟨0|$ e $⟨1|$ sono chiamate ket. [137]
3. Rappresentazione grafica: Sfera di Bloch. [141]
   1. Polo Nord: stato $|0⟩$. Polo Sud: stato $|1⟩$. [142]
   2. L'altezza indica la probabilità di misurare 0 (più in alto) o 1 (più in basso). [145]
4. La rotazione del qubit sulla sfera è chiamata fase. [148]
5. Esempio: stato $\left(\begin{array}{c}1/\sqrt{2}\\ \sqrt{3}/2\end{array}\right)$ è a metà tra l'Equatore e il Polo Sud. [152]

5. Operazioni sui Qubit: Porte Quantistiche [153]

5.1. Porte a Qubit Singolo (X, Y, Z) [153]

1. Le porte quantistiche cambiano gli stati dei qubit. [154]
2. Le porte più comuni sono X, Y, Z. [155]
3. Porta X (NOT): Inverte lo stato (0 $\to$ 1, 1 $\to$ 0). [157]
   1. Ruota il qubit di $180^{\circ }$ ($\pi$ radianti) attorno all'asse X. [161]
4. Porta Y: Ruota il qubit di $\pi$ attorno all'asse Y. [163]
5. Porta Z: Ruota il qubit di $\pi$ attorno all'asse Z. [165]
6. Applicare la stessa porta due volte riporta il qubit alla posizione originale (sono la propria inversa). [166]
7. Le porte sono rappresentate da matrici (es. Porta X). [168]
8. Applicare una porta significa moltiplicare la sua matrice per il vettore colonna del qubit. [171]
9. Per applicare una porta $U$ in notazione di Dirac: [173]
   1. La prima colonna della matrice $U$ è dove va lo stato $|0⟩$. [173]
   2. La seconda colonna è dove va lo stato $|1⟩$. [174]
10. Le porte agiscono linearmente su ogni stato di sovrapposizione individualmente. [176]
11. La Porta Z cambia $|1⟩$ in $-|1⟩$ (cambia la fase), ma non le probabilità. [180]

5.2. Introduzione alla Fase (Phase) [181]

1. La fase è la rotazione attorno all'asse Z. [183]
2. La fase è cruciale per la potenza del QC, anche se non cambia le probabilità di misurazione. [185]
3. La fase si rappresenta matematicamente con i numeri complessi in forma esponenziale. [187]
4. Esempio: Porta Z applicata a $\frac{1}{\sqrt{2}}|0⟩+\frac{1}{\sqrt{2}}|1⟩$ dà $\frac{1}{\sqrt{2}}|0⟩-\frac{1}{\sqrt{2}}|1⟩$. [191]
   1. Il fattore $-1$ è rappresentato come $e^{i\pi }$ (rotazione di $\pi$ radianti). [194]
5. Fase Globale vs Fase Relativa: [200]
   1. Fase Globale: Moltiplicazione dell'intero qubit per un complesso (irrilevante fisicamente). [201]
   2. Fase Relativa: Moltiplicazione solo dell'ampiezza dello stato $|1⟩$ (molto importante). [201]
6. La fase relativa ruota il qubit attorno all'asse Z sulla Sfera di Bloch. [205]
7. La fase non cambia la probabilità di misurazione (il modulo quadro dell'ampiezza rimane lo stesso). [206]

5.3. Stati Equatoriali e Porta Hadamard [210]

1. Gli stati sull'Equatore della Sfera di Bloch sono: $|+⟩$, $|-⟩$, $|i⟩$, $|-i⟩$. [212]
2. Questi sono shorthand per stati con fase relativa specifica: [214]
   1. $|+⟩=\frac{1}{\sqrt{2}}(|0⟩+|1⟩)$. [216]
   2. $|-⟩=\frac{1}{\sqrt{2}}(|0⟩-|1⟩)$ (fase relativa $-1$). [217]
   3. $|i⟩$ ha fase relativa $i$. [219]
3. Porta Hadamard (H): Matrice specifica. [220]
   1. Trasforma $|0⟩\to |+⟩$ e $|1⟩\to |-⟩$. [222]
   2. È la propria inversa: $HH=I$. [224]
4. La porta Hadamard mostra che la fase è importante. [226]
   1. Trasformando $|+⟩$ e $|-⟩$ (che differiscono solo per fase relativa) si ottengono risultati diversi (0 e 1). [227]

5.4. Porte Aggiuntive e Multi-Qubit [230]

1. Porta S: Aggiunge una fase relativa di $\pi /2$ radianti. [231]
2. Porta T: Aggiunge una fase relativa di $\pi /4$ radianti. [233]
3. Le loro inverse ($S^{†},T^{†}$) aggiungono la fase negativa corrispondente. [234]
4. Più Qubit: Rappresentati tramite il prodotto tensore ($\otimes$). [238]
   1. Due qubit $|0⟩$ sono rappresentati come $|00⟩$. [239]
   2. La sovrapposizione si espande usando il prodotto tensore sulle ampiezze. [241]
   3. Due qubit generano $2^2=4$ stati possibili (es. $|00⟩,|01⟩,|10⟩,|11⟩$). [243]
5. La misurazione funziona come prima (probabilità = modulo quadro del coefficiente). [244]
6. Aggiungere un qubit al sistema si fa con il prodotto tensore alla fine dello stato. [246]
7. Notazione shorthand: $n$ zeri possono essere scritti come $|0{⟩}^{\otimes n}$. [247]

6. Circuiti Quantistici e Porte Multi-Qubit [248]

6.1. Circuiti Quantistici [248]

1. Per indicare l'applicazione di una porta si usa il circuito quantistico. [248]
   1. Le linee verticali sono i qubit. [250]
   2. Le scatole sono le porte quantistiche (es. X). [251]
   3. Le frecce sono le misurazioni. [253]
   4. L'ordine di applicazione va da sinistra a destra. [254]
2. Esempio di circuito: stato iniziale $|001⟩$, poi porte X e H applicate al secondo qubit. [258]

6.2. Porte Multi-Qubit: CNOT e Toffoli [264]

1. Porta CNOT (Controlled-X): Agisce su due qubit (controllo e target). [265]
   1. Applica una porta X al target solo se il controllo è $|1⟩$. [269]
2. La CNOT si applica a ogni stato di sovrapposizione individualmente. [270]
3. Porta Toffoli: Simile alla CNOT, ma ha due qubit di controllo. [272]
4. Si possono creare versioni controllate di altre porte (Y, Z, S, T, H). [276]
   1. Sono rappresentate con la porta base e una linea che indica il controllo. [277]

6.3. Misurazione Multi-Qubit e Collasso [279]

1. Per trovare la probabilità di misurare un singolo qubit come 1, si sommano le probabilità di tutti gli stati in cui quel qubit è 1. [279]
2. Quando si misura un qubit, il sistema collassa allo stato misurato. [282]
3. Se si rimuovono stati (perché il qubit misurato non corrisponde), le probabilità totali scendono sotto 1. [285]
4. Si usa una costante di normalizzazione ($A$) per riportare la somma delle probabilità a 1. [286]
5. Esempio con tre qubit: se il qubit centrale è misurato come 0, lo stato collassa e viene normalizzato. [290]

7. Entanglement e Fenomeni Avanzati [299]

7.1. Entanglement (Intreccio) [299]

1. Se misurando un qubit si conosce immediatamente lo stato dell'altro, c'è entanglement. [299]
2. Uno stato è entangled se non può essere fattorizzato come prodotto tensore di stati singoli. [302]
3. Stati Massimamente Entangled (Bell States): Misurare un qubit determina lo stato degli altri. [305]
   1. Esempio: $\frac{1}{\sqrt{2}}(|00⟩+|11⟩)$ è massimamente entangled. [306]
4. Stati Parzialmente Entangled: La misurazione influenza le probabilità o la fase degli altri qubit. [309]

7.2. Phase Kickback (Ritorno di Fase) [310]

1. Fenomeno che si verifica con un circuito contenente $|+⟩$ e un qubit target $V$, con un'operazione controllata $U$. [311]
2. Se $V$ è un autostato di $U$ (cioè $U|V⟩=e^{i\theta }|V⟩$), avviene il phase kickback. [314]
3. La fase $e^{i\theta }$ viene applicata al qubit di controllo (il primo qubit in $|+⟩$). [319]
4. Questo fenomeno è usato in alcuni algoritmi quantistici. [322]

7.3. Superdense Coding [323]

1. Protocollo che permette di inviare due bit classici usando un solo qubit. [324]
2. Richiede che Alice e Bob condividano due qubit massimamente entangled inizialmente. [325]
3. Alice opera sul suo qubit a seconda dei due bit che vuole inviare (00, 01, 10, 11). [331]
4. Alice invia il suo qubit a Bob. [336]
5. Bob applica prima una CNOT (controllo: qubit di Alice, target: suo qubit). [338]
6. Poi applica una Hadamard al qubit di Alice. [339]
7. Misurando entrambi i qubit, Bob ottiene i due bit originali inviati da Alice. [340]

8. Reversibilità e Applicazione di Funzioni [344]

8.1. Operazioni Classiche e Reversibilità [344]

1. Operazioni classiche su bit: AND, OR, NOT, XOR (esclusivo OR). [345]
2. NOT: Inverte il bit (tabella di verità $X\to f(X)$). [346]
3. AND: Restituisce 1 solo se entrambi gli input sono 1. [350]
4. OR: Restituisce 1 se almeno uno degli input è 1. [353]
5. XOR: Restituisce 1 se gli input sono diversi (0 se uguali). [355]
6. L'operazione XOR è usata per rendere reversibili le porte classiche. [358]
7. Una funzione $f$ è Reversibile se, dato $f(x)$, si può determinare $x$. [359]
   1. OR non è reversibile (output 1 può venire da input 01, 10, 11). [360]
8. Per rendere reversibile una porta, si aggiunge un bit di input $C$ e si restituisce $X$ e $C\oplus f(X)$. [362]
   1. L'OR diventa reversibile con questo metodo. [364]
9. Importanza: Tutte le operazioni QC (tranne la misurazione) devono essere reversibili (unitari). [368]

8.2. Funzioni Quantistiche e Phase Oracle [372]

1. Le funzioni quantistiche devono essere reversibili. [373]
2. Tecnica: Input $X$ e $Y$, output $X$ e $Y\oplus f(X)$. [375]
   1. Se si imposta $Y=0$, l'output è $X$ e $f(X)$ (si interroga la funzione). [377]
3. La funzione $f$ è codificata in una matrice unitaria $U_f$. [380]
4. Applicando $U_f$ allo stato $|X0⟩$, si ottiene $|X,F(X)⟩$. [382]
5. Phase Oracle: Se il secondo registro (output) è nello stato $|-⟩$, si ottiene una fase. [383]
   1. Lo stato finale è $-1^{f(x)}|x-⟩$. [395]
   2. Questo è chiamato phase oracle. [396]

9. Teorema No-Cloning e Algoritmo di Deutsch [398]

9.1. Teorema No-Cloning [398]

1. Copiare bit classici è facile leggendo e scrivendo. [399]
2. Non si può copiare uno stato quantistico sconosciuto (es. $\alpha |0⟩+\beta |1⟩$). [399]
3. Se si conoscono $\alpha$ e $\beta$, la copia è possibile. [401]

9.2. Algoritmo di Deutsch [402]

1. Problema: Data una funzione $f$ a 1 bit (input $\to$ output), determinare se è costante o bilanciata. [403]
   1. Costante: Stesso output per tutti gli input (es. $f(x)=0$ o $f(x)=1$). [409]
   2. Bilanciata: Metà input danno 0, metà danno 1 (es. Identità o NOT). [411]
2. Classicamente: Richiede 2 query ($f(0)$ e $f(1)$). [415]
3. Quantummente (Deutsch): Richiede una sola query. [418]
4. Circuito: [419]
   1. Inizialmente $|00⟩$. [421]
   2. Si applica Hadamard a entrambi i qubit: $|+⟩|-⟩$. [422]
   3. Si applica la funzione $U_f$ (come phase oracle). [425]
   4. Lo stato diventa $\frac{1}{\sqrt{2}}(-1{)}^{f(0)}|0-⟩+\frac{1}{\sqrt{2}}(-1{)}^{f(1)}|1-⟩$. [429]
   5. Caso Costante ($f(0)=f(1)$): Lo stato finale è $|+⟩$. [430]
   6. Caso Bilanciato ($f(0)\ne f(1)$): Lo stato finale è $|-⟩$. [431]
   7. Si applica Hadamard all'input (primo qubit). [437]
   8. Se era $|+⟩$, diventa $|0⟩$. [438]
   9. Se era $|-⟩$, diventa $|1⟩$. [438]
   10. Misurando il primo qubit: 0 $⟹$ Costante; 1 $⟹$ Bilanciata. [439]

10. Algoritmi Generalizzati: Deutsch-Jozsa e Bernstein-Vazirani [443]

10.1. Algoritmo di Deutsch-Jozsa (DJ) [443]

1. DJ risolve lo stesso problema di Deutsch, ma per funzioni che accettano $N$ bit in input. [443]
2. Classicamente: Richiede fino a $2^{N-1}+1$ query nel caso peggiore. [450]
3. Quantummente: Richiede una sola query. [455]
4. Circuito: Simile a Deutsch, ma con $N$ qubit di input. [456]
   1. Si applica Hadamard a tutti gli $N$ qubit iniziali $|0{⟩}^{\otimes N}$. [457]
   2. Identità Importante: Hadamard su $|0{⟩}^{\otimes N}$ crea una superposizione uniforme di tutti i $2^N$ bit string. [461]
   3. Si applica la funzione $U_f$ (come phase oracle). [475]
   4. Si applica Hadamard a tutti gli $N$ qubit di input. [480]
   5. Si usa una nuova identità per l'Hadamard su un bit string arbitrario $X$. [484]
   6. Si analizza l'ampiezza dello stato $|0{⟩}^{\otimes N}$. [495]
   7. Se $f$ è costante, l'ampiezza è $\pm 1$. Probabilità di misurare $|0{⟩}^{\otimes N}$ è 1. [501]
   8. Se $f$ è bilanciata, l'ampiezza è 0. Probabilità di misurare $|0{⟩}^{\otimes N}$ è 0. [505]
5. Misurando $|0{⟩}^{\otimes N}$ si conferma che è costante; altro $⟹$ bilanciata. [513]

10.2. Algoritmo di Bernstein-Vazirani (BV) [517]

1. Problema: Data $f(x)=x\cdot S(\mathrm{mod}2)$ (prodotto scalare), trovare la stringa segreta $S$. [518]
2. Classicamente: Richiede $N$ query (una per ogni bit di $S$). [520]
3. Quantummente: Richiede una sola query. [523]
4. Circuito: Uguale a DJ, ma la funzione $U_f$ usa il qubit target nello stato $|-⟩$. [524]
   1. Lo stato finale (dopo $U_f$) è proporzionale a ${\sum }_x(-1{)}^{x\cdot S}|x-⟩$. [529]
   2. Si applica Hadamard a tutti i qubit di input. [532]
   3. Si usa l'identità che porta a ${\sum }_z(-1{)}^{(S+Z)\cdot X}|Z⟩$. [533]
5. Risultato: L'ampiezza dello stato $|S⟩$ è 1. [540]
6. Misurando i qubit si ottiene direttamente la stringa segreta $S$ con probabilità 1. [546]

10.3. Quantum Fourier Transform (QFT) [550]

1. QFT e Quantum Phase Estimation (QPE) sono usati in molti algoritmi (es. Shor). [550]
2. QFT: Trasforma la codifica binaria (fasi) in codifica di fase. [552]
   1. In input, i numeri sono codificati in binario (0 o 1 per qubit). [554]
   2. In output, i numeri sono codificati nella fase dei qubit in sovrapposizione uniforme. [557]
   3. Il qubit più a destra ha $2^N$ possibili posizioni di fase. [560]
3. Esempio (Numero 5, $N=3$): [562]
   1. Il qubit più a destra ruota di $5/8\times 2\pi$ radianti. [563]
   2. Il qubit successivo ruota del doppio, e così via. [564]
4. Circuito QFT: Usa porte Controlled-R e Swap. [567]
   1. Controlled-R$_k$: Applica una fase relativa $e^{2\pi i/2^k}$ se il controllo è 1. [570]
   2. Swap: Scambia gli stati di due qubit. [574]
5. Applicando QFT a uno stato base $|J⟩$, si ottiene una formula generale che codifica $J$ nelle fasi. [593]
6. Inverse QFT: Annulla la trasformazione QFT. [594]

10.4. Quantum Phase Estimation (QPE) [597]

1. QPE trova l'autovalore ($e^{i\theta }$) di un autovettore ($V$) data una matrice $U$. [596]
2. QPE è cruciale per l'algoritmo di Shor. [599]
3. Circuito QPE: Due registri: $M$ qubit per la fase stimata, $N$ qubit ($V$) per l'autovettore. [600]
4. Passaggi: [606]
   1. Hadamard sui qubit del primo registro (fase). [607]
   2. Applicare $U^{2^k}$ controllato dal $k$-esimo qubit del primo registro, con $V$ come target. [607]
   3. Si verifica il phase kickback su ogni qubit di controllo. [608]
   4. Lo stato finale ha fasi che dipendono da $J$, dove $\theta =2\pi J$. [611]
   5. Si applica l'Inverse QFT al primo registro. [621]
5. Misurando il primo registro si ottiene $J$ (approssimazione di $S/R$ in Shor). [623]

10.5. Algoritmo di Shor [625]

1. Shor fattorizza un numero grande $N=PQ$ (dove $P,Q$ sono primi). [626]
2. Questo potrebbe rompere la crittografia RSA. [628]
3. Passo Classico: Scegliere $A$ tale che $\text{GCD}(A,N)=1$. [631]
4. Passo Quantistico: Trovare il periodo $R$ dell'esponenziazione modulare $A^x(\mathrm{mod}N)$. [635]
   1. $R$ è il più piccolo intero tale che $A^R\equiv 1(\mathrm{mod}N)$. [639]
5. Costruzione della Porta $U$: Trasforma $|x⟩\to |xA(\mathrm{mod}N)⟩$. [643]
6. Applicando $U$ allo stato $|1⟩$ ripetutamente si ottengono le potenze di $A$. [645]
7. Lo stato $|1⟩$ (che è $1(\mathrm{mod}N)$) è un autovettore di $U$ con autovalore $e^{2\pi iS/R}$. [652]
   1. $S/R$ è la fase che QPE può stimare. [653]
8. Si costruisce uno stato di sovrapposizione uniforme di tutti gli stati $|U^s⟩$. [654]
9. Circuito: È QPE, dove l'autovettore è $|1(\mathrm{mod}N)⟩$. [660]
   1. QPE restituisce un valore decimale $J\approx S/R$. [665]
10. Passo Classico Finale: Usare la tecnica delle frazioni continue per stimare $S$ e $R$ da $J$. [666]
    1. Si cerca una frazione $R<N$. [672]
11. Fattorizzazione: Usando $R$, si calcolano $\text{GCD}(A^{R/2}-1,N)$ e $\text{GCD}(A^{R/2}+1,N)$. [675]
    1. Questi GCD hanno alta probabilità di contenere i fattori $P$ e $Q$. [678]
12. Esempio $N=15$: Scegliendo $A=7$, si trova $R=4$. I fattori sono $\text{GCD}(7^2-1,15)=3$ e $\text{GCD}(7^2+1,15)=5$. [680]