= Solution
We prove the <one-query constancy obstruction for phase oracles> while allowing arbitrary <quantum ancillas>. By <purification of a density operator>, the <quantum state> immediately before the sole query can be taken as
$$
|\Psi\rangle=\sum_{x=0}^{M-1}|x\rangle|a_x\rangle,
\qquad p_x=\langle a_x|a_x\rangle,
\qquad\sum_xp_x=1.
$$
The <ancilla> vectors need not be normalized or <orthogonal>. Classical randomness and earlier <quantum measurements> can be included in additional <ancillas>; allowing access to these systems only gives the proposed algorithm more power.
For the zero <constant function>, the <phase oracle> is $I$, leaving $|\Psi\rangle$ unchanged. For each $j$, consider the <Boolean function> that is one at $j$ and zero elsewhere. Since $M>2$, it is nonconstant, and its <phase oracle> produces
$$
|\Psi_j\rangle=|\Psi\rangle-2|j\rangle|a_j\rangle,
\qquad\langle\Psi|\Psi_j\rangle=1-2p_j.
$$
Any later fixed <unitary transformation> preserves these <inner products>. An arbitrary final <quantum measurement> cannot distinguish the constant output from each nonconstant output with certainty unless they are <orthogonal>, by <perfect discrimination of pure states requires orthogonality>. Explicitly, an accepting <POVM> effect $E$ would satisfy $E|\Psi\rangle=|\Psi\rangle$ and $E|\Psi_j\rangle=0$, forcing $\langle\Psi|\Psi_j\rangle=0$.
Therefore exact classification requires $p_j=1/2$ for every $j$. Summing gives
$$
\boxed{1=\sum_{j=0}^{M-1}p_j=\frac M2,}
$$
which contradicts $M>2$. Thus \b[one query cannot decide constancy with certainty]. The other <constant function> gives $-I$, differing only by a <global phase>, so it does not change the argument. For comparison, $M=2$ permits $p_0=p_1=1/2$; the impossibility arises from demanding the test work for every nonconstant <Boolean function>.
Back to article page
