L'algoritmo di Bernstein–Vazirani, che risolve il problema di Bernstein–Vazirani è un algoritmo quantistico inventato da Ethan Bernstein e Umesh Vazirani nel 1992. Si tratta di un caso particolare dell'algoritmo di Deutsch-Jozsa dove invece di distinguere due diverse classi di funzioni, cerca di conoscere una stringa codificata in una funzione. L'algoritmo di Bernstein–Vazirani fu ideato per dimostrare una separazione degli oracoli tra le classi di complessità BQP e BPP.
Enunciato del problema Dato un oracolo che implementa una funzione in cui è il prodotto scalare modulo 2 tra e una stringa segreta , , trovare .
Algoritmo Classicamente, il metodo più efficiente per trovare la stringa segreta è valutare la funzione volte con i valori di input per ogni :
In contrasto alla soluzione classica che necessita di almeno chiamate alla funzione per trovare , usando la computazione quantistica, solo una chiamata è necessaria. L'algoritmo quantistico è il seguente:
Si comincia dallo stato a qubit , su cui si applica la porta di Hadamard per ottenere
Dopo, si applica l'oracolo che trasforma lo stato . Questo effetto si ottiene dalla trasformazione ( denota la somma mod 2.) dove lo stato su cui si copia la funzione è
.
Questo trasforma la sovrapposizione in
Si applica un'altra trasformata di Hadamard a ogni qubit. Essa, per i qubit dove , trasforma lo stato da a e per i qubit dove , trasforma lo stato da a . Per ottenere , viene fatta una misura nella base standard () sui qubit.
Graficamente, l'algoritmo può essere rappresentato dal seguente diagramma, dove denota la porta di Hadamard su qubit:
Il motivo per cui l'ultimo stato è è perché, per una particolare ,
Siccome è vera solo per , ciò significa che l'unica ampiezza non nulla è su . Quindi, misurando l'output del circuito nella base standard, si ottiene con certezza la stringa segreta .
Note
Categoria:Teoria della complessità computazionale Bernstein