Algorisme Bernstein-Vazirani

L'algorisme de Bernstein Vazirani en el model de circuit

L'algorisme de Bernstein–Vazirani, que resol el problema de Bernstein–Vazirani, és un algorisme quàntic inventat per Ethan Bernstein i Umesh Vazirani el 1997. És una versió restringida de l'algorisme Deutsch–Jozsa on en comptes de distingir entre dues classes diferents de funcions, intenta aprendre una cadena codificada en una funció. L'algorisme de Bernstein-Vazirani va ser dissenyat per demostrar una separació d'oracle entre les classes de complexitat BQP i BPP.

Esquema gràfic de l'algorisme de Bernstein-Vazirani

Declaració del problema

Donat un oracle que implementa una funció $f\colon \{0,1\}^{n}\rightarrow \{0,1\}$ en el qual $f(x)$ es promet que serà el producte puntual entre $x$ i una cadena secreta $s\in \{0,1\}^{n}$ mòdul 2, $f(x)=x\cdot s=x_{1}s_{1}\oplus x_{2}s_{2}\oplus \cdots \oplus x_{n}s_{n}$, trobar $s$.

Algorisme

Clàssicament, el mètode més eficient per trobar la cadena secreta és avaluar la funció $n$ vegades amb els valors d'entrada $x=2^{i}$ per a tots $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}}$

En contrast amb la solució clàssica que necessita almenys $n$ consultes de la funció a trobar $s$, només es necessita una consulta mitjançant la computació quàntica. L'algorisme quàntic és el següent:

Cal aplicar una transformació Hadamard al $n$ estat qubit $|0\rangle ^{\otimes n}$ per aconseguir

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

A continuació, apliqueu l'oracle $U_{f}$ que es transforma $|x\rangle \to (-1)^{f(x)}|x\rangle$. Això es pot simular mitjançant l'oracle estàndard que transforma $|b\rangle |x\rangle \to |b\oplus f(x)\rangle |x\rangle$ aplicant aquest oracle a ${\frac {|0\rangle -|1\rangle }{\sqrt {2}}}|x\rangle$. ( $\oplus$ denota addició mod dos.) Això transforma la superposició en

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

Una altra transformada Hadamard s'aplica a cada qubit, la qual cosa fa que sigui per a qubits on $s_{i}=1$, el seu estat es converteix de $|-\rangle$ a $|1\rangle$ i per a qubits on $s_{i}=0$, el seu estat es converteix de $|+\rangle$ a $|0\rangle$. Per obtenir $s$, una mesura en la base estàndard ( $\{|0\rangle ,|1\rangle \}$ ) es realitza als qubits.

Gràficament, l'algorisme es pot representar amb el diagrama següent, on $H^{\otimes n}$ denota la transformada de Hadamard $n$ qubits:

$|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$

El motiu pel qual és l'últim estat $|s\rangle$ és perquè, per a un particular $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{ if }}s\oplus y={\vec {0}},\,0{\text{ altrament}}.$

Des de $s\oplus y={\vec {0}}$ només és cert quan $s=y$, això vol dir que l'única amplitud diferent de zero està activada $|s\rangle$. Per tant, mesurant la sortida del circuit en la base computacional s'obté la cadena secreta $s$.

S'ha proposat una generalització del problema de Bernstein-Vazirani que implica trobar una o més claus secretes mitjançant un oracle probabilístic. Aquest és un problema interessant per al qual un algorisme quàntic pot proporcionar solucions eficients amb certesa o amb un alt grau de confiança, mentre que els algorismes clàssics no resolen completament el problema en el cas general.