One-query Deutsch–Jozsa algorithm

Input. An integer $n\ge 1$ and a total Boolean oracle $f:\{0,1{\}}^n\to \{0,1\}$ satisfying the Deutsch–Jozsa promise of Deutsch–Jozsa promise, with an ordered $n$-qubit address register $A$ and one target qubit $T$ initialized to $\mathrm{\mid }{0}^n{⟩}_A\mathrm{\mid }0{⟩}_T$.

Output. One classical bit: output $0$ (constant) exactly when the measured address is $0^n$; otherwise output $1$ (balanced).

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$ once on $(A,T)$. Apply $H^{\otimes n}$ to $A$, measure $A$ in its ordered computational basis, and apply the output rule. 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.