Past exam of the mathematics course of the University of Cambridge / 2021 / iii / Paper 324 / 1 / a

Solution

The hidden subgroup problem supplies an oracle

f : G \to X

promised to satisfy

f (g_{1}) = f (g_{2}) ⟺ g_{1} H = g_{2} H

for an unknown subgroup

H \leq G

; the task is to determine

H

f : Z_{K} \to Z

with least period

r

dividing

K

G = Z_{K}

and hidden subgroup

H = ⟨ r ⟩ = {0, r, 2 r, \dots, K - r} .

r

. Periodicity makes

f

constant on each coset, while injectivity within a period makes values on distinct cosets different. Determining

H

, or its least positive generator

r

There are no discussions about this article yet.

There are currently no matching articles.