The Bernstein-Vazirani Algorithm - Mathematical approach

Overview

Secondary School

Physics, Mathematics

Quantum Computing

English

Overview

Keywords: Bernstein–Vazirani algorithm, hidden binary string, Hadamard gates, quantum circuit, single query
Age group: 16-18 years
Required knowledge/skills: Students should have done Lesson 2 about Deutsch's algorithm
Time frame: 75-90 minutes

Author: Sergio Rivera Hernandez (DE)

Content

Learning objectives
Lesson plan
Worksheet 1: Student tasks and solutions
  • The problem
  • Task 1, Task 2, Task 3
  • Quantum Solution: The Bernstein‑Vazirani Algorithm
  • Task 4
Worksheet 2: Testing the algorithm for the case $n = 2$ with solutions
  • Task 1, Task 2, Task 3, Task 4
  • Optional tasks

Summary

This teaching unit introduces the Bernstein‑Vazirani algorithm as an example where a quantum approach massively outperforms the classical approach for finding a hidden binary string. Students work through the algorithm step by step for small cases, using tables, Hadamard gates, and state transformations to see how the hidden string is obtained with a single query. The unit then connects the theoretical calculations to a concrete circuit implementation using the IBM Quantum Composer.

Learning objectives

The goal of this lesson is for students to apply and deepen their understanding of the general physical principles introduced in Lesson 1 (Superposition, Interference and Quantum Function Evaluation), now in the context of the Bernstein-Vazirani Algorithm.

First, students will explore the general idea of the algorithm, as they did in Lesson 2. Then, they will apply the algorithm to the n = 2 case.

It is important that, throughout the lesson, students understand that for n≥3, calculations become increasingly tedious. However, understanding the n=2 case allows them to generalize the algorithm for larger values of n. The choice of n=2 is based on time constraints and the fact that solving larger cases is not necessary to grasp the core principles of the algorithm.

This lesson will also reinforce the fundamental structure underlying many quantum algorithms, known as the Golden Circuit Pattern.

Lesson plan

Timing in minutes	Lesson phases	Activity	Material
0–5	Introduction	In this phase, the teacher will explain that this lesson will cover a more complex algorithm, one that solves one of the search algorithms [FU1.1][SR1.2]from Lesson 1 in a single step.	Worksheet & Spreadsheet tool
5–20	Work Phase I	In this phase, students will receive the worksheet, work on Tasks 1,2 and 3, and read through the three steps of the algorithm.	Worksheet 1
15–45	Intermediate Reflection and Work Phse II	In this phase, the results of the first three tasks will be reviewed to ensure that students have understood the general idea before proceeding with the concrete application of the algorithm. The teacher will explain the algorithm in detail to ensure that students fully understand it, after which they will proceed to solve Task 4.
30-40	Work Phase III	In this phase, students will receive the next work-sheet and work on Exercises 1–4. Students who finish early can proceed to using a computer and continue with the optional task.	Worksheet 2
75–90	Closure	Discussion of results. In this section, the teacher will once again emphasize the physical principles behind the algorithm and highlight that these principles will be needed again in the next lesson.

Note for Teachers: This lesson is designed as a double period (approx. 90 minutes). If your schedule uses 45-minute slots, Task 4 and the IBM Composer activity can be assigned as homework or covered in a second session

You can download both worksheets to use with your students:

Worksheet 1: pdf and docx
Worksheet 2: pdf and docx

Worksheet 1

The Bernstein-Vazirani algorithm, developed in 1993, builds upon Deutsch’s algorithm and provides another example of how quantum computing can solve certain problems more efficiently than classical computing.
In Lesson 1, you solved a task trying to discover a hidden binary string by asking Yes/No questions one at a time. Using a classical approach as you did, one needs to ask one question per bit to determine the entire string. This means that for a hidden string of $n$ bits, you required $n$ queries in the worst case.
However, quantum computing leverages the Bernstein-Vazirani algorithm to find the hidden string in just one query, regardless of how many bits it contains: Yes, it reduces $n$ queries to a single one.
In this lesson, you will first explore how this quantum speedup is achieved using an example where the hidden string consists of three bits. Then, you will generalize the concept to $n$ bits.

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 = (a_{1} a_{2} \dots a_{n})$ , where each $a_{i}$ is either $0$ or $1$ .

To compute $f_{a}$ $(x)$ , the function follows these steps :

Take a $n$ -bit input $x = (x_{1} x_{2} \dots x_{n})$ , where each $x_{i}$ is $0$ or $1$ .
Multiply each input bit by the corresponding bit in a: $a_{1} \cdot x_{1} + a_{2} \cdot x_{2} + \dots + a_{n} \cdot 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$ .

