In this Quantum Computing: From Concepts to Code‘s chapter, we’ll solve a new type of promise problem using a circuit that looks exactly like the one we used for the Deutsch-Jozsa algorithm. This time, our promise oracle contains a secret bitstring, $s$, of length $n$. For any given input $x$ of length $n$, the oracle promises to return a single bit that is the bitstring dot product of $x$ and $s$.
Our goal is to uncover this secret string with the fewest possible queries to the oracle. On a classical computer, you would have to make at least $n$ queries to figure out the bits of $s$. However, using the Bernstein-Vazirani algorithm, a quantum computer can find the entire secret string with just one query.
🔍 The Oracle’s Hidden Secret
The oracle is designed to perform a specific calculation. For a given input bitstring $x$ and the secret bitstring $s$, it computes the bitstring dot product, $s \cdot x$. This is a calculation that involves multiplying corresponding bits of the two strings together and then summing the results.
The final output bit is either 0 or 1, based on whether this sum is even or odd. This means the oracle’s output is highly dependent on the secret string $s$. The challenge for us is to work backwards from the output and figure out what $s$ must be.
⚛️ A Familiar Circuit, a New Solution
The beauty of the Bernstein-Vazirani algorithm is that it uses the exact same circuit structure as the Deutsch-Jozsa algorithm. We start by preparing an input register of $n$ qubits and an auxiliary qubit in a superposition state.
We then send this superposition into the oracle for a single query. The oracle performs its parallel computation on every possible input, and thanks to a phenomenon called phase kickback, the secret string $s$ is encoded into the phase of the qubits in the output superposition.
🎯 A Perfect Measurement Every Time
After the single query to the oracle, the algorithm performs a final set of Hadamard gates on the input register and then measures all $n$ qubits. The remarkable result is that the measured bitstring is guaranteed to be the secret string $s$.
Unlike other algorithms where you might get a probabilistic result, the Bernstein-Vazirani algorithm gives you the correct answer with 100% certainty.
It’s a stunning demonstration of how a simple quantum circuit can solve a problem that would be much more labor-intensive on a classical computer. This shows how quantum parallelism, when combined with a clever oracle design, can be used to efficiently extract a huge amount of information from a single computation.
—
Glassner, Andrew. Quantum Computing: From Concepts to Code. No Starch Press, 2025.
More Topics
- The Quantum Threat: How Shor’s Algorithm Puts Modern Encryption at Risk
- The Deutsch-Jozsa Algorithm: An Exponential Leap in Quantum Problem Solving
- Simon’s Algorithm: The First Quantum Speedup That Left Classical Computers in the Dust
- Cracking the Code: How Quantum Parallelism Solves Deutsch’s Problem in One Step
- Your First Quantum Program: The ‘Hello, World!’ of a Qubit
- Scaling Up: How Quantum Computers Handle Multiple Qubits
- The ‘Spooky Action’: What Happens When Qubits Entangle?
