Order finding is run for and with and register size

PHYSICS · Multi-part · Fermi University Physics · Quantum Information & Technology · The quantum circuit model and quantum algorithms · The quantum circuit model and quantum algorithms

Quantum Information and Technology, Ch Order finding and Shor's factoring algorithm

Problem

Order finding is run for

N = 11

and

a = 2

with

L = \lceil\log_2 11\rceil = 4

and register size

t = 2L+1 = 9

, so the output register has

2^9 = 512

values. A run returns the measured value

b = 154

. ((a)) Compute the continued fraction expansion of

b/2^t = 154/512

and list its convergents. ((b)) Take the convergents whose denominators are less than

N=11

and test those denominators in turn, smallest first, as candidate orders

r'

, by checking whether

a^{r'} \equiv 1 \pmod{11}

. ((c)) State the order

r

2

modulo

11

recovered from this run.

Browse the problem library