FONDAMENTI E PRINCIPI DI ELABORAZIONE QUANTISTICA, SPIEGATI QUASI FACILI: L’ALGORITMO DI Bernstein-Vazirani

L’algoritmo di Bernstein-Vazirani è un particolare e specifico algoritmo quantistico, derivato dall’algoritmo di Deutsch-Jozsa, che permette di trovare una stringa segreta codificata in una funzione con una sola chiamata all’oracolo che implementa la funzione. Per oracolo, nel calcolo quantistico, si intende uno strumento (operatore) che consente di ottenere la valutazione di una funzione su un dato input senza conoscere la definizione della funzione stessa.

Questo algoritmo dimostra una separazione tra le classi di complessità BQP (Bounded-error Quantum Polynomial-time, “tempo polinomiale quantistico con errore limitato”) e BPP (Bounded-error Probabilistic Polynomial time, “tempo polinomiale probabilistico con errore limitato”), in quanto un algoritmo classico richiederebbe almeno n chiamate all’oracolo per trovare la stringa segreta di lunghezza n.

L’algoritmo si basa sulle proprietà della trasformata di Hadamard e del prodotto scalare modulo 2. L’idea è di preparare uno stato quantistico sovrapposto di tutti i possibili input della funzione e applicare l’oracolo su di esso. Poi, si applica nuovamente la trasformata di Hadamard su ogni qubit e si misura lo stato finale. Il risultato della misura sarà la stringa segreta cercata.

Per capire meglio il funzionamento dell’algoritmo, vediamo un esempio con n=3. Supponiamo che la stringa segreta sia s=101 e che la funzione f(x) sia il prodotto scalare modulo 2 tra x e s, ovvero f(x)=x·s mod 2.

L’algoritmo procede come segue:

1) Si parte dallo stato |000⟩|1⟩, dove il primo registro a tre qubit contiene l’input della funzione e il secondo registro a un qubit contiene l’output della funzione. Si applica la porta di Hadamard su tutti i qubit per ottenere lo stato:

|000⟩|1⟩ → 1/√8 (|000⟩ + |001⟩ + |010⟩ + |011⟩ + |100⟩ + |101⟩ + |110⟩ + |111⟩)(|0⟩ – |1⟩)

2) Si applica l’oracolo che implementa la funzione f(x) sullo stato precedente. L’oracolo aggiunge al secondo registro il valore di f(x) per ogni x nel primo registro, ottenendo lo stato:

1/√8 (|000⟩ + |001⟩ + |010⟩ + |011⟩ + |100⟩ + |101⟩ + |110⟩ + |111⟩)(|0⟩ – |1⟩) →
1/√8 (|000⟩(f(000) ⊕ 0 – f(000) ⊕ 1) + … + |111⟩(f(111) ⊕ 0 – f(111) ⊕ 1))

Sostituendo i valori di f(x), si ottiene

1/√8 (|000⟩(-1 – 1) + |001⟩(-1 – 1) + |010⟩(-1 – 1) + |011⟩(1 – (-1)) + |100⟩(1 – (-1)) + |101⟩(-1 – 1) + |110⟩(1 – (-1)) + |111⟩(-1 – 1))

Semplificando i termini nulli, si ottiene

-2/√8 (|011⟩ – |100⟩ + |110⟩)

3) Si applica nuovamente la porta di Hadamard su tutti i qubit del primo registro, ottenendo lo stato:

-2/√8 (|011⟩ – |100⟩ + |110⟩)(|0⟩ – |1⟩) →
-2/√8 (H(|011⟩) – H(|100⟩) + H(|110⟩))(|0⟩ – |1⟩)

Applicando le regole della trasformata di Hadamard, si ottiene

-2/√8 (|101⟩ – |-101⟩ + |-110⟩)(|0⟩ – |1⟩)

Semplificando i segni, si ottiene

-2/√8 (|101⟩ + |-101⟩ – |-110⟩)(|0⟩ – |1⟩)

4) Si misura il primo registro nella base computazionale, ottenendo con certezza il valore |101⟩, che corrisponde alla stringa segreta.

La specificità di questo algoritmo è nota e risolve un problema da cui l’algoritmo prende il nome; la sua esistenza è causata dalla necessità di dimostrare la separazione tra le classi di complessità BQP e BPP, rispetto all’applicazione dell’algoritmo classico: si tratta dunque di un esercizio di calcolo, che evidenzia le possibilità dell’elaborazione quantistica rispetto a quella classica in termini di complessità e costo.