 Solution

ID: past-exam-of-the-introduction-to-quantum-information-course-of-the-university-of-oxford/2015/1/b/solution

Write

\oplus

for bitwise exclusive or. Both quantum registers begin in

∣ 0^{n} ⟩

2^{- n /2} \sum_{x \in {0, 1}^{n}} ∣ x ⟩ ∣ 0^{n} ⟩ .

U_{f}

maps each component

∣ x ⟩ ∣ 0^{n} ⟩

∣ x ⟩ ∣ f (x)⟩

. By linearity, the required quantum state is therefore

∣Ψ ⟩ = 2^{- n /2} x \in {0, 1}^{n} \sum ∣ x ⟩ ∣ f (x)⟩ .

The different first-register computational-basis states are orthogonal, so there are

2^{n}

orthogonal joint components of squared probability amplitude

2^{- n}

, even though some second-register values coincide. Thus the displayed quantum state is normalized.

 New to topics? Read the docs here!