Bernstein–Vazirani algorithm

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
Bernstein-Vazirani quantum circuit.png

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]

  1. ^ a b Ethan Bernstein and Umesh Vazirani (1997). "Quantum Complexity Theory". SIAM Journal on Computing. 26 (5): 1411–1473. doi:10.1137/S0097539796300921.
  2. ^ 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.{{cite journal}}: CS1 maint: multiple names: authors list (link)