Quantum Advantage in Bernstein-Vazirani

1. From Global Properties to Hidden Information

The Deutsch-Jozsa algorithm was our first example of a quantum speedup, but the problem it solves is somewhat abstract. The Bernstein-Vazirani algorithm provides a more compelling case for the power of quantum computation. It tackles a problem of information extraction: finding a secret bitstring hidden inside a black-box function, or oracle.

First, let's briefly formalize the idea of an oracle-based problem, which is central to many quantum algorithms.

With that context, we can now define the specific problem that the Bernstein-Vazirani algorithm solves.

The Bernstein-Vazirani Problem

Imagine you are given access to an oracle that implements a function $f_s(x)$. This function takes an $n$-bit input string $x$ and returns a single bit (0 or 1). You are promised that for some hidden, unknown $n$-bit string $s$, the function is defined as:

Your task is to find the hidden string $s$.

The operation $s\cdot x(\mathrm{mod}2)$ is a bitwise dot product. It works like this:

1. Perform a bitwise AND between the strings $s$ and $x$.
2. Sum the bits of the resulting string and take the result modulo 2 (which is the same as finding the parity or XORing all the bits together).

For example, if $n=4$, the hidden string is $s=1011$, and you choose the input $x=1100$:

• $s\cdot x=(1\cdot 1)+(0\cdot 1)+(1\cdot 0)+(1\cdot 0)=1+0+0+0=1$
• So, $f_{1011}(1100)=1$

The following article provides a crisp definition of the problem.

2. The Classical Solution: One Bit at a Time

Before diving into the quantum approach, let's consider how we would solve this with a classical computer. How many times would we need to query the oracle to guarantee we find $s$?

To find the $n$-bit string $s=s_n{s}_{n-1}...s_1$, we need to determine each of its $n$ bits. A clever way to do this is to choose our inputs $x$ strategically to isolate one bit of $s$ at a time.

Consider querying the oracle with an input $x$ that is all zeros except for a single '1' at the $i$-th position.

• To find $s_1$, we query with $x=\mathrm{00...01}$. The dot product becomes $s\cdot x=s_1$. So, the oracle's output is exactly the first bit of $s$.
• To find $s_2$, we query with $x=\mathrm{00...10}$. The dot product becomes $s\cdot x=s_2$. The output is the second bit of $s$.
• ...and so on.

After $n$ such queries, we will have determined all $n$ bits of $s$. It can be proven that you cannot do better than this classically. To recover $n$ bits of information, you need to gain at least one bit of information per query, which requires a minimum of $n$ queries.

The video below gives a clear walkthrough of this classical strategy.

So, the classical query complexity is O(n). To find a 100-bit string, you need 100 queries.

3. The Quantum Solution: A Single Query

Now for the quantum approach. As mentioned, the Bernstein-Vazirani algorithm uses the same circuit as the Deutsch-Jozsa algorithm.

Let's see how this structure solves the problem in a single query. The magic lies in how this specific oracle, implementing $f(x)=s\cdot x$, interacts with the superposition created by the Hadamard gates.

Here’s a conceptual walkthrough:

1. Initialization: We start with $n$ input qubits in the $|0{⟩}^{\otimes n}$ state and one ancilla qubit in the $|1⟩$ state.

2. Superposition: We apply Hadamard gates to all $n+1$ qubits. The input register becomes an equal superposition of all $2^n$ possible input strings, and the ancilla becomes $|-⟩$. The combined state is:

   $$\frac{1}{\sqrt{2^n}}\sum _{x\in \{0,1{\}}^n}|x⟩\otimes |-⟩$$

3. Oracle and Phase Kickback: We apply the oracle $U_f$. As we saw with Deutsch-Jozsa, when the ancilla is in the $|-⟩$ state, the oracle's output $f(x)$ is "kicked back" as a phase of $(-1{)}^{f(x)}$ to the input register. Since $f(x)=s\cdot x$, our state becomes:

   $$\frac{1}{\sqrt{2^n}}\sum _{x\in \{0,1{\}}^n}(-1{)}^{s\cdot x}|x⟩\otimes |-⟩$$

   At this point, the hidden string $s$ is encoded in the relative phases of the superposition. The problem now is how to read it out.

4. Interference: We apply Hadamard gates to the $n$ input qubits again. This is the crucial interference step. It turns out that this specific transformation has a remarkable property:

   $$H^{\otimes n}\left(\frac{1}{\sqrt{2^n}}\sum _{x\in \{0,1{\}}^n}(-1{)}^{s\cdot x}|x⟩\right)=|s⟩$$

   The final Hadamard gates cause all the states in the superposition to interfere destructively, except for the one corresponding to our hidden string, $|s⟩$.

5. Measurement: When we measure the $n$ input qubits, we get the string $s$ with 100% probability.

The Qiskit video below explains precisely how the Deutsch-Jozsa circuit, when given a Bernstein-Vazirani oracle, produces the hidden string $s$.

4. The Quantum Advantage

The comparison is now stark and clear:

• Classical algorithm: Requires $n$ queries to find the $n$-bit string $s$.
• Quantum algorithm: Requires only 1 query, regardless of the size of $s$.

This is a proven, significant advantage in query complexity. While the Deutsch-Jozsa algorithm provided an exponential speedup for a promise problem, Bernstein-Vazirani demonstrates a more practical form of speedup by efficiently extracting a hidden piece of information.

From a computer science perspective, this result was one of the first to provide an "oracle separation" between complexity classes. It showed that there is a problem that a quantum computer (in the class BQP, Bounded-error Quantum Polynomial time) can solve efficiently, while a classical probabilistic computer (in the class BPP, Bounded-error Probabilistic Polynomial time) cannot.

The key takeaway is that the quantum algorithm is not trying out all $2^n$ inputs one-by-one. Instead, it uses a single, massive superposition to set up an interference pattern that reveals the hidden structure of the function—the string $s$—all at once.

Conclusion

In this lesson, we explored the Bernstein-Vazirani algorithm, a cornerstone of quantum computing that beautifully illustrates quantum advantage. You've seen how it uses the same core components as the Deutsch-Jozsa algorithm—superposition, phase kickback, and interference—to achieve a completely different and more practical goal.

Key Takeaways:

• The Bernstein-Vazirani problem is to find a hidden $n$-bit string $s$ given an oracle that computes $f(x)=s\cdot x(\mathrm{mod}2)$.
• A classical computer requires a minimum of $n$ queries to the oracle to determine $s$.
• A quantum computer can determine $s$ with 100% certainty in just a single query.
• The quantum advantage arises from using the Deutsch-Jozsa circuit structure to encode the hidden string $s$ into the phases of a superposition and then using a final set of Hadamard gates to make $|s⟩$ the only state that survives the interference.

Preview of the Next Lesson:
Now that you have a firm grasp of the theory behind the Bernstein-Vazirani algorithm, the next logical step is to build it. In the next lesson, we will implement the Bernstein-Vazirani algorithm in Qiskit to find the hidden bitstring, turning the circuit diagram you saw today into a working quantum program.