Let and . Order finding is run with control qubits, so the output register has…

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

Let

N=21

and

a=2

. Order finding is run with

t=9

control qubits, so the output register has

2^9=512

values, and the input to phase estimation is the easy state

|1\rangle=\tfrac1{\sqrt r}\sum_{s=0}^{r-1}|u_s\rangle

. ((a)) Find the order

r

2

modulo

21

, and list the

r

ideal phases

s/r

s=0,\ldots,r-1

. ((b)) Phase estimation on a single eigenstate

|u_s\rangle

returns the reading nearest

2^t s/r

with the Dirichlet-kernel probability of Eq. (7.14); averaged over the

r

equally weighted branches,

s=0,\ldots,r-1

, this gives the reading distribution actually produced by

|1\rangle

. Compute this averaged probability for the ten readings

b=0,85,86,170,171,256,341,342,426,427

. ((c)) One run returns

b=171

; a second returns

b=256

. Expand each

b/2^t

as a continued fraction, and for each take the last convergent whose denominator is below

N=21

. Test each candidate order

r'

against

a^{r'}\equiv1\pmod{21}

, and show both fail. Two failed candidates

r_1'

and

r_2'

obtained this way always divide the true order

r

, so their least common multiple is itself always a candidate worth testing; taking this as given, test

\mathrm{lcm}(r_1',r_2')

and show that it passes. ((d)) Using the order recovered in part (c), extract the two factors of

21

Browse the problem library