Skip to main content

View on GitHub

Open this notebook in GitHub to run it yourself
The Bernstein-Vazirani (BV) algorithm [1], [2], introduced by Ethan Bernstein and Umesh Vazirani, is a fundamental quantum algorithm that addresses a special case of the hidden-shift problem. It employs the same functional circuit structure as the Deutsch-Jozsa algorithm and achieves a linear speedup over its classical counterpart in the oracle query model. The algorithm treats the following problem:
  • Input: A Boolean function f:{0,1}n→{0,1}f: \{0,1\}^n \rightarrow \{0,1\} defined as
f(x)≡(x⋅a)  mod  2  ,f(x)\equiv (x\cdot a) \,\,\mod 2~~, where ⋅ \cdot refers to a bitwise dot operation, and aa is a binary string of length nn.
  • Promise:
  • Output: Returns the secret string aa with minimum inquiries of the function.
Complexity: The quantum approach requires a single query call, therefore, the quantum complexity query is O(1)O(1). In contrast, Classically, the minimum inquiries of the function ff for determining the secret string is nn: ff is called with these strings:
f(100…0)=a0 ,f(010…0)=a1 ,⋮f(00…01)=an−1 ,\begin{aligned} f(100\dots0) &= a_0~, \\ f(010\dots0) &= a_1~, \\ \vdots\\ f(00\dots01) &= a_{n-1}~, \end{aligned} which reveals the secret string, one bit at a time. If one allows for randomness, the expected number of queries remains linear in nn. >
Keywords: Hidden string problem, Foundational quantum algorithms, Oracle/Query complexity.
bv_qprog.png

Figure

  1. The Bernstein-Vazirani algorithm comprises three quantum blocks.

The main part of the algorithm is the implementation of the Bernstein-Vazirani predicate $f(x)\equiv (x\cdot a) \mod 2$.

​
How to Build the Algorithm with Classiq

The BV algorithm contains three function blocks: an oracle for the predicate ff, “sandwiched” between two Hadamard transforms. The resulting state corresponds to the secret string. The full mathematical derivation is at the end of this notebook.

​

​
Implementing the BV Predicate

A simple quantum implementation of the binary function f(x)f(x) applies a series of controlled-X operations: starting with the state ∣f⟩=∣0⟩|f\rangle=|0\rangle, we apply an X gate, controlled on the ∣xi⟩|x_i\rangle state, for all ii such that ai=1a_i=1: ∣x0…xn−1⟩∣0⟩f→Πi:ai=1CX(xi,f)∣x0…xn−1⟩∣0⟩f=∣x0…xn−1⟩Xa⋅x∣0⟩f=∣x0…xn−1⟩∣a⋅x( mod 2)⟩f. |x_0\dots x_{n-1}\rangle |0\rangle_f \rightarrow \Pi_{i: a_i=1} {\rm CX}(x_i,f) |x_0\dots x_{n-1}\rangle |0\rangle_f = |x_0\dots x_{n-1}\rangle X^{a\cdot x}|0\rangle_f=|x_0\dots x_{n-1}\rangle |a\cdot x \left(\text{ mod } 2\right)\rangle_f.
Figure 2 shows an example of such implementation, for a=01101a=01101 and n=5n=5. Screenshot 2025-06-19 at 22.14.13.png

Figure

  1. The Bernstein-Vazirani predicate $f(x)$ for a secret string $a=01101$, on $n$ qubits.

The quantum variable $x$ is stored on the five upper qubits and the resulting value of $f$ is on the lowermost qubit.

​

​
Implementing the BV Quantum Function

The quantum part of the BV algorithm is essentially identical to the deutsch_jozsa function in the Deutsch-Jozsa notebook. However, in contrast to the latter, the predicate function implementation is fixed, depending solely on the secret string aa. Hereafter, we refer to the secret string as a secret integer, defined as an integer argument for the bv_function:

​
An Example on Five Qubits

We construct a model for a specific example, setting the secret integer to a=13a=13 and n=5n=5. The algorithm requires only a single application of the quantum circuit, as in an ideal noiseless execution, the resulting quantum state corresponds exactly to the hidden integer (see the last Eq. (1) below). Even in the presence of noise, the idea of using only a single query call of ff has demonstrated algorithmic speedup in Ref. [3], where the authors considered a modified version of the BV algorithm in which the secret integer changes after every inquiry. In this example, we take num_shots=1000 to highlight the fact that the resulting state is purely the secret string.
We can now visualize the circuit:
Output:
Output:
We execute and extract the result:
Output:
Output:
Output:

​
Technical Notes

Here is a brief summary of the linear algebra behind the Bernstein-Vazirani algorithm. The first Hadamard transformation generates an equal superposition over all the standard basis elements: ∣0⟩n→H⊗n12n/2∑j=02n−1∣j⟩n.|0\rangle_n \xrightarrow[H^{\otimes n}]{} \frac{1}{2^{n/2}}\sum^{2^n-1}_{j=0}|j\rangle_n. The oracle gets the Boolean Bernstein-Vazirani predicate and adds an eπi=−1e^{\pi i}=-1 phase to all states for which the function returns true: 12n/2∑j=02n−1∣j⟩n→Oracle(f(j))12n/2∑j=02n−1(−1)a⋅j∣j⟩n.\frac{1}{2^{n/2}}\sum^{2^n-1}_{j=0}|j\rangle_n \xrightarrow[\text{Oracle}(f(j))]{}\frac{1}{2^{n/2}}\sum^{2^n-1}_{j=0}(-1)^{a\cdot j}|j\rangle_n. Finally, application of the Hadamard transform, which can be written as H⊗n≡12n/2∑k,l=02n−1(−1)k⋅l∣k⟩⟨l∣H^{\otimes n}\equiv \frac{1}{2^{n/2}}\sum^{2^n-1}_{k,l=0}(-1)^{k\cdot l} |k\rangle \langle l| , gives 12n/2∑j=02n−1(−1)a⋅j∣j⟩→H⊗n∑k=02n−1(12n∑j=02n−1(−1)j⋅(k⊕a))∣k⟩.\frac{1}{2^{n/2}}\sum^{2^n-1}_{j=0}(-1)^{a\cdot j}|j\rangle \xrightarrow[H^{\otimes n}]{} \sum^{2^n-1}_{k=0} \left(\frac{1}{2^{n}}\sum^{2^n-1}_{j=0}(-1)^{j\cdot \left(k\oplus a \right)} \right) |k\rangle. The final expression represents a superposition over all basis states ∣k⟩|k\rangle; however, we can verify that the amplitude of the state ∣k⟩=∣a⟩|k\rangle=|a\rangle is simply one, as a⊕a=0a\oplus a =0: (12n∑j=02n−11)∣a⟩+∑k≠a2n−10∣k⟩=∣a⟩.(1)\left(\frac{1}{2^{n}}\sum^{2^n-1}_{j=0}1 \right) |a\rangle + \sum^{2^n-1}_{k\neq a} 0 |k\rangle = |a\rangle. \tag{1} Therefore, the final state is the secret string.

​
References

[1]: Vazirani, Umesh, and E. Bernstein. Quantum complexity theory. Special issue on Quantum Computation of the Siam Journal of Computing 10 (1997) [2]: Bernstein-Vazirani (Wikipedia) [3]: Pokharel B., and Daniel A. L. Demonstration of algorithmic quantum speedup. Physical Review Letters 130, 210602 (2023)