Bernstein Vazirani: a whole secret in one shot

The last algorithm extracted one bit of information in a single query, whether a function was constant or balanced. This one extracts an entire hidden string in a single query, and watching it happen is the most satisfying demonstration of phase kickback I know. Same machinery as before, but the payoff is vivid: you guess a secret that a classical computer would have to pry out one bit at a time, and you get all of it at once.

The problem

Someone has chosen a secret bit string. Call it s, n bits long, hidden inside a function you cannot look into. The function works like this: you give it an input string x, and it returns the dot product of s and x, modulo 2. In plain terms, it lines s and x up bit by bit, multiplies each pair, adds up the results, and gives you back whether that total is even or odd, as a single bit. You can query this function as many times as you like. Your job is to discover s.

This is a clean, well defined task. The secret is in there, the function leaks a little about it with every query, and you want to reconstruct the whole string.

What it costs classically

The classical strategy is methodical and slow. To learn the first bit of s, you query with x equal to 1 followed by all zeros. The dot product then picks out exactly the first bit of s and hands it to you. To learn the second bit, you query with 0, 1, 0, and the rest zeros, isolating the second bit. And so on. Each carefully chosen query reveals exactly one bit of the secret, so for an n bit string you need n queries, one per bit, marching through the string position by position. No way around it classically: each query gives you one bit of information about s, so n bits of secret take n queries.

It is worth pausing on why that is genuinely the best classical approach, not just the obvious one. Each query to the function returns a single bit, the dot product result, so by basic information counting a single query can deliver at most one bit about the secret. The secret holds n bits. So you need at least n queries just to receive enough information to specify it, and the position by position strategy hits that floor exactly, one bit learned per query. There is no clever classical querying that does better, because you cannot extract more than one bit of secret from a one bit answer. This is what makes the quantum result so striking: the quantum circuit appears to violate that counting, pulling n bits from what looks like a single query. It does not actually break information theory, the resolution is that the single quantum query acts on a superposition of all inputs at once, but the felt impossibility of it is exactly why this algorithm is such a satisfying demonstration.

What it costs on a quantum computer

One query. The entire string, however long, in a single shot. Where the classical approach reads s one bit at a time, the quantum circuit reads all n bits simultaneously. That is the separation here: linear in the length of the secret classically, constant quantum.

Building it

The circuit shape is identical to the last post, which is the point: same engine, different oracle. Inputs into superposition, ancilla into |−⟩, oracle once, Hadamards on the inputs, measure. And the oracle for this problem is almost laughably simple. The dot product with s is computed by putting a CNOT from each input qubit where s has a 1, onto the ancilla. The qubits where s is 0 are left alone, and the loop below walks the string in reverse because Qiskit numbers its qubits from the right. Let me hide the string 1011 and recover it.

from qiskit import QuantumCircuit
from qiskit.primitives import StatevectorSampler

secret = "1011"
n = len(secret)

qc = QuantumCircuit(n + 1, n)
qc.x(n); qc.h(n)                 # ancilla -> |->
for q in range(n):
    qc.h(q)                      # inputs -> superposition

# oracle: CNOT into the ancilla from each qubit where the secret bit is 1
for i, bit in enumerate(reversed(secret)):
    if bit == "1":
        qc.cx(i, n)

for q in range(n):
    qc.h(q)                      # interfere
qc.measure(range(n), range(n))

result = StatevectorSampler().run([qc], shots=1000).result()[0].data.c.get_counts()
print(result)   # {'1011': 1000}

Run it. The measurement comes back as 1011, every single time, with no spread at all. The secret string is read directly off the input qubits in one query. You did not infer it bit by bit. The whole thing appeared at once, exactly the string that was hidden in the oracle. Change the secret to anything you like and the circuit recovers it just the same, always in a single shot.

It works for any secret

That last claim is worth not taking on faith, so change the secret and watch. The circuit does not know or care what string is hidden, it just reads out whatever the oracle encoded.

for secret in ["101", "110"]:
    n = len(secret)
    qc = QuantumCircuit(n + 1, n)
    qc.x(n); qc.h(n)
    for q in range(n):
        qc.h(q)
    for i, bit in enumerate(reversed(secret)):
        if bit == "1":
            qc.cx(i, n)
    for q in range(n):
        qc.h(q)
    qc.measure(range(n), range(n))
    counts = StatevectorSampler().run([qc], shots=500).result()[0].data.c.get_counts()
    print(f"secret {secret} -> {counts}")

Run it. The secret 101 comes back as 101, and 110 comes back as 110, each in a single clean query, with no spread across the shots. The circuit is a general secret reader: hide any string in the oracle, run once, and the measurement hands it back. There is no probability to average over, no repetition to gather statistics, no ambiguity to resolve. Whatever pattern the oracle encoded into the phases, the Hadamard layer decodes it exactly. That determinism is what makes Bernstein and Vazirani feel almost magical the first time, and it is worth running with a few of your own secrets to convince yourself it is not a fluke of the particular string.

Why it works, the clean version

This is phase kickback at its most transparent, so it is worth being precise. The opening Hadamards put the input register into a superposition of every possible input. The ancilla sits in |−⟩. Now the oracle: each CNOT from an input qubit into that |−⟩ ancilla does not flip anything, it kicks a phase back onto that input qubit, exactly the trick from two posts ago. But here is the elegant part. The oracle only places a CNOT on the qubits where s has a 1. So a phase gets kicked back onto precisely those qubits, and not the others. The pattern of which qubits received a phase is exactly the pattern of s.

