A High-Speed Overview of Shor’s Algorithm
From last time:
• The quantum Fourier transform is
q−1
1 (cid:88)
QFT |x⟩ = √ e2πixk/q|k⟩.
q
k=0
• The inverse quantum Fourier transform is
q−1
1 (cid:88)
IQFT |x⟩ = √ e−2πixℓ/q|ℓ⟩.
q
ℓ=0
• The controlled Pauli Z gate on a 2-qubit system is
CZ |xy⟩ = eiπxy |xy⟩.
1/12
A High-Speed Overview of Shor’s Algorithm
Let’s jump again from n qubits to 2n qubits. Denote a state by
|x,y⟩, where x represents the first n qubits and y represents the
second n qubits (x and y are called registers). Let q = 2n as
before.
We can extend the idea of the controlled Pauli Z gate to this
system. In fact, it looks almost the same:
CZ |x,y⟩ = e2πixy/q|x,y⟩.
QUICK EXERCISE. Let QFT act on |x,y⟩ by applying the QFT
2
operator to the |y⟩ component, and similarly for IQFT . Carefully
2
work out
IQFT ·CZ ·QFT |x,y⟩.
2 2
2/12
A High-Speed Overview of Shor’s Algorithm
q−1
1 (cid:88)
Answer. First, QFT |x,y⟩ = √ e2πiyk/q|x,k⟩.
2
q
k=0
Applying CZ to each |x,k⟩ yields e2πixk/q|x,k⟩. Therefore
q−1
1 (cid:88)
CZ ·QFT |x,y⟩ = √ e2πiyk/qe2πixk/q|x,k⟩
2
q
k=0
q−1
1 (cid:88)
= √ e2πik(x+y)/q|x,k⟩.
q
k=0
Lastly, we apply IQFT :
2
q−1
1 (cid:88)
IQFT ·CZ ·QFT |x,y⟩ = √ e2πik(x+y)/qIQFT |x,k⟩
2 2 2
q
k=0
3/12
A High-Speed Overview of Shor’s Algorithm
q−1 q−1
1 (cid:88) 1 (cid:88)
= √ e2πik(x+y)/q√ e−2πikℓ/q|x,ℓ⟩
q q
k=0 ℓ=0
q−1(cid:32)q−1 (cid:33)
1 (cid:88) (cid:88)
= e2πik(x+y−ℓ)/q |x,ℓ⟩.
q
ℓ=0 k=0
The sum over k is 0 unless (x +y −ℓ) mod q = 0: that is, if
ℓ = (x +y) mod q. For that particular value of ℓ,
e2πik(x+y−ℓ)/q = 1. Therefore the expression reduces to
q−1
1 (cid:88)
IQFT ·CZ ·QFT |x,y⟩ = 1·|x,(x +y) mod q⟩
2 2
q
k=0
= |x,(x +y) mod q⟩.
We have invented a quantum adder!
4/12
A High-Speed Overview of Shor’s Algorithm
There are also implementations of quantum multipliers using
similar techniques. Hopefully plausible conceptual jump: from now
on, we assume that our quantum computer can do standard
arithmetic.
Part 4: Shor’s Algorithm for Prime Factorization
Let n be the number that we wish to factor. Assume that n is not
prime, not the power of a prime, and not even.
Fact. The process of finding the greatest common divisor of two
integers can be performed efficiently on a classical computer.
Choose a random integer x that has no common factors with n
(verified by showing that gcd(x,n) = 1.)
5/12
A High-Speed Overview of Shor’s Algorithm
Proposition. If we can find the smallest positive integer r such
that xr ≡ 1 mod n, then we have a good chance of find a
nontrivial factor of n.
Idea of proof. Let r be the smallest positive integer such that
xr ≡ 1 mod n. If r is odd, the process fails and we have to restart
with a new value of x.
Suppose r is even. By definition, xr ≡ 1 mod n, which means that
xr −1 = dn for some integer d. Observe that
dn = xr −1 = (xr/2−1)(xr/2+1).
By the choice of r, xr/2−1 cannot be a multiple of n. If xr/2+1
is a multiple of n, the process fails and we have to restart with a
new value of x.
Suppose xr/2+1 is not a multiple of n. Then gcd(n,xr/2−1) is a
nontrivial divisor of n, as is gcd(n,xr/2+1).
6/12
A High-Speed Overview of Shor’s Algorithm
The “good chance” part comes from some number theoretical
results that demonstrate that the failure cases are rare when x is
chosen at random (details omitted – see Shor’s paper).
Given n and x, it remains to determine the smallest positive r such
that xr ≡ 1 mod n. Note that r < n (can you see why?).
Let q be the integer power of 2 such that n2 ≤ q < 2n2.
Now build a quantum computer consisting of two registers. The
first has lg(q) qubits, and the second has lg(n) qubits. Use the
notation |x,y⟩ as before.
7/12
A High-Speed Overview of Shor’s Algorithm
Quantum step 1. Put the quantum computer into the state
q−1
1 (cid:88)
√ |k,0⟩.
q
k=0
Quantum step 2. Using quantum gates, construct the operation
that takes state |k,0⟩ to state (cid:12) (cid:12)k,xk mod n(cid:11) , and apply this to the
state from step 1. The resulting state is
q−1
1 (cid:88)(cid:12) (cid:69)
√ (cid:12)k,xk mod n
q (cid:12)
k=0
8/12
A High-Speed Overview of Shor’s Algorithm
Quantum step 3. Apply the QFT operator to the first register.
Result:
q−1q−1
1 (cid:88)(cid:88) (cid:12) (cid:69)
e2πikℓ/q(cid:12)ℓ,xk mod n
q (cid:12)
k=0ℓ=0
Quantum step 4. Observe the machine!
QUICK EXERCISE. Fix a specific ℓ. Fix a specific value of
xa mod n, where 0 ≤ a < r. Which values of k in the above
expression contribute to the state |ℓ,xa mod n⟩?
Answer. The index k has to satisfy k ≡ a mod r. If we let
c = a mod r, then we need to sum over all those k of the form
br +c. The terms contributing to this state are
⌊(q−c−1)/r⌋
1 (cid:88)
e2πi(br+c)ℓ/q|ℓ,xa mod n⟩.
q
b=0
9/12
A High-Speed Overview of Shor’s Algorithm
The probability of measuring state |ℓ,xa mod n⟩ is then
(cid:12) (cid:12)2
(cid:12) ⌊(q−c−1)/r⌋ (cid:12)
(cid:12) (cid:12)1 (cid:88) e2πi(br+c)ℓ/q(cid:12)
(cid:12)
(cid:12)q (cid:12)
(cid:12) b=0 (cid:12)
The common factor of e2πicℓ/q that can be ignored because it
factors out of the summation and has magnitude 1. Moreover, any
term of the form e2πim where m is an integer is 1 and can be
ignored. The probability reduces to
(cid:12) (cid:12)2
(cid:12) ⌊(q−c−1)/r⌋ (cid:12)
(cid:12) (cid:12)1 (cid:88) e2πib(rℓ)/q(cid:12)
(cid:12)
(cid:12)q (cid:12)
(cid:12) b=0 (cid:12)
where the only relevant contribution from the product (rℓ) is
rℓ mod q.
10/12
A High-Speed Overview of Shor’s Algorithm
(cid:12) (cid:12)2
(cid:12) ⌊(q−c−1)/r⌋ (cid:12)
(cid:12) (cid:12)1 (cid:88) e2πib(rℓ)/q(cid:12)
(cid:12)
(cid:12)q (cid:12)
(cid:12) b=0 (cid:12)
When is this probability big? We are adding up a collection of eiθ
terms. The magnitude is maximized when all of the θ’s are in
approximately the same direction: that is, when rℓ mod q is small.
Thus the most likely value of ℓ that we measure is one for which
there is an integer d such that
|rℓ−dq| < ϵ.
Dividing out by r and ℓ (and treating the right-hand side as
generically “small”), we get
(cid:12) (cid:12)
(cid:12)ℓ d(cid:12)
(cid:12) − (cid:12) < ϵ.
(cid:12)q r (cid:12)
11/12
A High-Speed Overview of Shor’s Algorithm
We know q, and we measured ℓ. Take the fraction ℓ, and round it
q
down to the nearest fraction whose denominator is < n. That
denominator should be a good guess at the number r.
See Shor’s paper for more technical details on how good a guess it
is, and why we needed q > n2.
Summary
1. We built a |k,0⟩ → (cid:12) (cid:12)k,xk mod n(cid:11) operator. We want to find
the particular input r such that xr mod n = 1.
2. We applied the operator to a superposition of all possible
inputs simultaneously.
3. We used a quantum Fourier transform to fix the odds so that
the most likely answer to be measured is one that allows us to
solve for r!
12/12
