Past exam of the computer science course of the University of Oxford / 2023 / Quantum information / 2 / d

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 asThe 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 ⟩$ 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 producesAny 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 ⟩=|\Psi ⟩$ and $E|{\Psi }_j⟩=0$, forcing $⟨\Psi |{\Psi }_j⟩=0$.

Therefore exact classification requires $p_j=1/2$ for every $j$. Summing giveswhich contradicts $M>2$. Thus 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.