In questo articolo vedremo alcune caratteristiche di base dell’informatica quantistica, e in particolare vedremo come applicare funzioni classiche a stati quantistici.
Spazio dei bit e dei qubit
Consideriamo lo spazio classico $B_n = \{0,1\}^n$ delle sequenze di $n$ zero o uno. Lo spazio $\{0,1\}$ è lo spazio di un singolo bit, e quindi $B_n$ è lo spazio di $n$ bit classici. In pratica, una sequenza in $B_3$ può essere, ad esempio, $001$ oppure $111$ etc. L’intero spazio di due bit è $B_2=\{00, 01, 10, 11\}$. In generale $B_n$ ha $2^n$ elementi. Una funzione (classica) è quindi in generale una funzione $f: B_n \to B_m$.
In termini quantistici, abbiamo dei qubit invece che dei bit classici. Un qubit è una sovrapposizione quantistica $\alpha \ket{0} + \beta \ket{1}$ dei due possibili stati di un bit classico ($0$ o $1$). Poiché $\alpha$ e $\beta$ sono numeri complessi, lo spazio di un qubit è $\mathcal{H}_1 \equiv \C^2$. Lo spazio di $k$ qubit è il prodotto tensoriale di $k$ volte lo spazio di Hilbert di un qubit, ovvero
$$\mathcal{H}_k = \underbrace{\mathcal{H}_1 \otimes \mathcal{H}_1 \otimes \cdots \otimes \mathcal{H}_1}_{k\,\mathrm{volte}} = (\C^2)^k$$
La dimensione dello spazio di $k$ qubit è $\mathrm{dim} \mathcal{H}_k = 2^k$. Notiamo che questa è la dimensione di uno spazio vettoriale ($\mathcal{H}_k$) che ha un numero infinito di elementi mentre nel caso classico $B_k$ ha $2^k$ elementi in totale. Una base ovvia per $\mathcal{H}_k$ è data da $\ket{x}=\ket{x_1}\ket{x_2}\cdots \ket{x_k}$ dove $x_i =0,1$, e quindi un elemento generico $\ket{\psi} \in \mathcal{H}_k$ è dato da una sovrapposizione $\ket{\psi} = \sum_x c_x \ket{x}$ dove $c_x$ sono numeri complessi. In particolare, gli elementi di base $x$ sono naturalmente in corrispondenza con i bit classici in $B_k$. Ad una sequenza di $k$ bit classici $x_1 x_2 \cdots x_k \in B_k$ con $x_i \in \{0,1\}$ associamo l’elemento di base $\ket{x}=\ket{x_1}\ket{x_2}\cdots \ket{x_k}$.
Operazioni unitarie per funzioni classiche biettive
Ora la domanda è la seguente: come facciamo ad applicare una funzione classica $f: B_k \to B_k$ ad uno stato quantistico $\ket{\psi} \in \mathcal{H}_k$? Poiché le sequenze di $k$ bit classici sono in corrispondenza con gli elementi di base di $\mathcal{H}_k$, è naturale definire un operatore quantistico $A_f$ che semplicemente applica $f$ ad ogni elemento di base, $A_f : \ket{x} \to \ket{f(x)}$; possiamo poi estendere $A_f$ linearmente a tutto $\mathcal{H}_k$. Ad esempio se $k=3$ e $f(010)=110$, allora poniamo $A_f \ket{010} = \ket{110}$. Il problema con questa operazione è che $A_f$ non è in generale unitaria, né in realtà invertibile, ed è proprio nell’unitarietà che sta la forza delle operazioni quantistiche.
Sotto quali condizioni $A_f$ è unitaria? Innanzitutto è chiaro che, se ad esempio $f$ è costante, allora tutti gli elementi di base verranno mandati allo stesso elemento, che non può spannare l’intero $\mathcal{H}_k$. Ciò vuol dire che se $A_f$ dev’essere unitaria, allora applicando $A_f$ all’insieme degli stati di base $\{\ket{x} \}$ dobbiamo ottenerli di nuovo tutti, quindi in particolare $f: B_k \to B_k$ deve essere suriettiva. Poiché $B_k$ è un insieme finito e $f$ è suriettiva, allora dev’essere anche biettiva. Per definizione, una funzione biettiva su un insieme finito è una permutazione, quindi $f$ dev’essere una permutazione degli elementi di base. Ma sappiamo che le matrici di permutazione sono unitarie, perciò $A_f$ è unitaria. Abbiamo perciò ottenuto il seguente risultato:
Proposizione. La mappa quantistica $A_f: \mathcal{H}_k \to \mathcal{H}_k$ definita da $A_f \ket{x} = \ket{f(x)}$ su una base $\{\ket{x} \}$ ed estesa linearmente è unitaria se e solo se $f$ è biettiva.
Possiamo fare un esempio nel caso $B_2=\{00, 01, 10, 11\}$. $f$ è una permutazione se restituisce gli stessi elementi in un ordine diverso, ad esempio
$$f(00) = 01 \quad f(01) = 10 \quad f(10) = 11 \quad f(11)=00$$
Mentre invece se $f$ ad esempio restituisse lo stesso valore per due input diversi allora non sarebbe biettiva e quindi non sarebbe una permutazione.
Operazioni unitarie per funzioni classiche non-biettive
A volte vogliamo applicare funzioni classiche $f$ che non sono biettive, oppure funzioni $f: B_n \to B_m$, ovvero funzioni che partono e arrivano in spazi di sequenze diversi. Come facciamo a implementare funzioni non biettive? È possibile utilizzare il risultato precedente insieme ad un trucco. Ovvero consideriamo lo spazio esteso $B_{n+m}$ e la funzione
$$\widetilde{f}: B_{n+m} \to B_{n+m} \quad \quad \widetilde{f}: (x,y) \to (x, y \oplus f(x))$$
dove $x \in B_n$ e $y \in B_m$. Poiché $f: B_n \to B_m$, allora $f(x)$ è una sequenza di $m$ bit, così come $y$ e perciò possiamo calcolarne l’addizione binaria bit per bit $\oplus$ con $f(x)$. L’addizione binaria è definita per $y=(y_1, y_2, \ldots, y_m)$ e $z=(z_1, z_2, \ldots, z_m)$ ponendo $y \oplus z = (y_1 \oplus z_1, y_2 \oplus z_2, \ldots, y_m \oplus z_m)$ dove per ogni $y_i \in \{0,1\}$ e ogni $z_i \in \{0,1\}$, l’operazione $y_i \oplus z_i$ è semplicemente l’addizione modulo due, ovvero $0 \oplus 0 = 0$, $0 \oplus 1 = 1 \oplus 0 = 1$, $1 \oplus 1 = 0$.
Il punto di questa operazione è che $\widetilde{f}$ è sempre biettiva indipendentemente da $f$, che può essere biettiva o meno. A tal scopo notiamo che nell’addizione binaria, $0 \oplus 0 =1 \oplus 1= 0$, perciò sommare due volte lo stesso numero è uguale a sommare zero, ovvero $y_i \oplus z_i \oplus z_i = y_i$ (dove appunto $\oplus$ è chiaramente associativa). Perciò applicando due volte $\widetilde{f}$ abbiamo
$$\widetilde{f}^2 (x,y) = \widetilde{f}(x, y \oplus f(x)) = (x, y \oplus f(x) \oplus f(x)) = (x,y)$$
Ciò vuol dire che $\widetilde{f}^2$ è l’identità, ovvero $\widetilde{f}$ è l’inversa di se stessa e quindi in particolare è biettiva. Perciò possiamo applicare la proposizione precedente a $\widetilde{f}$, il che darà luogo ad una mappa unitaria $U_f$, cioè
Proposizione. Data una funzione $f: B_n \to B_m$ qualsiasi, allora la mappa $U_f: \mathcal{H}_{n+m}\to \mathcal{H}_{n+m}$ data da $U_f \ket{x}\ket{y} = \ket{x} \ket{y \oplus f(x)}$ su una base ed estesa linearmente è unitaria.
dove appunto $\ket{x} \in \mathcal{H}_n$ e $\ket{y} \in \mathcal{H}_m$, analogamente a prima, sono gli elementi di base che abbiamo descritto per i rispettivi spazi.
Questa costruzione ci permette perciò di applicare una funzione classica su uno spazio quantistico. Infatti, poiché $00\cdots 0 \oplus y=y$ abbiamo
$$ U_f \ket{x} \ket{00\cdots 0} = \ket{x} \ket{f(x)}$$
E in particolare applicando $U_f$ ad una sovrapposizione di stati di base, otteniamo tutti i valori di $f(x)$ in un colpo solo,
$$U_f \sum_x \ket{x} \ket{00\cdots 0} = \sum_x \ket{x} \ket{f(x)}$$
Chiaramente poi non è ovvio come estrarli in maniera efficiente, perché dovremmo comunque effettuare molte misurazioni per estrarre tutti i valori nella sovrapposizione. Notiamo infine che lo stato $\sum_x \ket{x}$ a cui applichiamo $U_f$ contiene un numero esponenziale di termini, ovvero $2^k$ in $\mathcal{H}_k$. Tuttavia può essere realizzato applicando solamente $k$ porte di Hadamard, che in particolare soddisfano
$$H: \ket{0} \to \frac{\ket{0}+\ket{1}}{\sqrt{2}}$$
e quindi agendo sui $k$ qubit,
$$H \otimes H \cdots \otimes H \ket{0 0 \cdots 0} = \underbrace{\pqty{\frac{\ket{0}+\ket{1}}{\sqrt{2}}} \pqty{\frac{\ket{0}+\ket{1}}{\sqrt{2}}} \cdots \pqty{\frac{\ket{0}+\ket{1}}{\sqrt{2}}} }_{k\,\mathrm{volte}} = \frac{1}{2^{k/2}}\sum_x \ket{x} $$
perché appunto moltiplicando i termini al centro otteniamo tutte le possibili sequenze di $k$ zero e uno. Perciò lo stato $\sum_x \ket{x} \ket{f(x)}$ può essere realizzato utilizzando un numero lineare di porte quantistiche, nonostante contenga un numero esponenziale di termini.