Deutsch-Jozsa algorithm

The Deutsch-Jozsa algorithm uses phase kickback and interference to distinguish constant from perfectly balanced Boolean functions with one oracle call.

For an even-length Boolean string, one phase query followed by a known unitary extension can produce a zero-pair outcome with amplitude proportional to the zero-minus-one imbalance, or an index pair with amplitude proportional to the difference of their phase signs. A zero-pair observation certifies nonbalance. Every nonzero pair has opposite bits, so deleting it preserves the imbalance and allows recursion on two fewer indices. Ending with an empty list certifies balance. This quantum circuit is exact on all inputs and uses at most half the original length in queries, even without the constant-or-balanced promise.

If $F|0⟩=N^{-1/2}{\sum }_i|i⟩$, then applying a phase oracle followed by $F^{-1}$ gives amplitudeon $|0⟩$. It has modulus one for a constant Boolean function and vanishes for a balanced one.