Английская Википедия:Bernstein–Vazirani algorithm
The Bernstein–Vazirani algorithm, which solves the Bernstein–Vazirani problem, is a quantum algorithm invented by Ethan Bernstein and Umesh Vazirani in 1997.[1] It is a restricted version of the Deutsch–Jozsa algorithm where instead of distinguishing between two different classes of functions, it tries to learn a string encoded in a function.[2] The Bernstein–Vazirani algorithm was designed to prove an oracle separation between complexity classes BQP and BPP.[1]
Problem statement
Given an oracle that implements a function <math>f\colon\{0,1\}^n\rightarrow \{0,1\}</math> in which <math>f(x)</math> is promised to be the dot product between <math>x</math> and a secret string <math> s \in \{0,1\}^n</math> modulo 2, <math> f(x) = x \cdot s = x_1s_1 \oplus x_2s_2 \oplus \cdots \oplus x_ns_n</math>, find <math>s</math>.
Algorithm
Classically, the most efficient method to find the secret string is by evaluating the function <math>n</math> times with the input values <math>x = 2^{i}</math> for all <math>i \in \{0, 1, ..., n-1\}</math>:[2]
- <math>\begin{align}
f(1000\cdots0_n) & = s_1 \\ f(0100\cdots0_n) & = s_2 \\ f(0010\cdots0_n) & = s_3 \\ & \,\,\,\vdots \\ f(0000\cdots1_n) & = s_n \\ \end{align}</math>
In contrast to the classical solution which needs at least <math>n</math> queries of the function to find <math>s</math>, only one query is needed using quantum computing. The quantum algorithm is as follows: [2]
Apply a Hadamard transform to the <math>n</math> qubit state <math>|0\rangle^{\otimes n} </math> to get
- <math>\frac{1}{\sqrt{2^{n}}}\sum_{x=0}^{2^n-1} |x\rangle.</math>
Next, apply the oracle <math>U_f</math> which transforms <math>|x\rangle \to (-1)^{f(x)}|x\rangle</math>. This can be simulated through the standard oracle that transforms <math>|b\rangle|x\rangle \to |b \oplus f(x)\rangle |x\rangle</math> by applying this oracle to <math>\frac{|0\rangle - |1\rangle}{\sqrt{2}}|x\rangle</math>. (<math>\oplus</math> denotes addition mod two.) This transforms the superposition into
- <math>\frac{1}{\sqrt{2^{n}}}\sum_{x=0}^{2^n-1} (-1)^{f(x)} |x\rangle.</math>
Another Hadamard transform is applied to each qubit which makes it so that for qubits where <math>s_i = 1</math>, its state is converted from <math>|-\rangle</math> to <math>|1\rangle </math> and for qubits where <math>s_i = 0</math>, its state is converted from <math>|+\rangle</math> to <math>|0\rangle </math>. To obtain <math>s</math>, a measurement in the standard basis (<math>\{|0\rangle, |1\rangle\}</math>) is performed on the qubits.
Graphically, the algorithm may be represented by the following diagram, where <math>H^{\otimes n}</math> denotes the Hadamard transform on <math>n</math> qubits:
- <math>
|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
</math>
The reason that the last state is <math>|s\rangle</math> is because, for a particular <math>y</math>,
- <math>
\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{ otherwise}.
</math> Since <math>s \oplus y = \vec{0}</math> is only true when <math>s = y</math>, this means that the only non-zero amplitude is on <math>|s\rangle</math>. So, measuring the output of the circuit in the computational basis yields the secret string <math>s</math>.
A generalization of Bernstein–Vazirani problem has been proposed that involves finding one or more secret keys using a probabilistic oracle.
[3]
This is an interesting problem for which a quantum algorithm can provide efficient solutions with certainty or with a high degree of confidence, while classical algorithms completely fail to solve the problem in the general case.
See also
References
