Quantum oracle ($U_f|x,y⟩=|x,y\oplus f(x)⟩$)

A quantum oracle supplies coherent access to a function through a specified unitary operator. For a function with binary string output, the standard construction retains the input and adds the output into an answer quantum register by bitwise exclusive or. This operation is its own inverse, even when the function is not injective. A Boolean quantum oracle is the single-output-bit case; Simon's algorithm uses several answer qubits. Other encodings, such as a modular-addition quantum oracle or a phase gate encoding, require their own explicit query conventions.

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.