= Solution
Let $N_0,N_1$ be the two output counts. Choose a known preparation unitary F with $F|0\rangle=N^{-1/2}\sum_x|x\rangle=:|s\rangle$. The <Deutsch-Jozsa algorithm> applies the supplied <phase oracle> $O_f|x\rangle=(-1)^{f(x)}|x\rangle$ and then $F^\dagger$, declaring constant exactly for outcome 0. Its amplitude on that outcome is
$$
\langle0|F^\dagger O_fF|0\rangle=\langle s|O_f|s\rangle=\frac{N_0-N_1}{N}.
$$
This is the <Deutsch-Jozsa test with an arbitrary uniform-state unitary>. For $N=2^m$, the usual preparation is $F=H^{\otimes m}$; the argument itself needs only a uniform preparation on the stated N-dimensional space.
For an actually constant-up-to-k function, the two counts are $k$ and $N-k$, so the outcome-0 <probability> is $(1-2k/N)^2$. The error is returning the other label. Therefore
$$
\boxed{P_{\rm error}=1-\left(1-\frac{2k}{N}\right)^2=\frac{4k}{N}\left(1-\frac{k}{N}\right).}
$$
Here the possible count k is nonnegative, and the supplied bound implies $0\le k/N\le1/8$. The error is consequently at most $7/16$; at $k=0$ it vanishes. This is the error conditional on the stated constant-up-to-k case, not an average over unspecified prior <probabilities>. For comparison, the printed balanced-up-to-k definition has count \i[difference] $\pm k$, so its outcome-0 <probability> would be $(k/N)^2$, not the expression for the constant-up-to-k case. No change to that promise definition is made.
Back to article page
