L’algoritmo di Deutsch-Jozsa

L’algoritmo di Deutsch-Jozsa è stato storicamente il primo algoritmo quantistico che ha dimostrato un miglioramento esponenziale di complessità computazionale rispetto al migliore algoritmo classico. Sebbene non sia particolarmente utile, è comunque interessante come esempio particolarmente semplice di come i computer quantistici possono essere più efficienti di quelli classici.

Consideriamo una funzione $f: \{0,1\}^n \to \{0,1\}$. Ovvero $f$ è una funzione che prende in ingresso una sequenza di $n$ bit classici e restituisce un bit (cioè $0$ o $1$). Ad esempio per $n=3$ potremmo avere $f(010)=0$, oppure $f(111)=0$ e così via. Ora consideriamo due tipi di funzioni:

• funzioni costanti, cioè $f: \{0,1\}^n \to \{0,1\}$ dà sempre lo stesso risultato, indipendentemente dall’input. Esistono solo due funzioni del genere: $f(x)=0$ per ogni $x$ e $f(x)=1$ per ogni $x$.
• funzioni bilanciate. In cui $f: \{0,1\}^n \to \{0,1\}$ soddisfa $f(x)=1$ per esattamente metà degli input $x \in \{0,1\}^n$, mentre invece soddisfa $f(x)=0$ per l’altra metà.

Ora il problema che vogliamo risolvere è il seguente: ci è data una funzione $f: \{0,1\}^n \to \{0,1\}$ e sappiamo che è o costante o bilanciata. Dobbiamo determinare quale delle due.  Sappiamo necessariamente quindi che $f$ è una delle due, e dobbiamo quindi determinare se è costante oppure se è bilanciata.

Algoritmo classico

L’algoritmo classico per risolvere il problema è il seguente: ovvero calcoliamo $f(x)$ per un certo numero di input $x \in \{0,1\}^n$, il minor numero possibile per poter decidere se $f$ è costante e bilanciata. Nel migliore dei casi è necessario calcolare $f$ due sole volte: ovvero prendendo due input a caso, se $f$ una volta restituisce $1$ e l’altra $0$, allora sappiamo che non è costante, e quindi è bilanciata.

Tuttavia dobbiamo considerare anche il peggiore dei casi. Questo si verifica quando calcolando $f(x)$ per vari $x$ continuiamo ad ottenere lo stesso risultato, così da non poter decidere se è costante o bilanciata. Tuttavia se $f$ non è costante, allora potremo ottenere lo stesso risultato al massimo metà delle volte, perché se $f$ non è costante, allora è bilanciata. Il numero delle sequenze $\{0,1\}^n$ è $2^n$, perché abbiamo due scelte $n$ volte. Perciò metà dello spazio è $2^n/2 = 2^{n-1}$. Perciò nel peggiore dei casi troveremo lo stesso risultato $2^{n-1}$ volte, ma a quel punto basterà calcolare $f$ una volta in più: se otterremo di nuovo lo stesso risultato, allora $f$ è costante, altrimenti sarà bilanciata.

Ciò implica che dovremo calcolare $f$ un numero di volte pari a $2^{n-1}+1$ nel peggiore dei casi, che è quindi la complessità computazionale dell’algoritmo.

Algoritmo quantistico

Lo stesso problema può essere risolto da un computer quantistico calcolando $f$ esattamente una volta nel peggiore dei casi. Ciò vuol dire che mentre l’algoritmo classico richiede tempo esponenziale (e quindi intrattabile per $n$ grande), l’algoritmo quantistico richiede tempo costante (e quindi se $n$ è grande o piccolo non fa differenza). Vediamo come funziona.

In questo caso consideriamo lo spazio $\mathcal{H}_{n+1}$ di $n+1$ qubit quantistici. Abbiamo visto in un precedente articolo che la nostra funzione classica $f$ può essere implementata in $\mathcal{H}_{n+1}$ da un operatore unitario $U_f$ definito su una base da

$$U_f \ket{x} \ket{y} = \ket{x} \ket{y \oplus f(x)}$$

ed esteso linearmente, dove $\ket{x}=\ket{x_1 x_2 \ldots x_n}$ con $x_i=0,1$ è un elemento della base di $\mathcal{H}_n$ data dalle sequenze di $n$ bit, e $y=0,1$ invece è un solo qubit.

Ora la cosa intelligente da fare è considerare una specifica sovrapposizione e applicarci $U_f$. Infatti abbiamo

$$U_f \ket{x} \frac{\ket{0} -\ket{1}}{\sqrt{2}} =\ket{x} \frac{\ket{f(x)} -\ket{1 \oplus f(x)}}{\sqrt{2}} = (-1)^{f(x)} \ket{x} \frac{\ket{0} -\ket{1}}{\sqrt{2}}$$

