Algorithme de Bernstein-Vazirani

L'algorithme de Bernstein–Vazirani, qui résout le problème de Bernstein–Vazirani est un algorithme quantique inventé par Ethan Bernstein et Umesh Vazirani en 1992.

C'est une version restreinte de l'algorithme de Deutsch-Jozsa dans laquelle, au lieu de distinguer deux classes de fonctions, on essaie de retrouver une chaîne secrète encodée dans une fonction. Il a été conçu pour prouver la distinction entre les classes de complexité BQP et BPP.

Enoncé du problème

Soit un oracle qui implémente une fonction $f:\{0,1{\}}^n\to \{0,1\}$ dans laquelle $f(x)$ est un produit scalaire entre $x$ et une chaîne secrète $s\in \{0,1{\}}^n$ modulo 2, $f(x)=x\cdot s=x_1{s}_1\oplus x_2{s}_2\oplus \cdots \oplus x_n{s}_n$. Quelle est la valeur de $s$ ?

Algorithme

En informatique "classique", la méthode la plus efficace pour retrouver la chaîne secrète consiste à évaluer la fonction $n$ fois avec comme valeurs d'entrée $x=2^i$ pour tout $i\in \{0,1,...,n-1\}$ :

$\begin{array}{cc}f(1000\cdots 0_n)& =s_1\\ f(0100\cdots 0_n)& =s_2\\ f(0010\cdots 0_n)& =s_3\\ & ⋮\\ f(0000\cdots 1_n)& =s_n\\ \end{array}$

Avec un calculateur quantique, une seule requête sera suffisante :

Appliquer une transformée de Hadamard aux $n$ qubits $|0{⟩}^{\otimes n}$ pour obtenir :

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

Ensuite, appliquer l'oracle $U_f$ qui transforme $|x⟩\to (-1{)}^{f(x)}|x⟩$. Cela peut être simulé au moyen de l'oracle standard qui transforme $|b⟩|x⟩\to |b\oplus f(x)⟩|x⟩$ en appliquant l'oracle à $\frac{|0⟩-|1⟩}{\sqrt{2}}|x⟩$ ($\oplus$ représente une addition modulo 2).

Cela transforme la superposition en :

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

Une nouvelle transformée de Hadamard est appliquée à chaque qubit, de telle sorte que :

• pour les qubits où $s_i=1$, l'état est converti de $|-⟩$ à $|1⟩$
• pour les qubits où $s_i=0$, l'état est converti de $|+⟩$ à $|0⟩$

Pour obtenir $s$, une mesure selon la base standard ($\{|0⟩,|1⟩\}$) est effectuée sur les qubits.

L'algorithme peut donc être représenté ainsi, où $H^{\otimes n}$ représente la transformée de Hadamard sur $n$ qubits :

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

La raison pour laquelle l'état final est $|s⟩$ est que, pour un $y$ donné :

$\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{ si }s\oplus y=\overrightarrow{0},0\text{ sinon}.$

Puisque $s\oplus y=\overrightarrow{0}$ est vrai seulement quand $s=y$, cela signifie que la seule amplitude non nulle correspond à $|s⟩$.