This type of addition is called addition modulo 2. It means: if the total number of 1s is even, the result is 0; if it is odd, the result is 1.

Task 1

Use the hidden binary number $a = (1, 0, 1)$ for the case $n = 3$ and complete the following table by computing $f_{a} (x)$ .

Input x	$a \cdot x = a_{1} \cdot x_{1} + a_{2} \cdot x_{2} + a_{3} \cdot x_{3}$	Odd	Even	Output $f_{a} (x)$
$(0, 0, 0)$	$1 \cdot 0 + 0 \cdot 0 + 1 \cdot 0 = 0$		x	0
$(0, 0, 1)$	$1 \cdot 0 + 0 \cdot 0 + 1 \cdot 1 = 1$	x		1
$(0, 1, 0)$
$(0, 1, 1)$
$(1, 0, 0)$
$(1, 0, 1)$
$(1, 1, 0)$
$(1, 1, 1)$

Solution task 1 Solution task 1

Computing $f_{a} (x)$ for $a = (1, 0, 1)$ and $n = 3$

Input x	$a \cdot x = a_{1} \cdot x_{1} + a_{2} \cdot x_{2} + a_{3} \cdot x_{3}$	Odd	Even	Output $f_{a} (x)$
$(0, 0, 0)$	$1 \cdot 0 + 0 \cdot 0 + 1 \cdot 0 = 0$		x	0
$(0, 0, 1)$	$1 \cdot 0 + 0 \cdot 0 + 1 \cdot 1 = 1$	x		1
$(0, 1, 0)$	$1 \cdot 0 + 0 \cdot 1 + 1 \cdot 0 = 0$		X	0
$(0, 1, 1)$	$1 \cdot 0 + 0 \cdot 1 + 1 \cdot 1 = 1$	X		1
$(1, 0, 0)$	$1 \cdot 1 + 0 \cdot 0 + 1 \cdot 0 = 1$	X		1
$(1, 0, 1)$	$1 \cdot 1 + 0 \cdot 0 + 1 \cdot 1 = 2$		X	0
$(1, 1, 0)$	$1 \cdot 1 + 0 \cdot 1 + 1 \cdot 0 = 1$	X		1
$(1, 1, 1)$	$1 \cdot 1 + 0 \cdot 1 + 1 \cdot 1 = 2$		x	0

Understanding the challenge

Our goal is to discover the secret binary string $a$ used by the function $f_{a} (x)$ . To achieve this, we can ask the function questions by giving it different binary strings $x = (x_{1} x_{2} \dots x_{n})$ and observing what it returns.

Classical Solution

Task 2

Determine the minimum number of questions you need to ask to fully uncover the binary string $a = (a_{1}, a_{2}, a_{3})$ . Justify your answer.

Hint: Think back to the task you solved in Lesson 1, where you had to find a hidden binary string by asking Yes/No questions. How is that related to the problem we are facing now?

Solution task 2 Solution task 2

Classical Approach for finding $a$

Minimum number of queries needed: 3 (one for each bit).

Justification: Each bit $a_{i}$ is only affected by $x_{i}$ in the function $f_{a (x)}$ , meaning we can reveal $a$ by choosing queries carefully:

Query $x = (1, 0, 0)$ reveals $a_{1}$ .
Query $x = (0, 1, 0)$ reveals $a_{2}$ .
Query $x = (0, 0, 1)$ reveals $a_{3}$ .

Task 3

Now, consider the case where the binary string has $n$ bits: $a = (a_{1} a_{2} \dots a_{n})$ .

Determine the number of questions needed in this general case. Justify your answer.

Solution task 3 Solution task 3

Number of queries required in the classical case: $n$

Justification: The best strategy is to query one bit at a time:

$x = (1000 \dots 0)$ reveals $a_{1}$
$x = (0100 \dots 0)$ reveals $a_{2}$
$x = (0010 \dots 0)$ reveals $a_{3}$ , etc.

Quantum Solution: The Bernstein-Vazirani Algorithm

Instead of querying the function multiple times as in the classical method, the Bernstein–Vazirani algorithm extracts the entire hidden string in a single query using the circuit below:

It follows these steps:

Steps of the Bernstein–Vazirani Algorithm Steps of the Bernstein–Vazirani Algorithm

Step I: Creating superposition

Prepare $n$ qubis in state $| 0 ⟩$ in the first register. Apply a Hadamard gate to all of them. This creates a superposition of all possible states on the $n$ qubits:

