Transcript ppt - Département de physique

Four approaches to Shor
David Poulin
LITQ
Université de Montréal
Supervisor Gilles Brassard
(SAWUNEH may 2001)
Summary
•Shor’s entire algorithm formally
•Probability analysis
•Phase estimation
•Shor as phase estimation
•Quantum circuit for QFT
•Semi-classical circuit for QFT
•Single qubit phase estimation
•Mixed state quantum computing
A bit of number theory...
Theorem
If a  b (mod N) but a2  b2 (mod N)
Then gcd(a+b,N) is a factor of N.
Proof
a2 - b2 0 (mod N)
 (a - b)(a+b) 0 (mod N)
 ( t) [ (a - b) (a+b) = tN ]
uN
vN
 gcd(a+b, N) is a non trivial factor of N.
Shor’s entire algorithm
N is to be factored:
Easy 1.
Easy 2.
Hard 3.
Easy 4.
Easy 5.
Easy 6.
Easy 7.
Choose random x: 2  x  N-1.
If gcd(x,N)  1, Bingo!
Find smallest integer r : xr  1 (mod N)
If r is odd, GOTO 1
If r is even, a = xr/2 (mod N)
If a = N-1 GOTO 1
ELSE gcd(a+1,N) is a non trivial factor of N.
Success probability
Theorem
If N has k different prime factors, probability of
success for random x is  1- 1/2k-1.
Add this step to Shor’s algorithm:
Easy 0. -Test if N=N’2l and apply Shor to N’
-Compute j N for 2  j  ln2N. If one of these root is
integer, apply Shor to this root.
 Probability of success  ½.
Order finding
Quantum Fourier transform
1
e
F x  1 
c0
2ixc/
c
1
2ixc/
1
-1
x

e
c

F
 c0
Modular exponentiation
a

 mod N
a
,
b

a
,
b

x
EN,x
HA dim=
HB dim=
 = 2n
n = 2lnN
Order finding
A
|0
Hn
|0
B
EN,
x
C
F-1
m
m
For sake of
analysis!
r : xr  1 (mod N)
D
Bit
bucket
Step by step
|0|0
Hn
EN,x
1
1  a, 0
 a0
1
1 
a, xa mod N
 a0
A
B
The second register is r-periodic since xnr+b modN = xb modN
Step by step
m on the second register and obtain y a power of x.
What is left in the first register is an equal superposition
of everything consistent with y.
y  xs  xs+r  xs+jr modN
m

r
1
1  s jr
/r j0
C
Step by step
Quantum Fourier transform
F-1

r
1
1
1  1  e2i(s jr)c/ c
/r j0  c0
1
 c c
c0
c  r e

2isc/

r
1
e

j0
2ijrc/
D
What’s that probability?
Measure the first register:
m
“c” with probability
|c|2
= r2


r
1
2ijrc/
e

j0
What we want is r : xr  1 (mod N) !
Consider a c :  t integer with 0  rc-t  r/2
t   rc  t  +r/2
t j  jrc /   tj +rj/2   tj +1/2
0  jrc /   1/2 plus a integer!
2
What’s that probability?
Length of the arc: 
r
Length of the cord:
 2 arc  2

r
2
r
4

 |c|2  2 2 2  4r
 r
What’s that probability?
If 0  rc-t  r/2 then |c|2  4
r
#{c : 0  c  -1 and (t)[0  rc-t  r/2 ]}  r
 Pr( getting a good c )  4  40%

What the heck is so special about those c ?
Continuous fractions
The condition can be written c  t  1  1 n

r
2
22
c/ is the best n bits estimation of t/r.
Assume there is another t’/r’ satisfying this condition:
t  t'  1  tr' - t'r  1
r r' 
rr'

2
r
and
r
'

N

rr
'

N

Since
Hence tr’ – t’r =0  t and r are unique.
They can be found by continuous fraction algorithm!!!
That was Shor’s algorithm formally.
Now I’ll show what Shor’s algorithm really is.
Do you need a break?
Interference
|0  |0
|1  ei |1
|0
H

H
m
|0  |0+|1  |0+ei |1  (1+ ei )|0+ (1- ei )|1
Pr(“0”)=cos2(/2)
Pr(“1”)=sin2(/2)
Phase kick back
The previous dynamics can be simulated by:
|0
Same state as
previous slide!
H
|u
Apply U if top
wire is 1
U
|u
Bit
bucket
Where |u is an eigenstate of U: U|u = ei |u
|0|u  (|0+ |1)|u = |0|u+|1|u  |0|u +ei |1|u
 (|0+ei |1)|u
