One-query obstruction to exact Boolean truth-table identification

ID: one-query-obstruction-to-exact-boolean-truth-table-identification

For a one-bit-input Boolean oracle, decompose a query input into target eigenstates. The unchanged target- sector has weight , while the target- sectors at inputs have weights . Distinguishing functions differing only at one entry requires , leaving . Then functions differing at both entries have output overlap , 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.

New to topics? Read the docs here!