Gruppo TIM
Gruppo TIM

Il Qubit: introduzione agli algoritmi quantistici

Introduzione

Talvolta, in contesti divulgativi il computer quantistico viene etichettato come un particolare computer “incredibilmente più veloce”. Sebbene tale considerazione non sia del tutto lontana dalla realtà, è doveroso fare alcune precisazioni.

Il computer quantistico è strutturalmente distinto da un computer classico, tanto che la logica che ne determina i processi interni si allontana da quella comune, in quanto descrivibile solo grazie alle leggi della meccanica quantistica.

Ai fini di evidenziare gli aspetti di innovazione portati dal modello di calcolo quantistico, è necessario procedere con un richiamo al modello di calcolo classico ovvero al metodo di elaborazione delle informazioni da parte degli odierni computer.

La codifica del dato avviene attraverso sequenze di bit. Un singolo bit rappresenta l’unità di informazione classica ed è descritto da due stati possibili 0 e 1, pertanto qualsiasi dato elaborato da un computer è rappresentato come stringa binaria (successione di 0 e 1).

L’elemento di maggior distinzione si identifica proprio nella differente unità di informazione adottata da un processore quantistico, il concetto classico di bit viene superato e generalizzato da quello di bit quantistico o qubit.

Gli stati quantistici che descrivono il qubit non si limitano ai soli valori di 0 e 1, come accade per il bit, ma possono assumere infinite configurazioni intermedie realizzando quel fenomeno che in meccanica quantistica viene chiamato superposizione.

Sfruttando questo fenomeno, la comunità scientifica ha ideato alcuni algoritmi tramite i quali il computer quantistico è in grado di calcolare un certo risultato in un numero di passi molto minore rispetto alle controparti classiche.

Con il supporto del formalismo matematico, di seguito si procederà con una trattazione tecnica del qubit e del quantum computing. Infine, si darà un esempio di speed up (riduzione costo computazionale) quantistico rispetto all’approccio classico per la risoluzione di un particolare problema.

Definizione di Qubit

Gli stati quantistici di 0 e 1 sono indicati con i simboli[1] |0\rangle e |1\rangle. Un generico qubit è dato da una combinazione lineare di questi due simboli |\psi\rangle:=\alpha|0\rangle + \beta|1\rangle\text{ con }\alpha,\beta\in\mathbb{C}, ove i coefficienti \alpha e \beta rispettano la relazione |\alpha|^2+|\beta|^2=1. Questa costrizione sui coefficienti consente di associare ad |\alpha|^2 (risp. |\beta|^2) la probabilità di osservazione dello stato |0\rangle (risp. |1\rangle).

I qubit sono spesso rappresentati come punti della cosiddetta sfera di Bloch.

01_Bloch

Misura o osservazione

Il termine osservazione risulta particolarmente importante in questo contesto. In fisica si definisce osservabile una qualsiasi grandezza che è in qualche modo misurabile direttamente tramite tecniche opportune, pertanto di seguito osservazione e misura saranno trattate come sinonimi.

Nella distinzione fra meccanica classica e quantistica questo concetto è determinante. In meccanica classica la misurazione non ha alcun effetto sul sistema, in quanto descrive qualcosa di preesistente senza alterarlo. Ad esempio, si pensi ad un corridore di cui si rileva la velocità: è ovvio che la misurazione non condizionerà l’osservabile (velocità in questo caso) in alcun istante di tempo.

In meccanica quantistica, invece, l’osservazione di una superposizione di stati quantistici fa collassare in modo irreversibile il sistema ad uno stato particolare. Conseguenza di ciò, è che lo stato quantistico originario nella sua interezza risulta un’entità inaccessibile a qualunque strumento di misura.

Infatti, nel quantum computing, dato un qubit |\psi\rangle non è possibile stabilire con esattezza i valori \alpha e \beta che lo determinano. In genere, l’unica cosa che si può sperare di fare è riprodurre più volte |\psi\rangle, misurare e stimare le probabilità sulla base della frequenza di 0 e 1 come risultati.

Riassumendo, il circuito quantistico riceve in ingresso il qubit |\psi\rangle
02_measure
e restituisce, trasformando irreversibilmente il qubit, \begin{aligned}|0\rangle\text{ con probabilità } |\alpha|^2, \\ |1\rangle \text{ con probabilità } |\beta|^2.\end{aligned}

Gate quantistici