So after the oracle, the secret string is written into the phases of the input register: the qubits where s is 1 carry a phase, the qubits where s is 0 do not. Then the closing Hadamards perform the read. A Hadamard turns a qubit that carries this particular phase into a |1⟩ and a qubit without it into a |0⟩, deterministically. So the final measurement reads out a 1 wherever s had a 1 and a 0 wherever s had a 0. The string comes back perfectly. Kickback wrote s into the phases, qubit by qubit, and the Hadamard layer decoded it, qubit by qubit, all in parallel. No ambiguity, no statistics, no repetition. The secret was encoded in which qubits got a phase, and one layer of interference reads that encoding straight off.

How it compares to the last one

Put the two algorithms side by side and you can see the engine clearly. Deutsch and Jozsa used kickback and interference to extract one bit of global information, a single yes or no about the whole function. Bernstein and Vazirani uses the exact same kickback and interference to extract n bits, the entire secret string, in the same single query. Nothing about the machinery changed. The oracle just stamped a richer pattern into the phases, and the Hadamard layer read out more of it. That is the lesson worth carrying: the engine is fixed, and what changes from algorithm to algorithm is how much structure the oracle writes into the phases and how cleverly the interference reads it back.

The honest framing

As with the last one, this is a contrived problem. You will never, in real work, need to extract a secret string from an oracle that computes dot products with it. It is a constructed example, built to show a clean separation. So treat the result the same way: not as a tool, but as the clearest possible demonstration that phase kickback plus interference can extract structured information in parallel, reading many bits where a classical approach reads one at a time. A linear to constant separation, on a toy, with a mechanism that is entirely real. The genuinely useful algorithms are harder precisely because their oracles encode harder structure, but the move they make is this move, and Bernstein and Vazirani is the place you can watch it in its purest form.

The word to hold onto is parallel. The reason the quantum circuit reads all n bits at once, while the classical approach reads them one by one, is that the opening Hadamards created a superposition of every possible input, and the single oracle call acted on all of those inputs simultaneously. The classical machine is forced to be sequential, asking about one input at a time, so it learns one bit at a time. The quantum machine asks about all inputs in superposition, so the oracle stamps the entire secret into the phases in one go, and one interference step decodes the lot. That is the essence of what people gesture at, often badly, when they say quantum computers do things in parallel. They do not run many computations in separate universes that you can read independently, that is the wrong picture. They act on a superposition of all inputs at once and then use interference to distill a single, structured answer out of it. Bernstein and Vazirani is the cleanest place to see that real meaning of quantum parallelism, stripped of the science fiction, because the structured answer it distills is simply the secret, sitting there in the output, exactly right.

Where this sits in the bigger picture

It is worth knowing that Bernstein and Vazirani is not just a standalone curiosity, it is the friendly face of a much deeper pattern. The general shape of problem here, there is a hidden structure inside an oracle, and you want to extract it, is called a hidden structure or hidden subgroup problem, and it turns out to be one of the most important shapes in all of quantum algorithms. Bernstein and Vazirani is about the simplest instance of it, where the hidden structure is just a string and the extraction is a single clean readout.

Climb that same ladder and you reach the algorithms that actually matter. The period finding at the heart of Shor's factoring algorithm, the thing that genuinely threatens encryption, is a harder hidden structure problem of the same family: there is a hidden period inside a function, and the quantum computer extracts it through superposition, phase manipulation, and interference, the very same three moves you just watched, scaled up and made far more intricate. So when you run Bernstein and Vazirani and watch a secret string fall out in one shot, you are not just playing with a toy. You are seeing, in its cleanest possible form, the mechanism that the most consequential quantum algorithms are built on. The toy and the world changing algorithm are cousins. This is the cousin simple enough to fully understand, which is exactly why it is worth understanding completely.

A quick test before you move on

Close this and answer in your own words.

What does the oracle compute, and how many classical queries would it take to find the secret? If you cannot say the dot product of s and x mod 2, and n queries one bit at a time, reread the problem and the classical cost.

Why does a phase get kicked back onto exactly the qubits where the secret is 1? If your answer does not connect the CNOTs being placed only on those qubits to the |−⟩ ancilla, revisit the why it works section.

And what is the single most important difference between this algorithm and the last one? If extracting n bits instead of one, with the same machinery is not roughly your answer, reread the comparison, because it captures how the engine scales.

Where I am learning it

Free. Bernstein and Vazirani sits right after Deutsch and Jozsa in every algorithms course and in the IBM Quantum materials, and the two are best learned together since they share a circuit. What made it click for me was changing the secret to different strings and watching the circuit recover each one in a single shot, which turns the abstract claim into something you feel. As always, I learned it by running it, because a secret recovered in one query is far more convincing when it is your secret, on your machine, coming back exactly right.

A whole secret in one shot

Deutsch and Jozsa gave the first taste of quantum advantage. Bernstein and Vazirani makes it vivid: an entire hidden string, pulled out in a single query, where a classical computer would interrogate it bit by patient bit. The problem is a toy, as these early ones are, but the demonstration is unforgettable, because you watch parallelism do something a sequential machine simply cannot.

And it is the cleanest window onto the engine you will get. Phase kickback writes the secret into the phases, one qubit at a time, all at once. Interference reads it back, perfectly, in one layer. Every oracle algorithm ahead is a harder version of this, but none of them shows the move as plainly. If you understand how the secret got into the phases and how the Hadamards pulled it out, you understand the heart of quantum algorithms. The rest is structure.