= One-query obstruction to exact Boolean truth-table identification
For a one-bit-input Boolean oracle, decompose a query input into target $X$ eigenstates. The unchanged target-$+$ sector has weight $w_+$, while the target-$-$ sectors at inputs $0,1$ have weights $w_0,w_1$. Distinguishing functions differing only at one entry requires $1-2w_0=1-2w_1=0$, leaving $w_+=0$. Then functions differing at both entries have output overlap $-1$, so are the same physical ray. Thus one quantum query cannot identify all four truth tables with certainty, although the <Deutsch algorithm> finds their constant/balanced classification in one query.
Back to article page