$H | 0 ⟩ H | 0 ⟩ \dots H | 0 ⟩ = \frac{1}{\sqrt{2^{n}}} (| 00 \dots 0 ⟩ + | 00 \dots 1 ⟩ + \dots + | 11 \dots 1 ⟩)$

Step II: Applying the Function $f_{a}$ and Introducing Phases

Apply the function $f_{a}$ to the obtained state in Step I, using the second register. This operation adds a phase factor of either ${(-1)}^{0}$ or ${(-1)}^{1}$ to each term of the superposition:

$\frac{1}{\sqrt{2^{n}}} [{(-1)}^{f_{a} (00 \dots 0)} | 00 \dots 0 ⟩ + {(-1)}^{f_{a} (00 \dots 1)} | 00 \dots 1 ⟩ + \dots + {(-1)}^{f_{a} (11 \dots 1)} | 11 \dots 1 ⟩]$

Step III: Applying Hadamard Gates

Apply a Hadamard gate to each qubit in the first register:

$\frac{1}{\sqrt{2^{n}}} [{(-1)}^{f_{a} (00 \dots 0)} H | 0 ⟩ H | 0 ⟩ \dots H | 0 ⟩ + {(-1)}^{f_{a} (00 \dots 1)} H | 0 ⟩ H | 0 ⟩ \dots H | 1 ⟩ + \dots {(-1)}^{f_{a} (11 \dots 1)} H | 1 ⟩ H | 1 ⟩ \dots H | 1 ⟩]$

Note: The fact that the function introduces these phase shifts in the first register without affecting the second register directly is a fundamental concept in quantum computing. If you would like to explore in detail why and how these phase shifts occur, check the Quantum Function Evaluation worksheet.

Final Measurement: Measuring the first register now reveals $a$ with 100% probability. Unlike the classical case, where multiple queries are required, the quantum algorithm finds $a$ in one query. After measurement, we obtain $| a ⟩ = | a_{1} a_{2} \dots a_{n} ⟩$ .

Task 4

Compare the circuit used in the Deutsch Algorithm (see the figure) with the circuit used in the Bernstein-Vazirani Algorithm and answer the following questions:

Explain the similarities and differences between the two algorithms. How does the Deutsch Algorithm relate to the Bernstein-Vazirani Algorithm?

Solution task 4 Solution task 4

Similarities & Differences

Aspect	Deutsch Algorithm	Bernstein-Vazirani Algorithm
Problem Solved	Determines if $f (x)$ is constant or balanced	Finds the hidden bit-string $a$
Number of Qubits	2 qubits (1 input + 1 auxiliary)	$n + 1$ qubits ( $n$ input + 1 auxiliary)
Quantum Speedup	Reduces queries from 2 to 1	Reduces queries from $n$ to 1
Key Difference	Solves a binary classification problem	Extracts full information about $a$

Worksheet 2

Testing the algorithm for the case $n = 2$

Now, you will analyze each step of the algorithm to understand how the quantum principles behind it allow us to solve the problem with a single query for the case $n = 2$ . Here is the circuit for this case:

Task 1

Step I: Show that after applying a Hadamard gate to each $| 0 ⟩$ in the first register, the first register transforms into:

$H | 0 ⟩ H | 0 ⟩ = \frac{1}{2} (| 00 ⟩ + | 01 ⟩ + | 10 ⟩ + | 11 ⟩)$

Hint: The Hadamard operator can be expressed as $H = \frac{1}{\sqrt{2}} (| 0 ⟩ ⟨ 0 | + | 0 ⟩ ⟨ 1 | + | 1 ⟩ ⟨ 0 | - | 1 ⟩ ⟨ 1 |) .$

Solution task 1: Applying Hadamard Gates (Step I) Solution task 1: Applying Hadamard Gates (Step I)

We apply a Hadamard gate to each qubit in the first register, which transforms the initial state as follows:

$H | 0 ⟩ H | 0 ⟩ = \frac{1}{2} (| 00 ⟩ + | 01 ⟩ + | 10 ⟩ + | 11 ⟩)$

Explanation:

The Hadamard gate applied to $| 0 ⟩$ creates an equal superposition of $| 0 ⟩$ and $| 1 ⟩$ .
Since there are two qubits, applying Hadamard gates to both results in a uniform superposition of all four possible 2-bit states.