Prima di procedere con la descrizione delle trasformazioni caratterizzanti i circuiti quantistici, si espone da un punto di vista formale la concatenazione di più qubit. Siano |\psi_1\rangle=\alpha_1|0\rangle+\beta_1|1\rangle e |\psi_2\rangle=\alpha_2|0\rangle+\beta_2|1\rangle due qubit, la loro concatenazione \begin{aligned}|\psi_1\psi_2\rangle & := |\psi_1\rangle|\psi_2\rangle=\left(\alpha_1|0\rangle+\beta_1|1\rangle\right)\left(\alpha_2|0\rangle+\beta_2|1\rangle\right) \\ & = \alpha_1\alpha_2|00\rangle + \alpha_1\beta_2|01\rangle + \beta_1\alpha_2|10\rangle + \beta_1\beta_2|11\rangle\end{aligned} è un 2-qubit e si noti che i coefficienti dei simboli |00\rangle,|01\rangle,|10\rangle,|11\rangle sono ancora interpretabili come probabilità in quanto |\alpha_1\alpha_2|^2+|\alpha_1\beta_2|^2+|\beta_1\alpha_2|^2+|\beta_1\beta_2|^2=1.

Le operazioni (gate quantistici) attraverso cui è possibile manipolare i qubit sono perlopiù un’estensione delle porte logiche utilizzate nella computazione classica con il vincolo che la trasformazione di un qubit deve preservare la relazione fra i suoi coefficienti (si parla di trasformazione unitaria).

Formalmente, una trasformazione fra 1-qubit T: \alpha|0\rangle+\beta|1\rangle \longmapsto \alpha'|0\rangle+\beta'|1\rangle, deve soddisfare |\alpha'|^2+|\beta'|^2=1. In modo analogo, tale relazione è mantenuta nel caso di n-qubit.

Di seguito sono elencati i gate più ricorrenti nella costruzione di circuiti quantistici. Se ne riporta l’azione applicata a |0\rangle, |1\rangle nel caso degli 1-qubit e a |00\rangle,\dots,|11\rangle nel caso dei 2-qubit, tale azione si estende per linearità a qubit generici.

Il gate X o \bigoplus descrive l’operazione NOT sugli 1-qubit.
03_not
Il gate \bullet\!\!-\!\!\!\bigoplus descrive l’operazione CNOT e agisce sullo stato di un 2-qubit come un NOT sulla seconda entrata solo se il valore della prima è 1.
04_cnot
Il gate \times\!\!\!\!-\!\!\!-\!\!\! \times descrive l’operazione SWAP e agisce scambiando lo stato di un 2-qubit.
05_swap
Si noti che i precedenti gate quantistici corrispondono ad operazioni aventi una costruzione equivalente nel caso classico. Ad evidenziare le differenze tra il modello computazionale classico e quello quantistico sono i gate quantistici che per costruzione non possono avere un equivalente nel caso classico.

Ad esempio, il gate Hadamard H serve a realizzare il fenomeno della superposizione (uniforme). Infatti, se applicato a |0\rangle oppure |1\rangle restituisce un qubit che può assumere entrambi i valori con equa probabilità.
06_hadamard
Il gate R_{\theta} agisce esclusivamente sul coefficiente di |1\rangle.
07_phase
Si noti che l’insieme di gate esposti è sufficiente a descrivere qualsiasi gate quantistico agente su un generico n-qubit. Un insieme di gate con questa peculiarità viene detto universale.

Infine, data una funzione f:\{0,1\}^n\rightarrow\{0,1\}^m si definisce il gate U_f per la sua valutazione,

08_bool

ove in questo caso l’operazione \oplus denota l’usuale XOR.

Algoritmo di Deutsch-Jozsa

Si fornisce ora un esempio che dà una prima intuizione riguardo le potenzialità del calcolo quantistico presentando uno speed up rispetto al modello classico. Si considerino le funzioni \begin{aligned}b_1:\{0,1\} & \longrightarrow\{0,1\} & c_1:\{0,1\} & \longrightarrow\{0,1\} \\0&\longmapsto 0&0&\longmapsto 0\\1&\longmapsto 1&1 &\longmapsto 0\\[5pt] b_2:\{0,1\} & \longrightarrow\{0,1\} &c_2:\{0,1\} &\longrightarrow\{0,1\} \\0 &\longmapsto 1 & 0 &\longmapsto 1\\ 1 & \longmapsto 0 & 1& \longmapsto 1\end{aligned} b_1, b_2 sono dette bilanciate, in quanto al variare di tutti i possibili input restituiscono come risultato tanti 0 quanti 1, formalmente |b_i^{-1}(0)|=|b_i^{-1}(1)|, mentre c_1, c_2 sono dette costanti in quanto indipendentemente dall’input restituiscono lo stesso output.

