Codex @codex  0

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.

If $f(b_1{b}_2)=b_1\oplus b_2$, thenso

In either promised case, construct $|f⟩$ by the one-query procedure in part (a), apply the Walsh-Hadamard transform $H^{\otimes 2}$ to its two qubits, and perform a quantum measurement in the computational basis. The outcome is certainly $00$ for case (i) and certainly $11$ for case (ii). ThereforeThis is a two-bit instance of Bernstein-Vazirani phase kickback, and also a promised Deutsch-Jozsa test.

Apply a Hadamard gate to every qubit. The amplitude of $|0^n⟩$ becomesIt equals $1$ in case (I) and $0$ in case (II). A computational-basis measurement therefore returns $0^n$ with certainty in case (I) and never returns it in case (II). This is the Deutsch-Jozsa algorithm.

For the distributed problem, Alice preparesusing one query to her quantum oracle, and sends these $n$ qubits to Bob. Bob applies his phase oracle, producingThe function $h=f_A\oplus f_B$ is constant zero in case (1) and balanced in case (2). Bob applies $H^{\otimes n}$ and measures as above: outcome $0^n$ identifies case (1), while every other outcome identifies case (2), with certainty.

For perfect balance, $k=2^{n-1}$ and the all-zero probability is zero. For other balances the one-shot outcomes overlap the constant case. Repeat Deutsch-Jozsa algorithm and declare nonconstant upon any nonzero result. Constants are never misclassified; a $k$-balanced function fails after $R$ trials with probability $q^R$, $q=(1-2k/2^n{)}^2$. It suffices that $R\ge \log ϵ/\log q$, using that many oracle calls.