One-query Bernstein–Vazirani algorithm

Input. An integer $n\ge 1$ and an oracle $f_a(x)=a\cdot x$ satisfying the no-offset Bernstein–Vazirani promise of Bernstein–Vazirani no-offset promise, on an ordered $n$-qubit address register $A$ and one target qubit $T$ initialized to $\mathrm{\mid }{0}^n{⟩}_A\mathrm{\mid }0{⟩}_T$.

Output. The measured $n$-bit address, interpreted as the secret $a$.

Gate model. The declared nonoracle gate alphabet permits exact callable $H$ and $X$ gates, each occurrence charged as one nonoracle gate under Nonoracle quantum gate cost. The supplied standard bit query is charged separately as one oracle call.

Procedure. Apply $H^{\otimes n}$ to $A$. Apply $X$ and then $H$ to $T$. Invoke the standard XOR oracle $U_{f_a}$ once on $(A,T)$. Apply $H^{\otimes n}$ to $A$, measure $A$ in its ordered computational basis, and output the measured string. There are no intermediate measurements, loops, or failure branches.

The terminal measurement is specified by Normalized output law for finite quantum query branches and is separate from the declared one-qubit gate resource. No circuit-uniformity or classical bit-time bound is asserted.

The standard XOR query and quantum-query algorithm conventions are those of Standard bit-flip query convention and Quantum query algorithm. The phase action used by the procedure is verified by One standard query implements one phase query.