FONDAMENTI E PRINCIPI DI ELABORAZIONE QUANTISTICA, SPIEGATI QUASI FACILI: L’ALGORITMO DI DEUTSCH-JOZSA E IL PROBLEMA DELLA SCATOLA NERA.

L’algoritmo quantistico di Deutsch-Jozsa è un algoritmo che permette di determinare se una funzione booleana è costante o bilanciata, sfruttando le proprietà della meccanica quantistica. Questo algoritmo è uno dei primi esempi di come un computer quantistico possa essere più efficiente di un computer classico per risolvere certi problemi, come quello della scatola nera (modello black-box).

Una funzione booleana è una funzione che prende in input una stringa di bit e restituisce un bit (0 o 1) come output. Una funzione booleana è costante se restituisce sempre lo stesso valore per qualsiasi input, mentre è bilanciata se restituisce 0 per metà degli input possibili e 1 per l’altra metà.

L’algoritmo classico per determinare se una funzione booleana è costante o bilanciata richiede di valutare la funzione per almeno la metà più uno degli input possibili, nel caso peggiore. Ad esempio, se la funzione prende in input 3 bit, bisogna valutarla per almeno 5 input su 8 possibili.

L’algoritmo quantistico di Deutsch-Jozsa, invece, richiede solo una valutazione della funzione, grazie all’uso di qubit e porte logiche quantistiche. Un qubit è un’unità di informazione quantistica che può assumere due stati di base, indicati con |0> e |1>, ma anche una sovrapposizione lineare di essi, indicata con a|0> + b|1>, dove a e b sono coefficienti complessi tali che |a|^2 + |b|^2 = 1. Una porta logica quantistica è un’operazione che trasforma uno o più qubit in altri qubit.

L’algoritmo di Deutsch-Jozsa si svolge in quattro passaggi:

1) Si preparano n+1 qubit, dove n è il numero di bit in input della funzione booleana. I primi n qubit sono inizializzati nello stato |0>, mentre l’ultimo qubit è inizializzato nello stato |1>.

2) Si applica una porta Hadamard a tutti i qubit. Una porta Hadamard trasforma uno stato di base |0> in una sovrapposizione (|0> + |1>)/sqrt(2) e uno stato di base |1> in una sovrapposizione (|0> – |1>)/sqrt(2). Dopo questo passaggio, i qubit sono nella sovrapposizione di tutti gli stati possibili.

3) Si applica la funzione booleana ai qubit usando una porta U_f che agisce come segue: U_f|x>|y> = |x>|y XOR f(x)>, dove x è una stringa di n bit, y è un bit e XOR è l’operazione di disgiunzione esclusiva. Dopo questo passaggio, i qubit sono nella sovrapposizione degli stati |x>|y XOR f(x)>.

4) Si applica nuovamente una porta Hadamard ai primi n qubit. Dopo questo passaggio, i qubit sono nella sovrapposizione degli stati |x + f(x)>|y XOR f(x)>, dove x + f(x) è la somma modulo 2 dei bit di x e f(x).

Infine, si misura il risultato sui primi n qubit. Se la funzione booleana è costante, il risultato sarà sempre |0>, mentre se la funzione booleana è bilanciata, il risultato sarà diverso da |0> con probabilità 1.

L’algoritmo quantistico di Deutsch-Jozsa dimostra che esistono problemi per i quali un computer quantistico può risparmiare molte risorse computazionali rispetto a un computer classico. Tuttavia, l’algoritmo non ha molta applicazione pratica, poiché le funzioni booleane costanti o bilanciate sono casi particolari e non molto interessanti. Altri algoritmi quantistici più generali e potenti sono stati sviluppati: si vedano ad esempio Shor e Grover.