= One-query constancy obstruction for phase oracles
{title2=$M>2\implies Q_E(\text{constancy};\text{phase oracle})>1$}
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\rangle=\sum_x|x\rangle|a_x\rangle$ with $p_x=\|a_x\|^2$ and $\sum_xp_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>.
Back to article page
