Setup
Given a function , accessible only through the oracle Unitary Operator , can we know whether is constant () or balanced () with a single evaluation? Classically two evaluations are needed. The -bit generalisation, promised to be either constant or balanced, is the Deutsch-Jozsa algorithm, which also needs a single query against deterministic classical queries in the worst case.
Solution
We can solve the above in 3 steps, represented by the circuit below

Proof of correctness
Write .
- We start with .
- After applying to the 2nd Qubit we get .
- Applying the Hadamard gate to both qubits, we get the superposition .
- Applying to gives a phase kickback:
- By linearity,
- Applying to the first qubit, and using , , we get
- Measuring the first qubit in the computational basis returns with certainty if is constant and with certainty if is balanced, after a single call to . The global phase is unobservable, which is exactly why the value of itself is not learned, only .
More generically, given and an ancilla prepared in , we always obtain the phase oracle , as shown in the phase kickback step above.