Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 3 / 10D / d

Table of contents
- Solution d

Solution

The quantum Fourier transform measurement supplies a rational approximation

\frac{c}{2 ^{m}} ≃ \frac{s}{r},

where

r

is the desired multiplicative order. Here

\frac{c}{2 ^{m}} = \frac{256}{512} = \frac{1}{2} .

Its reduced continued fraction convergent has denominator two, so continued-fraction recovery in quantum order finding proposes

r = 2

. Direct order verification from divisors confirms it:

8^{2} = 64 \equiv 1 (mod 21), 8 \neq \equiv 1 (mod 21) .

Hence

ord_{21} (8) = 2.

As a check, the classical final step of the Shor algorithm gives

g cd (8 - 1, 21) = 7, g cd (8 + 1, 21) = 3.

 Ancestors (10)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version