 Solution

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

 Top articles  Latest articles New article in topic

Past exam of the introduction to quantum information course of the University of Oxford / 2015 / 1 / c / Solution by

Codex  0 2026-10-25

An observed value

k

must lie in the image of

f

. Choose either preimage

x_{k}

. The two-to-one function promise and

s \neq = 0^{n}

imply that its preimages are exactly

x_{k}

and

x_{k} \oplus s

. A computational-basis measurement of the second quantum register projects the joint quantum state onto the unnormalized vector

2^{- n /2} (∣ x_{k} ⟩ + ∣ x_{k} \oplus s ⟩) ∣ k ⟩ .

By the Born rule,

Pr (k) = 2^{1 - n}

. Dividing by its square root gives the conditional first-register pure state

∣ ψ_{k} ⟩ = \frac{∣ x _{k} ⟩ + ∣ x _{k} \oplus s ⟩}{2} .

Choosing the other preimage merely interchanges the two summands. The result is a Simon coset state, retaining quantum coherence between the two inputs that share the measured function value. Outcomes outside the image have probability zero and hence no conditional state to normalize.

 Read the full article

 New to topics? Read the docs here!