Phase estimation
In Deutsch’s problem, we were able to determine whether
 was 0 or .
Q: Can me determine any  ?
A: We can get the best n bit estimation of /2.
4
i2
|0+e |1
|0

Hn
|0+ei |1
|u
U
U2
2
2
U
3
2
U
4
2
U
|u
|
F
Phase estimation
1
2ixc/
1
x 
e
c

 c0
  0 e
2i(0.xn)
  p j
n
j1
1  0 e
2i(0.xn1xn)
1  ...  0 e
2i(0.x1...xn)
where p   0 e
i2
 j  0.xn j xn j1 ... xn
1
1
(binary extension of x/ - integer)
So applying F-1 to | will yield |x that is the best n bit
estimation of /2.
k

2


x   2 
mod 1
k 0
 2

n
k
Multiplication
Consider UN,a : |x  |ax mod N. Then,
r1
k   e2ikj/r a j mod N
j0
for k = 1,...,r
are eigenstates of UN,a with eigenvalues e2ik /r
r1
UN,a k   e
j1
j0
2ik /r
e
r
a mod N   e
2ikj/r
j1
r1
e

j0
2ikj/r
2ik(j1)/r
j
a mod N
j
a mod N
If we could prepare such a state, we could obtain an
estimation of k/r hence of r. It requires the knoledge of r.
Multiplication
Consider the sum
r
r
r-1
2ikj/r
j

k

e
a
mod N  1


k 1
k 1 j0
r
Since  e2ikj/r   j0
k 1
The state |1 is easy to prepare. In what follows, we
show that it can be used to get an estimation of k/r
for random k.
Phase estimation
|0
Hn
|1
m

F-1
UN,a
U2
N,a
2
2
UN,a
3
2
UN,a
4
2
UN,a
m
m

Make measurement here to collapse the state to a
random |k : get an estimation of k/r for random k.
This measurement commutes with the Us so we can
perform it after.
This measurement is useless!
F-1
1
QFT
x  1 e2ixc/ c
 j  0.xn j xn j1 ... xn
 c0
  p j
where p   0 e
n
i2
j1
circuit
1
Qubit n is |0+ |1 if x0 is |0 and |0- |1 if x0 is |1.
(x0 with a phase 0 or -)
|x0
pn
H
Qubit n-1 depends on x0 with a phase 0 or -/2 and on
x1 with a phase 0 or -
|x1
|x0
H
pn1
R1
H
pn
QFT circuit
We define the gate Rk as a -/2k phase gate.
|x3
H
R1
|x2
R2
H
R1
|x1
Note 2:
p1
R2
H
p2
R1
|x0
Note 1: H = R0
p0
R3
H
Rk

Rk
p3
Semi-classical QFT
Measurements!
|x3
|x2
|x1
|x0
p0
H
p1
R1 H
R 2 R1
p2
H
R 3 R2 R 1 H
p3
All controlled phase gates are now classically controlled!
Single qubit phase estimation
…
H …
|0+ |1

|0+ |1

…
|0+ |1
…
|0+ |1
…
|1
U
2n-1
…
…
… U22 U21 U20
Bit
bucket
H
R1
H
R2
R1
H
Single qubit phase estimation
|0+ |1
H …
|0+ |1
|1
U
2 n-1
|0+ |1
|0+ |1
Rn-2
Rn-1
H
…
…
… U22
1
2
U
Rn
H
H
0
2
U
Almost anything will do the job!!!
The
are measurements.
The Rk are phase gates with an angle 0.b1b2...bk-1
where bj is the classical outcome of the jth measurement.
Mixed state computing
1
I
1
Maximally mixed state:
  k k
  k0
Independent of the basis |k.
The |k k=1,2,...,r are orthogonal, but do not form a
complete basis since r < .
The other eigenvectors of UN,a are of the form:
j
d
d
rd 1
e
k 0
2ijd k /rd
k
gda mod N
Where gd are solutions of gar-g  0 mod N and rd is the
period of the period x  gdax mod N.
Mixed state computing
Theorem: Given q and p : N = pq, then gar-g  0 mod N
for at most p+q-1 values of g.
We express the maximally mixed state as a mixture of
the eigenvalues of UN,a.
r 1
d
d
I 1 
j j
  d j 0
d
d
d
d
The output of the algorithm will then be the best n bit
estimation of jd/rd for d and jd chosen at random.
(p1)(q1)  1.
The result is useful if gd=1: Prob =
pq
Mixed state computing
Since I is independent of the basis, we can input anything
in the bottom register and it will work pretty well.
In particular, this is useful for NMR computing.
(it’s impossible to prepare a pure state)