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
in which
is promised to be the dot product between
and a secret string
modulo 2,
, find
.
Algorithm[edit]
Classically, the most efficient method to find the secret string is by evaluating the function
times with the input values
for all
:[2]
-
In contrast to the classical solution which needs at least
queries of the function to find
, only one query is needed using quantum computing. The quantum algorithm is as follows: [2]
Apply a Hadamard transform to the
qubit state
to get
-
Next, apply the oracle
which transforms
. This can be simulated through the standard oracle that transforms
by applying this oracle to
. (
denotes addition mod two.) This transforms the superposition into
-
Another Hadamard transform is applied to each qubit which makes it so that for qubits where
, its state is converted from
to
and for qubits where
, its state is converted from
to
. To obtain
, a measurement in the standard basis (
) is performed on the qubits.
Graphically, the algorithm may be represented by the following diagram, where
denotes the Hadamard transform on
qubits:
-
The reason that the last state is
is because, for a particular
,
-
Since
is only true when
, this means that the only non-zero amplitude is on
. So, measuring the output of the circuit in the computational basis yields the secret string
.
See also[edit]
References[edit]
Recent Comments