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. 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. The Bernstein–Vazirani algorithm was designed to prove an oracle separation between complexity classes BQP and BPP.
Problem statement
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
Classically, the most efficient method to find the secret string is by evaluating the function times with the input values for all :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:
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. 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.
A generalization of Bernstein–Vazirani problem has been proposed that involves finding one or more secret keys using a probabilistic oracle.
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.
Classical ''vs.'' quantum complexity
The Bernstein-Vazirani problem is usually stated in its [|non-decision version]. In this form, it is an example of a problem solvable by a Quantum Turing machine with queries to the problem's oracle, but for which any Probabilistic Turing machine algorithm must make queries.To provide a separation between BQP and BPP, the problem must be reshaped into a decision problem. This is accomplished with a recursive construction and the inclusion of a second, random oracle.
The resulting decision problem is solvable by a QTM with queries to the problem's oracle, while a PTM must make queries to solve the same problem. Therefore, Bernstein-Vazirani provides a super-polynomial separation between BPP and BQP.