Suppose f(x) = s · x mod 2, the parity of the bits that x shares with a hidden string s. Classically, each query of f reveals one bit of s at best: asking about x = 100 gives the first bit, and so on, n queries for n bits.

The Bernstein–Vazirani algorithm finds all of s with one query, with the circuit of Deutsch–Jozsa: inputs in superposition, the target in |−⟩, the oracle, and Hadamards on the inputs. The oracle leaves the state

Σₓ (−1)^(s·x) |x⟩ / √2ⁿ,

and that pattern of signs is exactly what n Hadamards turn into the single basis state |s⟩.

Remember the bit order: the outcome is written c[2] c[1] c[0], the highest bit first. An oracle that reads `q[0]` and `q[2]` has the hidden string 101.