Algoritmo di Bernstein-Vazirani

Circuito quantistico dell'algoritmo

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 $f\colon \{0,1\}^{n}\rightarrow \{0,1\}$ in cui $f(x)$ è il prodotto scalare modulo 2 tra $x$ e una stringa segreta $s\in \{0,1\}^{n}$ , $f(x)=x\cdot s=x_{1}s_{1}+x_{2}s_{2}+\cdots +x_{n}s_{n}$, trovare $s$.

Algoritmo

Classicamente, il metodo più efficiente per trovare la stringa segreta è valutare la funzione $n$ volte con i valori di input $x=2^{i}$ per ogni $i\in \{0,1,...,n-1\}$:

${\begin{aligned}f(1000\cdots 0_{n})&=s_{1}\\f(0100\cdots 0_{n})&=s_{2}\\f(0010\cdots 0_{n})&=s_{3}\\&\,\,\,\vdots \\f(0000\cdots 1_{n})&=s_{n}\\\end{aligned}}$

In contrasto alla soluzione classica che necessita di almeno $n$ chiamate alla funzione per trovare $s$, usando la computazione quantistica, solo una chiamata è necessaria. L'algoritmo quantistico è il seguente:

Si comincia dallo stato a $n$ qubit $|0\rangle ^{\otimes n}$, su cui si applica la porta di Hadamard per ottenere

${\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}|x\rangle .$

Dopo, si applica l'oracolo $U_{f}$ che trasforma lo stato $|x\rangle \to (-1)^{f(x)}|x\rangle$. Questo effetto si ottiene dalla trasformazione $|b\rangle |x\rangle \to |b\oplus f(x)\rangle |x\rangle$ ($\oplus$ denota la somma mod 2.) dove lo stato su cui si copia la funzione è

$|b\rangle ={\frac {|0\rangle -|1\rangle }{\sqrt {2}}}$.

Questo trasforma la sovrapposizione in

${\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}|x\rangle .$

Si applica un'altra trasformata di Hadamard a ogni qubit. Essa, per i qubit dove $s_{i}=1$, trasforma lo stato da $|-\rangle$ a $|1\rangle$ e per i qubit dove $s_{i}=0$, trasforma lo stato da $|+\rangle$ a $|0\rangle$. Per ottenere $s$, viene fatta una misura nella base standard ($\{|0\rangle ,|1\rangle \}$) sui qubit.

Graficamente, l'algoritmo può essere rappresentato dal seguente diagramma, dove $H^{\otimes n}$ denota la porta di Hadamard su $n$ qubit:

$|0\rangle ^{n}\xrightarrow {H^{\otimes n}} {\frac {1}{\sqrt {2^{n}}}}\sum _{x\in \{0,1\}^{n}}|x\rangle \xrightarrow {U_{f}} {\frac {1}{\sqrt {2^{n}}}}\sum _{x\in \{0,1\}^{n}}(-1)^{f(x)}|x\rangle \xrightarrow {H^{\otimes n}} {\frac {1}{2^{n}}}\sum _{x,y\in \{0,1\}^{n}}(-1)^{f(x)+x\cdot y}|y\rangle =|s\rangle$

Il motivo per cui l'ultimo stato è $|s\rangle$ è perché, per una particolare $y$,

${\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}(-1)^{f(x)+x\cdot y}={\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}(-1)^{x\cdot s+x\cdot y}={\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}(-1)^{x\cdot (s\oplus y)}=1{\text{ se }}s\oplus y={\vec {0}},\,0{\text{ altrimenti}}.$

Siccome $s\oplus y={\vec {0}}$ è vera solo per $s=y$, ciò significa che l'unica ampiezza non nulla è su $|s\rangle$. Quindi, misurando l'output del circuito nella base standard, si ottiene con certezza la stringa segreta $s$.