The Bernstein-Vazirani Algorithm - Computational Approach

Learning objectives

The goal of this part of the lesson is for students to deepen their understanding of the Bernstein‑Vazirani algorithm by analyzing its quantum implementation.

By working through a low‑dimensional example, students focus on how the sequence of quantum gates leads to the measurement of the hidden string and how this result can be generalized to larger input sizes.

You can download the worksheet as pdf and docx.

Additional tool for Bernstein-Vazirani lesson

The spreadsheet tool can be used to model any 3‑qubit Bernstein‑Vazirani problem and to illustrate the basic set‑up of the function and the underlying circuitry. By using Hadamard gates, it shows how the hidden string can be determined, and the $a_i$ coefficients may be hidden so that students can attempt to deduce the string themselves.

The tool is designed for teacher‑led exposition prior to the exercises in the lesson. While it can be configured for any Bernstein‑Vazirani problem, four versions have been pre‑configured to correspond to the worksheet exercises.

Download the additional Excel tool.

Introduction

Imagine you’re in an arcade, and you’ve discovered a mysterious slot machine. Here’s how it works: you have three coins – some dimes and some quarters. The machine allows you to throw in these coins in various combinations, and it will either give you nothing or exactly $1. Your goal is to figure out the exact hidden combination of dimes and quarters that unlocks the dollar jackpot.

This arcade game is a playful analogy for the Bernstein-Vazirani algorithm, which solves a similar type of puzzle – but with quantum superpowers! Just as the slot machine has a hidden rule based on your coin choices, this algorithm is all about discovering a secret pattern (a hidden string of 0s and 1s) that determines the output of a special function. The challenge? Doing it as efficiently as possible.

How to play (students and teacher)

1. Students have three coins to start with, represented as bits (0 for dimes and 1 for quarters).
2. The slot machine (teacher) has the key (hidden string) and evaluates the input combination and gives the result: 0 (no dollar) or 1 (jackpot!).
3. Students’ mission is to guess the exact rule (the hidden string) that determines the result.

Mathematical formulation of the problem

Imagine we have a mystery box represented by a function $f_a$. This box is special because when you give a binary number with $n$ bits, it returns either $0$ or $1$. The function $f_a$ is defined using a fixed secret binary number $a=\left(a_1,a_2,\dots ,a_n\right)$, where each $a_i$ is either $0$ or $1$.

To compute $f_a\left(x\right)$, the function follows these steps:

• Take an $n$-bit input $x=\left(x_1,x_2,\dots ,x_n\right)$, where each $x_i$ is either $0$ or $1$.
• Multiply each input bit by the corresponding bit in $a$: $a_1·x_1+a_2·x_2+\dots +a_n·x_n$.
• Check the result of the sum:
  • If the sum is even, the function outputs $0$.
  • If the sum is odd, the function outputs $1$.

Task 1

Use the hidden binary number $a=\left(1,0,1\right)$ for the case $n=3$ and complete the following table by computing $f_a\left(x\right)$.

Analyse the Results: How many and which combinations of quarters and dimes will result in a 1$ win. Notice how the outputs depend on the hidden pattern. This pattern is the key to understanding the function’s behaviour.

Task 2 

Now we focus on the actual problem to find the hidden string of a function $f_a(x_1,x_2,x_3)$ from the table below:

Find the most efficient strategy to determine the string $a=\left(a_1,a_2,a_3\right)$:

• How many queries do we need?
• Which input values $\left(x_1,x_2,x_3\right)$ would you use to determine the string $a=\left(a_1,a_2,a_3\right)$ most efficiently?
• What is the hidden string?

Quantum computer simulation with the IBM Composer

1. In this first approach, we use a classical algorithm to find the hidden string. 

Open https://quantum.ibm.com/composer/files/new . The circuit below implements a particular string, which we are trying to figure out.

Example: Input $x_1=\left(1,0,0\right)$.

• The input values $x_1,x_2,x_3$ are the inputs from the first three qubits $q\left[0\right],q\left[1\right],q\left[2\right]$.
• The function value is the output from $q\left[3\right]$.
• All qubits are initialized to input value $0$. In order to change the input value from $0$ to $1$, apply $\oplus$ to the respective qubit.
• Measurement   of the last qubit $q\left[3\right]$ gives $f_a(x_1,x_2,x_3)$.

The measured value, in this case $1$, is the function value $f_a(x_1,x_2,x_3)$, which can be read from the graph that shows the simulation of the measurement probability.

Task 3 

Build the above quantum circuit and use the quantum composer to complete the table below:

2. In this second approach we use the Bernstein Vazirani quantum algorithm to find the hidden string.

The quantum algorithm uses the circuit below. The function is, as before, implemented by the 2 CNOT gates. The hidden output string is obtained after measuring the output of the first 3 qubits. Similar as in the case of the Deutsch Algorithm, the initial Hadamard gates create a superposition of all possible input states.

Build the Quantum algorithm and confirm that the simulation indeed reveals the string you found classically in problem 3.

Notice: It took 3 queries classically, but only one query using the quantum algorithm.

In order to explore how the quantum algorithm solves the problem, let’s look at the two dimensional example, $f(x_1,x_2)$, which state evolution we can easily track with help from an Excel sheet.

Download the Excel sheet.

Task 4

Build the circuit below one gate at a time as you fill in the Excel sheet one gate at a time. Confirm that your Excel agrees with the state evolution from the composer.

Some help how to get started. Use ket notation, explain that I drop the normalisation in the Excel.

Initially all qubits are in state $|0⟩$: $|q_0⟩|q_1⟩|q_2⟩\equiv |q_0,q_1,q_2⟩=|0,0,0⟩.$

The $\oplus$-Gate is acting on $|q_2⟩$ and flips the total state to $|0,0,1⟩$, which we note in our table:

The Hadamard gate acting on $|q_0⟩$ and creates a superposition $\frac{1}{\sqrt{2}}(|0⟩+|1⟩)$. The total state is therefore $\frac{1}{\sqrt{2}}(|0⟩+|1⟩)|0⟩|1⟩=\frac{1}{\sqrt{2}}(|0,0,1⟩+|1,0,1⟩).$

For simplicity, we drop the normalisation factor and denote the final state in our table as

Finish the Excel table and answer the following questions:

• a) What do the two Hadamard gates in the beginning accomplish?
• b) Why is there an $\oplus$-Gate at the beginning of the output qubit? Look what would happen if the $\oplus$-Gate was missing.
• c) What is the purpose of the last two Hadamard gates?
• d) What string $\left(a_1,a_2\right)$ does the measurement reveal?