Algoritmo di Bernstein-Vazirani

algoritmo quantistico

L'algoritmo di Bernstein–Vazirani, che risolve il problema di Bernstein–Vazirani è un algoritmo quantistico inventato da Ethan Bernstein e Umesh Vazirani nel 1992.[1] 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.[2] L'algoritmo di Bernstein–Vazirani fu ideato per dimostrare una separazione degli oracoli tra le classi di complessità BQP e BPP.

Circuito quantistico dell'algoritmo

Enunciato del problema

modifica

Dato un oracolo che implementa una funzione   in cui   è il prodotto scalare modulo 2 tra   e una stringa segreta   ,  , trovare  .

Algoritmo

modifica

Classicamente, il metodo più efficiente per trovare la stringa segreta è valutare la funzione   volte con i valori di input   per ogni  :[2]

 

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:[2]

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  .

  1. ^ Ethan Bernstein e Umesh Vazirani, Quantum Complexity Theory, in SIAM Journal on Computing, vol. 26, n. 5, 1997, pp. 1411–1473, DOI:10.1137/S0097539796300921.
  2. ^ a b c S D Fallek, C D Herold, B J McMahon, K M Maller, K R Brown, e J M Amini, Transport implementation of the Bernstein–Vazirani algorithm with ion qubits, in New Journal of Physics, vol. 18, 2016, DOI:10.1088/1367-2630/aab341.