Bernstein–Vazirani
The Bernstein–Vazirani algorithm finds a hidden string of n bits, called s, with just one question to a black box that computes f(x) = s·x mod 2. Any normal computer needs n questions, and that is proven. The gain is real but modest (n down to 1, not exponential). Today it is mostly used to test hardware and to show clearly how one quantum query can reveal n bits at once.
| Task | Best classical | Quantum |
|---|---|---|
| Recover the n-bit hidden string | n queries (provably optimal) | 1 query |
What problem does it solve?
A black box, called an oracle, hides a secret string s of n bits. You can give it an input x, which is also n bits. It answers with one bit. To get that bit, it looks only at the spots where s has a 1. It counts how many of those spots also have a 1 in x. If the count is odd, it answers 1. If even, it answers 0. This is called the parity. In code it is popcount(s & x) % 2. Your job is to find s with as few questions as possible.
Here is a small example. Say s = 101 and you ask with x = 111. The spots where s has a 1 are the first and last. x has a 1 in both of those. That is 2 ones, which is even, so the box answers 0.
Think of a website that returns a checksum over some secret set of your input bits. You want to learn which bits it uses. That set of bits is the mask.
How would a normal computer solve it?
Ask about one bit at a time. Send an input with a single 1 in position i and 0s everywhere else, like x = 0…010…0. The box answers exactly s_i, the secret bit in that spot. Do this for every spot and you have the whole string. That takes n questions.
No normal method can do better. Each answer is just one bit, and s holds n bits of information. You can't learn 10 bits from 9 yes-or-no answers. This limit is airtight.
So the normal cost is already cheap. It grows only in step with n, and the questions can all be asked at the same time. Keep that in mind when you weigh what the quantum version gains.
How does one quantum query recover all n bits?
It uses the same frame as Deutsch–Jozsa:
- Put a helper qubit, called the ancilla, into the state
|−⟩. - Put Hadamard (H) gates on all the input qubits.
- Ask the oracle once.
- Put Hadamard gates on the inputs again.
The oracle adds s·x into the ancilla using XOR (addition where 1 + 1 = 0). Because the ancilla is in |−⟩, each input pattern |x⟩ in the superposition picks up a sign instead: (−1)^(s·x). That is +1 or −1. The answer moves out of the ancilla and into the signs of the inputs. This trick is called phase kickback.
Here is the key idea. There are 2^n possible input patterns. The exact set of signs they end up with is the same set you get by putting Hadamards on the state |s⟩. The last layer of Hadamards just runs that step in reverse. So the inputs land on |s⟩ every time. No averaging and no repeats. You read the whole string off one measurement.
Think of a combination lock that clicks differently for each digit. One clever turn lets you hear all the clicks at once. Unlike a real lock, though, you don't hear anything along the way. You only get the final reading.
A quantum query is a stronger tool than a normal one. It runs the function once on a superposition. Then interference (amplitudes adding up or canceling) turns the pattern of signs back into bits. That is the honest story. Nothing was computed "in parallel universes."
What doesn't it prove?
Here are three honest warnings.
- The gain is modest, not exponential. It saves you going from
nquestions down to 1. For 100 bits, that is 100 questions down to 1. That makes a good demo. It is not the kind of gap that changes what we can compute in practice. - The oracle already holds the answer. The pattern of CX gates in the oracle is the string
s. The answer was built into the circuit. This is a fact about counting questions. It is not a way to pull unknown facts out of the world. - The stronger versions are a different story. A repeated, nested version of this problem gives a much bigger gap (called superpolynomial). But that is a different build. It does not run on today's hardware at useful sizes.
What does this look like on real hardware?
Bernstein–Vazirani is a favorite hardware test. It needs one ancilla, up to n CX gates, and only a few layers. There is also a single right answer to check against. Runs with 5–15 input qubits are routine on current devices. The chance of success drops as n grows.
It also shows the chip's wiring honestly. Every CX targets the same ancilla. On chips where each qubit connects to only a few others, the compiler must add chains of SWAP gates. Those move qubits next to the ancilla. That is connectivity costs made visible. Machines where every qubit connects to every other (trapped ions) handle this directly. Compare the same circuit across machine types on the hardware comparison page.