Algoritmo di Bernstein-Vazirani

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

Dato un oracolo che implementa una funzione ${\displaystyle f\colon \{0,1\}^{n}\rightarrow \{0,1\}}$ in cui ${\displaystyle f(x)}$ è il prodotto scalare modulo 2 tra ${\displaystyle x}$ e una stringa segreta ${\displaystyle s\in \{0,1\}^{n}}$ , ${\displaystyle f(x)=x\cdot s=x_{1}s_{1}+x_{2}s_{2}+\cdots +x_{n}s_{n}}$, trovare ${\displaystyle s}$.

Algoritmo

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

${\displaystyle {\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 ${\displaystyle n}$ chiamate alla funzione per trovare ${\displaystyle s}$, usando la computazione quantistica, solo una chiamata è necessaria. L'algoritmo quantistico è il seguente:^[2]

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

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

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

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

Questo trasforma la sovrapposizione in

${\displaystyle {\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 ${\displaystyle s_{i}=1}$, trasforma lo stato da ${\displaystyle |-\rangle }$ a ${\displaystyle |1\rangle }$ e per i qubit dove ${\displaystyle s_{i}=0}$, trasforma lo stato da ${\displaystyle |+\rangle }$ a ${\displaystyle |0\rangle }$. Per ottenere ${\displaystyle s}$, viene fatta una misura nella base standard (${\displaystyle \{|0\rangle ,|1\rangle \}}$) sui qubit.

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

${\displaystyle |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 è ${\displaystyle |s\rangle }$ è perché, per una particolare ${\displaystyle y}$,

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