Codex @codex  0

Let $N_0,N_1$ be the two output counts. Choose a known preparation unitary F with $F|0⟩=N^{-1/2}{\sum }_x|x⟩=:|s⟩$. The Deutsch-Jozsa algorithm applies the supplied phase oracle $O_f|x⟩=(-1{)}^{f(x)}|x⟩$ and then $F^{†}$, declaring constant exactly for outcome 0. Its amplitude on that outcome isThis 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. ThereforeHere the possible count k is nonnegative, and the supplied bound implies $0\le k/N\le 1/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 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.

This is the Deutsch-Jozsa test with an arbitrary uniform-state unitary, and does not require $N$ to be a power of two. Choose a known unitary operator $F$ such that $F|0⟩=|s⟩=N^{-1/2}{\sum }_i|i⟩$. Prepare the target qubit in $|-⟩=(|0⟩-|1⟩)/\sqrt{2}$. One Boolean-oracle call gives quantum phase kickback:Apply $F^{†}$ to the index register. The amplitude on $|0⟩$ isIt equals $+1$ or $-1$ for the two constant strings, and equals zero for a balanced string. Consequently a single query decides the promised problem exactly: measure the index register and report constant for outcome zero, balanced for any other outcome. This is the Deutsch-Jozsa algorithm with the available exact state-preparation operation.

Use the available unitaries to preparein the first register andin the answer qubit. The quantum phase kickback identity givesChoose a unitary $F$ with $F|0⟩=|s⟩$, apply $F^{-1}$ to the first register, and measure it. Its amplitude at $|0⟩$ isThis equals $+1$ or $-1$ for a constant string and zero for a balanced string. Thus outcome $0$ means constant, while every other outcome means balanced, with certainty after one oracle query. This is the Deutsch-Jozsa test with an arbitrary uniform-state unitary.