Consideriamo il seguente problema: sia f una funzione di cui si sa solo essere appartenente all’insieme \{b_1,b_2,c_1,c_2\}, f è bilanciata o costante?

Nel modello di computazione classico, dato un oracolo O_f per il calcolo di f, il problema è risolto applicando l’oracolo alla metà di tutti gli input possibili più 1, il che corrisponde nel caso 1-dimensionale a 2 e nel caso n-dimensionale a 2^{n-1}+1.

L’algoritmo quantistico di Deutsch-Josza risolve il problema individuato tramite il seguente circuito, combinando i gate quantistici U_f e H introdotti precedentemente.
09_DJ
Tramite tale algoritmo, la soluzione al quesito richiede una singola esecuzione di U_f nel caso 1-dimensionale ed è semplice estendere la trattazione con il medesimo risultato al caso n-dimensionale. Pertanto, 1 applicazione di U_f contro 2^{n-1}+1 chiamate a O_f (nel caso n-dimensionale) mostra uno speed up esponenziale rispetto al caso classico.

Segue la dimostrazione.

1. Il gate H applicato ad entrambi i qubit agisce come di seguito. |01\rangle\longmapsto\frac{1}{2}\sum_{x\in \{0,1\}}|x\rangle\left(|0\rangle-|1\rangle\right) 2. Come anticipato il gate U_f corrisponde alla valutazione di f. \begin{aligned} \frac{1}{2}\sum_{x\in \{0,1\}}|x\rangle\left(|0\rangle-|1\rangle\right)\longmapsto & \frac{1}{2}\sum_{x\in \{0,1\}}|x\rangle\left(|f(x)\rangle-|1\oplus f(x)\rangle\right) \\ & = \frac{1}{2}\sum_{x\in \{0,1\}}(-1)^{f(x)}|x\rangle(|0\rangle-|1\rangle) \end{aligned} 3. Il gate H applicato ad entrambi i qubit calcola \frac{1}{2}\sum_{x\in \{0,1\}}(-1)^{f(x)}|x\rangle(|0\rangle-|1\rangle) \longmapsto \frac{1}{2}\sum_{x,y\in\{0,1\}}(-1)^{f(x)+\langle x,y \rangle}|y\rangle|1\rangle.4. La misura del primo qubit restituisce y\in\{0,1\} con probabilità \frac{1}{2^{2}}\left|\sum_{x\in\{0,1\}}(-1)^{f(x)+\langle x,y \rangle}\right|^2. Nel caso in cui f sia costante si ottiene y=0 con probabilità \frac{1}{2^{2}}\left|\sum_{x\in\{0,1\}}(-1)^{f(x)+\langle x,y \rangle}\right|^2=\frac{1}{2^{2}}\left|\sum_{x\in\{0,1\}}(-1)^{\text{const}+0}\right|^2=1, mentre nel caso in cui f sia bilanciata la probabilità di ottenere y=1 è \frac{1}{2^{2}}\left|\sum_{x\in\{0,1\}}(-1)^{f(x)+\langle x,y \rangle}\right|^2=\frac{1}{2^{2}}\left|\sum_{x\in\{0,1\}}(-1)^{f(x)+x}\right|^2=1. Di conseguenza, il risultato della misura del primo qubit è discriminante rispetto alla natura della funzione f: nel caso in cui sia costante si otterrà sicuramente 0 come risultato, mentre nel caso in cui sia bilanciata il risultato certo corrisponde a 1. Una discussione del tutto analoga è valida nel caso n-dimensionale, ovvero nel caso di f:\{0,1\}^n\to\{0,1\}, sempre applicando il gate U_f un’unica volta.


[1] Da un punto di vista matematico questi simboli rappresentano dei vettori nello spazio di Hilbert \mathbb{C}^2. Tale approfondimento teorico non sarà oggetto del presente articolo.

[2] Entità che permette di valutare la funzione f senza conoscerla.


Per altri articoli relativi ai temi Quantum e Crittografia si rimanda alle relative categorie nel blog.

Gli autori

Veronica Cristiano, laureata triennale in Matematica presso l’Università di Pisa e laureata magistrale in Matematica con specializzazione in Crittografia presso l’Università di Trento, entrata a far parte del gruppo di ricerca in Crittografia di Telsy a metà del 2021.

Francesco Stocco, laureato magistrale in Matematica presso l’Università degli Studi di Padova e l’Université de Bordeaux frequentando il percorso di studi “Algebra Geometry And Number Theory” (ALGANT), entrato a far parte del gruppo di ricerca in Crittografia di Telsy alla fine del 2020 occupandosi in particolare di temi inerenti alle tecnologie quantistiche.

13