Bernstein–Vazirani algorithm
![Bernstein-Vazirani quantum circuit.png](http://upload.wikimedia.org/wikipedia/commons/thumb/1/15/Bernstein-Vazirani_quantum_circuit.png/220px-Bernstein-Vazirani_quantum_circuit.png)
The Bernstein–Vazirani algorithm, which solves the Bernstein–Vazirani problem is a quantum algorithm invented by and Umesh Vazirani in 1992.[1] It's 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 between complexity classes BQP and BPP.[1]
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 :[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[]
- Hidden Linear Function problem
References[]
- ^ Jump up to: a b and Umesh Vazirani (1997). "Quantum Complexity Theory". SIAM Journal on Computing. 26 (5): 1411–1473. doi:10.1137/S0097539796300921.
- ^ Jump up to: a b c S D Fallek, C D Herold, B J McMahon, K M Maller, K R Brown, and J M Amini (2016). "Transport implementation of the Bernstein–Vazirani algorithm with ion qubits". New Journal of Physics. 18. doi:10.1088/1367-2630/aab341.CS1 maint: multiple names: authors list (link)
- Quantum algorithms
- Quantum complexity theory
- Computational complexity theory