Ciò perché appunto $f(x)=0,1$ e possiamo controllare esplicitamente i due casi. Perciò prendendo la sovrapposizione su tutti questi stati,

$$U_f \sum_x \ket{x} \frac{\ket{0} -\ket{1}}{\sqrt{2}} = \sum_x (-1)^{f(x)} \ket{x} \frac{\ket{0} -\ket{1}}{\sqrt{2}}$$

Poiché l’ultimo qubit è invariato possiamo ignorarlo, e abbiamo quindi una procedura per ottenere

$$\frac{1}{2^{n/2}} \sum_x \ket{x} \to \frac{1}{2^{n/2}} \sum_x (-1)^{f(x)} \ket{x} \equiv \ket{\eta_f}$$

Possiamo ripetere la costruzione per un’altra funzione $g$ ottenendo un altro stato $\ket{\eta_g}$. Abbiamo che $\expval{\eta_f | \eta_g} = \frac{1}{2^n}\sum_x (-1)^{f(x)+g(x)}$, perciò se $f$ è costante e $g$ è bilanciata, allora $\expval{\eta_f | \eta_g}=0$, perché il segno di $f$ è irrilevante e metà dei segni di $g$ darà $+1$ e l’altra metà $-1$. Perciò gli stati corrispondenti alle funzioni bilanciate e alle funzioni costanti sono ortogonali.

Per concludere l’algoritmo effettuiamo una misurazione, e per fare ciò ruotiamo di nuovo nella base computazionale. Avevamo notato nel precedente articolo che

$$H \otimes H \otimes \cdots \otimes H \ket{00\cdots 0} = \frac{1}{2^{n/2}}\sum_{x} \ket{x}$$

dove $H$ sono porte di Hadamard. Poiché $H^2=1$ possiamo applicare di nuovo la stessa operazione e tornare nella base computazionale, ovvero

$$H \otimes H \otimes \cdots \otimes H \sum_{x} \ket{x}  = 2^{n/2}\ket{00\cdots 0}$$

In particolare per $f$ costante allora $(-1)^{f(x)} \equiv \pm 1$ costante, e quindi

$$H \otimes H \otimes \cdots \otimes H \ket{\eta_f} = \pm \ket{00\cdots 0}$$

Se $f$ è costante e $g$ è bilanciata allora come abbiamo visto $\ket{\eta_f}$ e $\ket{\eta_g}$ sono ortogonali; perciò poiché $H$ è unitaria allora i due stati rimangono ortogonali anche applicando $H$ agli stati. Ciò implica che applicando $H \otimes H \otimes \cdots \otimes H$ ad $\ket{\eta_g}$ otterremo uno stato ortogonale a $\ket{00\cdots 0}$. Perciò ora possiamo misurare i qubit: se otteniamo tutti $0$ allora la funzione è necessariamente costante, mentre invece se otteniamo qualcos’altro allora la funzione è necessariamente bilanciata. Ciò richiede una sola misurazione di ognuno dei qubit. Infatti poiché gli stati sono ortogonali, qualunque cosa sia $\ket{\eta_g}$ nella base computazionale, non potrà contenere nessun $\ket{00\cdots 0}$.

L’algoritmo è riassunto nel seguente circuito quantistico:

Partiamo da $n$ qubit posizionati a $0$ e da un qubit posizionato a $1$. Applichiamo quindi $H^{\otimes n}=H \otimes H \otimes \cdots H$ ai primi $n$ qubit per ottenere la sovrapposizione $\frac{1}{2^{n/2}}\sum_{x} \ket{x}$ e applichiamo invece $H$ al qubit $\ket{1}$ per ottenere la sovrapposizione $\frac{\ket{0} -\ket{1}}{\sqrt{2}}$. Applichiamo quindi $U_f$ come descritto e poi di nuovo $H^{\otimes n}$ per tornare alla base computazionale. Infine misuriamo gli $n$ qubit. In totale perciò utilizziamo $2n+1$ porte di Hadamard, un’applicazione di $U_f$ e $n$ misurazioni, tutti numeri lineari in $n$. In particolare ricordiamo che nel caso classico avremmo avuto bisogno di un numero esponenziale di applicazioni di $f$, mentre nel caso quantistico abbiamo applicato $U_f$ una volta sola.

In conclusione notiamo che mentre l’algoritmo quantistico è essenzialmente ottimale (non possiamo fare meglio di una sola applicazione di $f$), possiamo rilassare le condizioni sull’algoritmo classico per renderlo più efficiente. Ad esempio se richiediamo che l’algoritmo dia la risposta esatta con probabilità $p < 1$ e non con certezza, allora anche l’algoritmo classico riesce a dare una risposta in tempo costante con $n$ e non più esponenziale.