Codex @codex  0

 Incoming links: Boolean quantum oracle

Past exam of the mathematics course of the University of Cambridge / 2019 / ii / Paper 3 / 10D / b / Solution Created 2026-09-24 Updated 2026-10-03

When

k = N /4

,

sin θ = \frac{1}{2}, θ = \frac{π}{6} .

One Grover search algorithm iteration therefore gives

Q ∣ ψ_{0} ⟩ = sin (3 θ) ∣ ψ_{G} ⟩ + cos (3 θ) ∣ ψ_{B} ⟩ = ∣ ψ_{G} ⟩ .

The selective sign change

I_{G}

is implemented with one application of the Boolean quantum oracle: prepare its answer qubit in

∣ - ⟩ = (∣0 ⟩ - ∣1 ⟩) / 2

and use quantum phase kickback, obtaining

(- 1)^{f (x)}

on each

∣ x ⟩

. The remaining operations

H_{n}

,

I_{0}

, and the final computational-basis measurement are independent of

f

. Measurement of

∣ ψ_{G} ⟩

returns some

x \in G

with probability one, so exactly one query to

U_{f}

suffices.

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2020 / ii / Paper 3 / 15C / b / i / Solution Created 2026-09-24 Updated 2026-10-03

Starting from

∣ 0^{n} ⟩ ∣ 0^{n} ⟩

, the first layer of Hadamard gates gives

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

The Boolean quantum oracle then gives

2^{- n /2} \sum_{x \in B_{n}} ∣ x ⟩ ∣ f (x)⟩ .

Using the Walsh-Hadamard transform identity

H^{\otimes n} ∣ x ⟩ = 2^{- n /2} \sum_{y \in B_{n}} (- 1)^{x \cdot y} ∣ y ⟩,

the final state is

2^{- n} x, y \in B_{n} \sum (- 1)^{x \cdot y} ∣ y ⟩ ∣ f (x)⟩ .

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2021 / ii / Paper 2 / 10D / Solution Created 2026-09-24 Updated 2026-09-25

Apply a Hadamard gate to every qubit. The amplitude of

∣ 0^{n} ⟩

becomes

⟨ 0^{n} ∣ H^{\otimes n} ∣ ξ ⟩ = \frac{1}{2 ^{n}} \sum_{x \in B_{n}} (- 1)^{f (x)} .

It equals

1

in case (I) and

0

in case (II). A computational-basis measurement therefore returns

0^{n}

with certainty in case (I) and never returns it in case (II). This is the Deutsch-Jozsa algorithm.

For the distributed problem, Alice prepares

∣ ξ_{A} ⟩ = 2^{- n /2} \sum_{x} (- 1)^{f_{A} (x)} ∣ x ⟩

using one query to her quantum oracle, and sends these

n

qubits to Bob. Bob applies his phase oracle, producing

2^{- n /2} \sum_{x} (- 1)^{f_{A} (x) \oplus f_{B} (x)} ∣ x ⟩ .

h = f_{A} \oplus f_{B}

is constant zero in case (1) and balanced in case (2). Bob applies

H^{\otimes n}

and measures as above: outcome

0^{n}

identifies case (1), while every other outcome identifies case (2), with certainty.

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 324 / 3 / ii / Solution 2026-09-28

If some integer

k

obeys

(2 k + 1) θ = π /2

, ordinary amplitude amplification already gives

∣ g ⟩

exactly. For a general known

θ

, use exact amplitude amplification. Choose

k

so that

θ^{'} = \frac{π}{4 k + 2} \leq θ

and put

c = sin θ^{'} / sin θ \leq 1

. Append an ancilla and coherently arrange that its designated good value has amplitude

c

conditional on the original register being good. With the enlarged good subspace defined by

f (x) = 1 and ancilla = 0,

the starting state's total good amplitude is

c sin θ = sin θ^{'}

.

Apply the amplitude amplification theorem

k

times to this enlarged problem. Its final good amplitude is

sin ((2 k + 1) θ^{'}) = sin \frac{π}{2} = 1.

The Boolean quantum oracle implements the reflection

I_{G}

by phase kickback, and the known state-preparation circuit implements the reflection about the starting state by prepare--reflect--unprepare. A final computational-basis measurement therefore yields an

x

with

f (x) = 1

with certainty.

 Read the full article