Phase oracle ($O_f|x⟩=(-1{)}^{f(x)}|x⟩$)

A phase oracle encodes a Boolean function in the signs of computational basis states. Its diagonal entries have modulus one, so it is a unitary operator. The usual convention $O_f$ changes the sign when $f(x)=1$. A complemented convention $U_f|x⟩=(-1{)}^{f(x)\oplus 1}|x⟩$ instead changes the sign when $f(x)=0$, with $U_f=-O_f$; $\oplus$ denotes exclusive or. The two conventions differ by a global phase when used without coherent control, but the global phase of a controlled quantum gate makes that difference observable when the quantum oracle is controlled.

An unrestricted Boolean function on $M>2$ inputs cannot be classified as constant or nonconstant with certainty using a single phase oracle query, even with quantum ancillas. Write a purified query input as $|\Psi ⟩={\sum }_x|x⟩|a_x⟩$ with $p_x=\Vert a_x{\Vert }^2$ and ${\sum }_x{p}_x=1$. The zero constant function leaves it unchanged; the function supported only at $j$ produces a vector with inner product $1-2p_j$ with it. Perfect discrimination of pure states requires orthogonality, forcing $p_j=1/2$ for all $j$ and thus $M=2$, a contradiction. This is an exact quantum query complexity obstruction for all nonconstant inputs, rather than the restricted promise used by the Deutsch-Jozsa algorithm.