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.[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  .


A generalization of Bernstein–Vazirani problem has been proposed that involves finding one or more secret keys using a probabilistic oracle. [3] 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.

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. arXiv:1710.01378. doi:10.1088/1367-2630/aab341.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  3. ^ Alok Shukla and Prakash Vedula (2023). "A generalization of Bernstein--Vazirani algorithm with multiple secret keys and a probabilistic oracle". Quantum Information Processing. 22:244 (6): 1–18. arXiv:2301.10014. doi:10.1007/s11128-023-03978-3.