Bernstein–Vazirani algorithm – Wikipedia

Quantum algorithm

The Bernstein–Vazirani algorithm, which solves the Bernstein–Vazirani problem, is a quantum algorithm invented by Ethan Bernstein and Umesh Vazirani in 1992.^[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[edit]

Given an oracle that implements a function

${displaystyle fcolon {0,1}^{n}rightarrow {0,1}}$

in which

${displaystyle f(x)}$

is promised to be the dot product between

${displaystyle x}$

and a secret string

${displaystyle sin {0,1}^{n}}$

modulo 2,

${displaystyle f(x)=xcdot s=x_{1}s_{1}oplus x_{2}s_{2}oplus cdots oplus x_{n}s_{n}}$

, find

${displaystyle s}$

.

Algorithm[edit]

Classically, the most efficient method to find the secret string is by evaluating the function

${displaystyle n}$

times with the input values

${displaystyle x=2^{i}}$

for all

${displaystyle iin {0,1,…,n-1}}$

:^[2]

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

In contrast to the classical solution which needs at least

${displaystyle n}$

queries of the function to find

${displaystyle s}$

, only one query is needed using quantum computing. The quantum algorithm is as follows: ^[2]

Apply a Hadamard transform to the

${displaystyle n}$

qubit state

${displaystyle |0rangle ^{otimes n}}$

to get

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

Next, apply the oracle

${displaystyle U_{f}}$

which transforms

${displaystyle |xrangle to (-1)^{f(x)}|xrangle }$

. This can be simulated through the standard oracle that transforms

${displaystyle |brangle |xrangle to |boplus f(x)rangle |xrangle }$

by applying this oracle to

${displaystyle {frac {|0rangle -|1rangle }{sqrt {2}}}|xrangle }$

. (

${displaystyle oplus }$

denotes addition mod two.) This transforms the superposition into

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

Another Hadamard transform is applied to each qubit which makes it so that for qubits where

${displaystyle s_{i}=1}$

, its state is converted from

${displaystyle |-rangle }$

to

${displaystyle |1rangle }$

and for qubits where

${displaystyle s_{i}=0}$

, its state is converted from

${displaystyle |+rangle }$

to

${displaystyle |0rangle }$

. To obtain

${displaystyle s}$

, a measurement in the standard basis (

${displaystyle {|0rangle ,|1rangle }}$

) is performed on the qubits.

Graphically, the algorithm may be represented by the following diagram, where

${displaystyle H^{otimes n}}$

denotes the Hadamard transform on

${displaystyle n}$

qubits:

${displaystyle |0rangle ^{n}xrightarrow {H^{otimes n}} {frac {1}{sqrt {2^{n}}}}sum _{xin {0,1}^{n}}|xrangle xrightarrow {U_{f}} {frac {1}{sqrt {2^{n}}}}sum _{xin {0,1}^{n}}(-1)^{f(x)}|xrangle xrightarrow {H^{otimes n}} {frac {1}{2^{n}}}sum _{x,yin {0,1}^{n}}(-1)^{f(x)+xcdot y}|yrangle =|srangle }$

The reason that the last state is

${displaystyle |srangle }$

is because, for a particular

${displaystyle y}$

,

${displaystyle {frac {1}{2^{n}}}sum _{xin {0,1}^{n}}(-1)^{f(x)+xcdot y}={frac {1}{2^{n}}}sum _{xin {0,1}^{n}}(-1)^{xcdot s+xcdot y}={frac {1}{2^{n}}}sum _{xin {0,1}^{n}}(-1)^{xcdot (soplus y)}=1{text{ if }}soplus y={vec {0}},,0{text{ otherwise}}.}$

Since

${displaystyle soplus y={vec {0}}}$

is only true when

${displaystyle s=y}$

, this means that the only non-zero amplitude is on

${displaystyle |srangle }$

. So, measuring the output of the circuit in the computational basis yields the secret string

${displaystyle s}$

.

See also[edit]

References[edit]