Bernstein–Vazirani algorithm explained

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. The Bernstein–Vazirani algorithm was designed to prove an oracle separation between complexity classes BQP and BPP.^[1]

Problem statement

Given an oracle that implements a function

f\colon\{ 0 , 1 \} ^{n →} \{ 0 , 1 \} in which f(x) is promised to be the dot product between x and a secret string s \in \{ 0 , 1 \} ^{n} modulo 2, f(x) = x ⋅ s = x _{1s} _{1} ⊕ x _{2s} _{2} ⊕ … ⊕ x _{ns} _{n} , find s .

Algorithm

Classically, the most efficient method to find the secret string is by evaluating the function

n times with the input values x = 2 ^{i} for all i \in \{ 0 , 1 , ..., n -1 \} :^[2] \begin{align} f( 1000 … 0 _{n)} & = s _{1} \\ f( 0100 … 0 _{n)} & = s _{2} \\ f( 0010 … 0 _{n)} & = s _{3} \\ & \vdots \\ f( 0000 … 1 _{n)} & = s _{n} \\ \end{align}

In contrast to the classical solution which needs at least

n queries of the function to find s , only one query is needed using quantum computing. The quantum algorithm is as follows: ^[2]

Apply a Hadamard transform to the

n qubit state | 0 \rangle ^{⊗} to get (1)/(\sqrt{ 2 ^{n}) }\sum_^ |x\rangle.

Next, apply the oracle

U _{f} which transforms |x\rangle \to ( -1 ) ^{f(x)} |x\rangle . This can be simulated through the standard oracle that transforms |b\rangle|x\rangle \to |b ⊕ f(x)\rangle |x\rangle by applying this oracle to (| 0 \rangle - | 1 \rangle)/(\sqrt{ 2) }|x\rangle. (⊕ denotes addition mod two.) This transforms the superposition into(1)/(\sqrt{ 2 ^{n}) }\sum_^ (-1)^ |x\rangle.

Another Hadamard transform is applied to each qubit which makes it so that for qubits where

s _{i} = 1 , its state is converted from | - \rangle to | 1 \rangle and for qubits where s _{i} = 0 , its state is converted from | + \rangle to | 0 \rangle . To obtain s , a measurement in the standard basis (\{| 0 \rangle, | 1 \rangle\} ) is performed on the qubits.

Graphically, the algorithm may be represented by the following diagram, where

H ^{⊗} denotes the Hadamard transform on n qubits:| 0 \rangle ^{n} \xrightarrow{H ^{⊗} } \frac \sum_ |x\rangle \xrightarrow \frac\sum_(-1)^|x\rangle \xrightarrow \frac \sum_(-1)^|y\rangle = |s\rangle

The reason that the last state is

|s\rangle is because, for a particular y ,(1)/(2 ^{n}) \sum ^{n}( -1 )} _{x \in \{ 0 , 1 \} ^{f(x)} = (1)/(2 ^{n}) \sum ^{n}( -1 )} _{x \in \{ 0 , 1 \} ^{x ⋅} = (1)/(2 ^{n}) \sum ^{n}( -1 )} _{x \in \{ 0 , 1 \} ^{x ⋅} = 1 if s ⊕ y = \vec{ 0 }, 0 otherwise . Since s ⊕ y = \vec{ 0 } is only true when s = y , this means that the only non-zero amplitude is on |s\rangle . So, measuring the output of the circuit in the computational basis yields the secret string s .

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

• Hidden Linear Function problem

Notes and References

1. . Quantum Complexity Theory . SIAM Journal on Computing . 26 . 5 . 1411–1473 . 1997 . 10.1137/S0097539796300921 .
2. S D Fallek, C D Herold, B J McMahon, K M Maller, K R Brown, and J M Amini . Transport implementation of the Bernstein–Vazirani algorithm with ion qubits . New Journal of Physics . 18 . 2016 . 10.1088/1367-2630/aab341 . free . 1710.01378 .
3. Alok Shukla and Prakash Vedula . A generalization of Bernstein--Vazirani algorithm with multiple secret keys and a probabilistic oracle . Quantum Information Processing . 22:244 . 6 . 1-18 . 2023 . 10.1007/s11128-023-03978-3 . 2301.10014 .