Normalization Factor: Explain to students that the factor $\frac{1}{2}$ is the result of multiplying the normalization factors of two individual qubits $(\frac{1}{\sqrt{2}} \cdot \frac{1}{\sqrt{2}} = \frac{1}{2}) .$ For a system with $n$ qubits, the general normalization factor is $\frac{1}{\sqrt{2^{n}}}$ .

Task 2

Step II: We know that applying the function $f_{a}$ to the state obtained in Step I results in the following transformation:

$\frac{1}{2} [{(-1)}^{f_{a} (00)} | 00 ⟩ + {(-1)}^{f_{a} (01)} | 01 ⟩ + {(-1)}^{f_{a} (10)} | 10 ⟩ + {(-1)}^{f_{a} (11)} | 11 ⟩] .$

Note: The function $f_{a}$ introduces phase shifts in the first register without directly affecting the second register. This is a fundamental concept in quantum computing. If you would like to explore in detail how and why these phase shifts occur, go to the Quantum Function Evaluation worksheet.

Your tasks

a) Assume that $a = (1, 0)$ and determine the function values by filling in the following table:

Input x	$a \cdot x = a_{1} \cdot x_{1} + a_{2} \cdot x_{2}$	Odd	Even	Output $f_{a} (x)$
$(0, 0)$
$(0, 1)$
$(1, 0)$
$(1, 1)$

b) Show that applying $f_{a}$ transforms the state from Step I as follows:

$\frac{1}{2} [| 00 ⟩ + | 01 ⟩ - | 10 ⟩ - | 11 ⟩] .$

Hint: The values in your table determine the signs of each basis state.

Solution task 2 Solution task 2

Applying $f_{a}$ (Step II)

a) Completing the Function Table (for $a = (1, 0)$ )

Input x	$a \cdot x = a_{1} \cdot x_{1} + a_{2} \cdot x_{2}$	Odd	Even	Output $f_{a} (x)$
$(0, 0)$	$1 \cdot 0 + 0 \cdot 0 = 0$		X	0
$(0, 1)$	$1 \cdot 0 + 0 \cdot 1 = 0$	x		0
$(1, 0)$	$1 \cdot 1 + 0 \cdot 0 = 1$	X		1
$(1, 1)$	$1 \cdot 1 + 0 \cdot 1 = 1$	x		1

b) Showing the Transformation:

Since the function $f_{a}$ modifies the phase based on whether the function output is $0$ or $1$ , we obtain:

$\frac{1}{2} (| 00 ⟩ + | 01 ⟩ - | 10 ⟩ - | 11 ⟩) .$

Task 3

a) Step III: Apply a Hadamard gate to each qubit in the state obtained in Step II:

$\frac{1}{2} [| 00 ⟩ + | 01 ⟩ - | 10 ⟩ - | 11 ⟩] .$

Show that this transformation exactly results in $| 10 ⟩$ .

Hint 1: Use the Hadamard transformations:

$H | 0 ⟩ = \frac{1}{\sqrt{2}} (| 0 ⟩ + | 1 ⟩), H | 1 ⟩ = \frac{1}{\sqrt{2}} (| 0 ⟩ - | 1 ⟩) .$

Hint 2: For example, applying Hadamard gates to $| 0 ⟩$ and $| 1 ⟩$ separately:

$H | 0 ⟩ H | 1 ⟩ = \frac{1}{\sqrt{2}} (| 0 ⟩ + | 1 ⟩) \frac{1}{\sqrt{2}} (| 0 ⟩ - | 1 ⟩) .$

b) What do you obtain after measuring the first register?

Compare your result with $a = (1, 0)$ .
What does this tell you about the problem that the algorithm is designed to solve?

c) Scaling to $n = 3$ : Suppose you want to test the algorithm for $n = 3$ .

How many terms would you obtain in Task 3 a) before cancellation of equal terms?
Explain why your teacher asked you to test the algorithm only for $n = 2$ and not for $n = 3$ .

Solution task 3: Applying Hadamard gates again (Step III) Solution task 3: Applying Hadamard gates again (Step III)

Applying Hadamard gates to both qubits in:

$\frac{1}{2} (| 00 ⟩ + | 01 ⟩ - | 10 ⟩ - | 11 ⟩) .$

Using the Hadamard transformations:

$H | 0 ⟩ = \frac{1}{\sqrt{2}} (| 0 ⟩ + | 1 ⟩), H | 1 ⟩ = \frac{1}{\sqrt{2}} (| 0 ⟩ - | 1 ⟩) .$

1. Apply $H \otimes H$ to the superposition:

