Deutsch algorithm

The one-input Deutsch algorithm determines whether a Boolean function is constant or balanced using one Boolean quantum oracle call. Initialize the input qubit in $|+⟩$ and the answer qubit in $|-⟩$. Quantum phase kickback changes the input to $(-1{)}^{f(0)}(|0⟩+(-1{)}^{f(0)\oplus f(1)}|1⟩)/\sqrt{2}$. A Hadamard gate and computational-basis measurement therefore return the parity $f(0)\oplus f(1)$ with certainty.

If the input qubit of the Deutsch algorithm acquires conditional environment states with overlap $⟨e_0|e_1⟩=v{e}^{i\alpha }$ between its two Hadamard gates, its fixed zero-for-constant, one-for-balanced rule succeeds with probability $(1+v\cos \alpha )/2$. A known phase can be compensated before the last Hadamard gate, raising the success probability to $(1+v)/2$. An orthogonal pair of environment states gives $v=0$ and destroys all information in the input qubit about the answer; unit overlap modulus preserves coherence up to a known phase.