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.