Deutsch–Jozsa algorithm is exact

By [F1] and [F3], after the oracle and final Hadamards the amplitude at address $y$ is ${\alpha }_y=2^{-n}{\sum }_{x\in \{0,1{\}}^n}(-1{)}^{f(x)+x\cdot y}\mathrm{.}$ For constant $f(x)=c$, factor out $(-1{)}^c$ and apply [F4] with $z=y$: ${\alpha }_y=(-1{)}^c$ if $y=0^n$ and $0$ otherwise.

For balanced $f$, [F2] gives equally many $+1$ and $-1$ terms in ${\alpha }_{0^n}$, so ${\alpha }_{0^n}=0$. For every $y$, the terminal output weight is $\mathrm{\mid }{\alpha }_y{\mathrm{\mid }}^2$ after summing the target coordinates: the state is ${\sum }_y{\alpha }_y\mathrm{\mid }y⟩\otimes \mathrm{\mid }-⟩$, the target has squared coordinate moduli $1\mathrm{/}2,1\mathrm{/}2$ by [F3]. Its unit-vector projector is a density operator by [F6], and [F5] and [F7] give the stated marginal. Thus the constant case outputs $0^n$ surely, while in the balanced case the probability of $0^n$ is zero.

The output weights sum to one by [F5]. Hence, when $f$ is balanced, all output probability is on strings other than $0^n$, which the output rule of [F1] labels balanced; in the constant case step 1.1 places all probability at $0^n$.

The procedure [F1] contains one oracle invocation. Its target preparation has one $X$ and one $H$, and its address has $n$ Hadamard gates before and $n$ after the query. Thus [F8] gives exactly one query and one $X$ and $2n+1$ $H$ gates, totaling $2n+2$ one-qubit gates; the terminal measurement is counted separately.