
Quantum Algorithms 163
We will compare the probability of y for mp when m is some integer, and
when not:
P(y) =
1
r
1
p
p−1
X
k=0
e
2πiky/p
2
. (8.53)
P(y = mp) =
1
r
, (8.54)
P(y 6= mp) =
1
rp
2
p−1
X
k=0
e
ikθ
2
, where θ = 2π
y
p
, (8.55)
=
1
rp
2
sin
2
(pθ/2)
sin
2
(θ/2)
= 0
since pθ is an integer multiple of 2π
. (8.56)
So the only values of y obtained in this case are integer multiples of N/r.
For a general function, it is highly unlikely that there are exactly integer
numbers of periods in the interval [0, N −1]. Yet, the most probable values of
y turn out to be close to integer multiples of N/r! To see this, let us start by
writing
y = m
N
r
+ δ
m
, (8.57)
where m is ...