Bernstein–Vazirani hidden-string circuit

Bernstein–Vazirani recovers a hidden bit string $s\in\{0,1\}^n$ from an oracle for the parity function $f(x)=s\cdot x=\bigoplus_i s_i x_i \bmod 2$. The circuit prepares the output qubit in $|-\rangle$ and the input register in superposition, queries $U_f$ once — phase kickback writes $(-1)^{s\cdot x}$ onto $|x\rangle$ — and applies $H^{\otimes n}$ to the input register, which by the Hadamard/Fourier identity collapses it exactly to the basis state $|s\rangle$: measuring returns $s$ with certainty in the ideal circuit. Classically, determining an $n$-bit $s$ from black-box parity queries requires $n$ queries (one per standard basis vector), so the quantum circuit gives an $n$-to-$1$ query reduction under this promise, not a general search speedup. This record reviews the CX-based parity-oracle construction and its Deutsch–Jozsa-style readout; the one-query claim is scoped to this query/promise model, and oracle-construction and state-preparation costs stay visible rather than folded into the count.