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.