Bernstein–Vazirani Algorithm

Recover a hidden pattern, not a truth table

Bernstein–Vazirani asks you to find an unknown n-bit string s. You may query a function that returns the parity of selected input bits: multiply corresponding bits of s and x, then XOR the products. The output is one bit, even though s has n bits. A coherent quantum query and an appropriate basis change recover the entire hidden string in the ideal model.

Start with Deutsch–Jozsa and phase kickback. You need the binary dot product, which differs from an ordinary real inner product. Its arithmetic is modulo two: one plus one becomes zero when contributions are combined by XOR.

WORKED DIAGRAM · A04Recover hidden string 101

For s=101, the oracle sign factorises across the first and third wires. H converts the resulting minus-plus-minus product into 101 with probability one.

Define the promise carefully

The oracle function has the form

$$f_s(x)=s\cdot x=s_0x_0\oplus s_1x_1\oplus\cdots\oplus s_{n-1}x_{n-1}.$$

The goal is to return s. Input access is a reversible bit oracle or its corresponding phase oracle. A deterministic classical method can query each unit-vector input: putting one in position j and zero elsewhere returns s in that position. This uses n queries. Each ordinary query yields one bit; an exact classical strategy needs enough information to distinguish all two-to-the-power-n possible strings.

The quantum method uses one coherent query, but that oracle can contain many elementary gates. If the hidden string were explicitly supplied as an ordinary classical input, there would be no mystery to solve. The separation concerns the specified black-box access, not magical extraction of a secret from any physical system.

Procedure and diagram

Prepare the n-qubit input uniformly with H gates. Prepare a minus target for a bit oracle, or use an explicitly supplied phase oracle. Query once, attaching phase negative one to the power s dot x. Apply H again to every input qubit. Measure the input register in Z and interpret the bitstring as s in the stated wire order.

For the three-bit example, the phase oracle factors into Z on q0 and q2, with no phase flip on q1. The diagram groups these operations as one invocation of the specified oracle interface. Its output is minus, plus, minus before the last H layer. A bit-oracle implementation instead includes the separately prepared minus target, which remains factored out. Both descriptions must preserve the same input-relative phase pattern.

Worked example: s equals 101

The function returns the XOR of the first and third input bits. Its value is zero on 000, one on 001, zero on 010, one on 011, one on 100, zero on 101, one on 110 and zero on 111. These eight values would require several ordinary queries to identify by a generic classical strategy, but their phase pattern has a compact factorisation.

After the quantum query, the input state is minus on the first wire, plus on the second and minus on the third. To see this, note that the phase factor splits into the product of a sign for the first bit and a sign for the third bit. H maps each minus to one and each plus to zero. The final state is therefore 101, with probability one.

This example is particularly useful because it does not need entanglement among the input qubits. The phase pattern factorises. Quantum advantages in a chosen oracle model cannot always be explained simply by pointing to entanglement. The access model and coherent basis transformation are central here.

Why the transform returns s

The amplitude of output z after the last H layer is the average of signs determined by the binary dot product of s XOR z with x. If z equals s, that dot product is zero for every x, so every contribution is positive and the amplitude is one. If z differs from s, choose a position where they differ. Pair each input x with the input obtained by flipping that position. The two contributions have opposite signs and cancel.

Thus all wrong outputs have zero amplitude and the correct output has unit amplitude. This pairing argument gives a clear correctness proof without expanding a large matrix. It is the orthogonality of binary Fourier characters expressed as a cancellation rule.

Constant offsets and conventions

Suppose the oracle is affine: f(x) equals s dot x XOR a fixed bit b. The extra bit adds a common sign negative one to the power b after phase kickback. The input measurement still returns s. It does not reveal b through that readout. A separate ordinary query at zero would reveal the offset, if the task also requires it.

This is another example of output design. The phase procedure discards a global distinction while preserving the relative pattern it needs. Do not claim that recovering s means recovering every possible detail of an arbitrary function. The linear or affine promise is essential. For a nonlinear function, the final H measurement samples its Fourier spectrum rather than necessarily returning one deterministic hidden string.

Costs and a sensible experiment

Outside the oracle, preparation and readout use a number of simple gates linear in n. The query advantage is one versus n under the given access and exact-success model. A physical implementation of a parity oracle may itself use a number of controlled gates linear in the weight of s, plus calibration and error costs. Report both the oracle count and the implementation when discussing runtime.

For a hand experiment, choose a hidden three-bit string, write the phase sign for all eight inputs, and factor the result into plus/minus states. Predict the final measurement before simulating. Test the all-zero string, a single-one string and 101. These cases catch accidental assumptions that every promised function must be balanced: the all-zero hidden string gives a constant-zero function, but the algorithm still works.

Exercises

1. Let s be 011. What are f(100), f(010) and f(111)? What string should the quantum circuit return?

2. Add an affine offset b equal to one. Which final probabilities change? How could you learn b separately?

Worked answers

1. The function ignores the first bit and XORs the last two. The values are zero, one and zero respectively. The final quantum output is 011 under the book’s leftmost-bit convention.

2. No input-register probabilities change because the offset contributes only a common phase. Querying the affine function at 000 returns b directly. Recovering the slope string and recovering the offset are distinct output tasks.

Source

The Bernstein–Vazirani section of IBM’s query-algorithm lesson explains the linear-function promise and its use of the same Hadamard-query-Hadamard circuit.

Check your understanding

PAUSE & THINK

An affine oracle adds a constant-one offset to s·x. What changes in the hidden-string measurement?

Choose your answer

Every output bit flipsNothing; the extra sign is globalThe output becomes random

Check my answer

Answer: Nothing; the extra sign is global. The offset negates every amplitude by the same factor. The circuit still returns s; learning the offset is a separate task.