$\frac{1}{2} [H | 0 ⟩ H | 0 ⟩ + H | 0 ⟩ H | 1 ⟩ - H | 1 ⟩ H | 0 ⟩ - H | 1 ⟩ H | 1 ⟩] .$

2. Expanding each term:

$H | 0 ⟩ H | 0 ⟩ = \frac{1}{2} (| 00 ⟩ + | 01 ⟩ + | 10 ⟩ + | 11 ⟩)$

$H | 0 ⟩ H | 1 ⟩ = \frac{1}{2} (| 00 ⟩ - | 01 ⟩ + | 10 ⟩ - | 11 ⟩)$

$- H | 1 ⟩ H | 0 ⟩ = - \frac{1}{2} (| 00 ⟩ + | 01 ⟩ - | 10 ⟩ - | 11 ⟩)$

$- H | 1 ⟩ H | 1 ⟩ = - \frac{1}{2} (| 00 ⟩ - | 01 ⟩ - | 10 ⟩ + | 11 ⟩)$

3. Result: After summing these terms, all coefficients except $| 10 ⟩$ cancel out to zero. The final state is exactly $| 10 ⟩$ .

We find that the final measurement gives $| 10 ⟩$ , meaning the algorithm has extracted $a = (1, 0)$ .

Task 4

If you still have time and motivation, repeat Steps I, II, and III for the remaining binary strings: $a = (0, 0)$ , $a = (0, 1)$ , $a = (1, 1)$ .

Solution task 4 Solution task 4

Testing for Other $a$ -Values

If we repeat the algorithm for:

$a = (0, 0)$ → Measurement result: $| 00 ⟩$
$a = (0, 1)$ → Measurement result: $| 01 ⟩$
$a = (1, 1)$ → Measurement result: $| 11 ⟩$

In each case, the algorithm directly reveals $a$ after a single function call.

Scaling to $n = 3$

Before cancellation, there would be $2^{3} = 8$ terms in the superposition.
The reason the teacher asks to test only for n=2 is:
- $n = 3$ would require manipulating and simplifying $8$ terms.
- The key ideas (Hadamard gates, phase shifts, and interference) are already evident with $n = 2$ .
- The generalization to higher $n$ follows the same pattern.

Optional tasks Optional tasks

Implementing the Bernstein-Vazirani Algorithm in the IBM Quantum Composer

In this task, you will implement the Bernstein-Vazirani algorithm using the IBM Quantum Composer. The circuit in the image represents the implementation of the algorithm for $n = 2$ . Analyze it carefully and answer the following questions:

a) The first two Hadamard gates are applied to the first two qubits. What is their purpose? How does their effect relate to the superposition state you calculated in Task 1?
b) There is an X-gate applied at the beginning to the output qubit. Why is this necessary? Predict what would happen if the X-gate were missing and then test your prediction in the Quantum Composer.
c) The last two Hadamard gates are applied before measurement. What do they accomplish? How does this step relate to Task 3, where you extracted the hidden string?
d) After running the circuit, the measurement gives a two-bit binary string. What value of $(a_{1}, a_{2})$ does the measurement reveal? Does this match your expectations based on the theoretical calculations in Tasks 1, 2, and 3?

Important Note on the Circuit Image in the optional task

Please note that the IBM Quantum Composer screenshot displays a circuit for a secret string $(1, 1)$ , as it contains two CNOT gates. But the theoretical calculations in Tasks 1–3 were based on $(1, 0)$ . Therefore, the measurement result in the image $| 11 ⟩$ will differ from your calculated result $| 10 ⟩$ .

Go to: Grover's Algorithm

Share this page

The Bernstein-Vazirani Algorithm - Mathematical approach

Overview

Overview

Content

Summary

Learning objectives

Lesson plan

Worksheet 1

The problem

Task 1

Understanding the challenge

Classical Solution

Task 2

Classical Approach for finding a

Task 3

Quantum Solution: The Bernstein-Vazirani Algorithm

Step I: Creating superposition

Step II: Applying the Function fa and Introducing Phases

Step III: Applying Hadamard Gates

Task 4

Worksheet 2

Testing the algorithm for the case n=2

Task 1

Task 2

Task 3

Task 4

Scaling to n=3

Implementing the Bernstein-Vazirani Algorithm in the IBM Quantum Composer

Important Note on the Circuit Image in the optional task

Similar teaching materials

How to implement Deutsch’s algorithm with a Mach–Zehnder interferometer

Careers in Quantum Technologies

Classical Approach for finding $a$

Step II: Applying the Function $f_{a}$ and Introducing Phases

Testing the algorithm for the case $n = 2$

Scaling to $n = 3$