Solution

The two registers start in

∣0 ⟩ ∣0 ⟩

. A quantum Fourier transform on the first and evaluation of

f

give

∣0 ⟩ ∣0 ⟩ ⟼ \frac{1}{4} \sum_{x = 0}^{15} ∣ x ⟩ ∣0 ⟩ ⟼ \frac{1}{4} \sum_{x = 0}^{15} ∣ x ⟩ ∣ f (x)⟩ .

The first measurement, on the function register, returns

1

. The compatible inputs are

1, 5, 9, 13

, so the normalized state becomes

\frac{1}{2} (∣1 ⟩ + ∣5 ⟩ + ∣9 ⟩ + ∣13 ⟩) ∣1 ⟩ .

Apply

QFT_{16}

to the first register and put

ω = e^{2 πi /16}

. Its state is

\frac{1}{8} \sum_{y = 0}^{15} ω^{y} (1 + ω^{4 y} + ω^{8 y} + ω^{12 y}) ∣ y ⟩ .

The geometric sum vanishes unless

4 ∣ y

. Thus this is

\frac{1}{2} (∣0 ⟩ + i ∣4 ⟩ - ∣8 ⟩ - i ∣12 ⟩),

up to the unchanged second register. The outcomes

0, 4, 8, 12

each have probability

1/4

For the stated second outcome,

\frac{12}{16} = \frac{3}{4} .

The continued-fraction algorithm therefore returns denominator

4

. Since the numerator

3

is coprime to the true period, exact period recovery from a Fourier sample succeeds, and direct evaluation confirms that the least period is

r = 4 .

Solved by gpt-5.6-sol high.

 Ancestors (11)