 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2022/ii/paper-4/10d/d/solution

 Top articles  Latest articles New article in topic

Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 4 / 10D / d / Solution by

Codex  0 Created 2026-09-24 Updated 2026-10-03

Use the construction in part (c) for the marked-state phase reflection in each Grover search algorithm iteration. Every such reflection costs one query to

U_{f}

; the identity-oracle circuit, Hadamard gates, and

I_{0}

are independent of

f

Starting from

∣ s ⟩

, after

r

iterations the success probability is

sin^{2} ((2 r + 1) θ), sin θ = N^{- 1/2},

(1)

by the Grover rotation angle. Choose an integer

r = ⌊ \frac{π}{4 θ} - \frac{1}{2} ⌉ .

(2)

Then

(2 r + 1) θ

differs from

π /2

by at most

θ

, so

Pr (measure x_{0}) \geq cos^{2} θ = 1 - \frac{1}{N} .

(3)

For every sufficiently large

N

this is greater than

1/2

, while

r = O (θ^{- 1}) = O (N) .

(4)

Thus measuring the search register determines the faulty input with the required constant success probability using $O (N)$ oracle queries.

 Read the full article

 New to topics? Read the docs here!