 Solution

ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2020/quantum-information/3/d/solution

Apply parts (b)(ii) and (b)(iii), keeping the oracle's minus sign:

W V_{f} ∣ e_{0} ⟩ = \frac{1}{N} [\frac{2 ( S _{0} - S _{1} )}{N} ∣ J ⟩ - ∣ A_{0} ⟩ + ∣ A_{1} ⟩] = \frac{1}{N} [∣ J ⟩ - ∣ A_{0} ⟩ + ∣ A_{1} ⟩] = \frac{2}{N} ∣ A_{1} ⟩ = \frac{2}{N} f (x) = 1 \sum ∣ x ⟩ .

The middle equality uses part (a), and the last uses

∣ J ⟩ = ∣ A_{0} ⟩ + ∣ A_{1} ⟩

. The final squared norm is

4 S_{1} / N = 1

, providing a normalization check.

W = 2∣ e_{0} ⟩ ⟨ e_{0} ∣ - I

fixes

∣ e_{0} ⟩

and negates its orthogonal complement. Its action on amplitudes is inversion about the mean. The negative of this reflection would change the final vector by an overall global phase, but mixing those conventions midway would give incorrect intermediate signs.^[ref]

 New to topics? Read the docs here!