Setup

Given an $n$ -bit Unitary Operator $f : F_{2^{n}} \to F_{2^{n}}$ , can we know whether this function is constant with a single evaluation?

Solution

We can solve the above in 3 steps, represented by the circuit below

We have $∣ ψ_{0} ⟩ = ∣ 00 ⟩$ .
After applying $X$ to the 2nd Qubit we get $∣ 01 ⟩$
Applying the Hadamard gate $H$ to both matrices, we get the superposition $∣ 00 ⟩ - ∣ 01 ⟩ + ∣ 10 ⟩ - ∣ 11 ⟩$ , up to normalisation.
Applying $U_{f}$ we get $∣ 0 (0 \oplus f (0)) ⟩ - ∣ 0 (1 \oplus f (0)) ⟩ + ∣ 1 (0 \oplus f (1)) ⟩ - ∣ 1 (1 \oplus f (1)) ⟩$ .
After applying the Hadamard gates on each bit individually, we get the Quantum state $∣ ψ_{1} ⟩ = \sum_{i = 0}^{2^{n + 1} - 1} ∣ i_{2} ⟩$ , up to normalisation, where $i_{2}$ is the binary representation of $i$ , i.e. $5_{2} = 101$ .
$∣ ψ_{2} ⟩ = U_{f} ∣ ψ_{1} ⟩ = \sum_{i = 0}^{2^{n + 1} - 1} ∣ i_{2} ⟩$
Complete the proof above.

More generically, there is always a way of building an Operator such that $U_{f} ∣ x ⟩ = (- 1)^{f (x)} ∣ x ⟩$ .