Transcript Quantum parallelism

Short course on quantum
computing
Andris Ambainis
University of Latvia
Lecture 2
Quantum algorithms and factoring
Factoring




Input: composite N.
Output: p, q  {2, …, N-1} s.t. pq=N.
Hard for classical computers.
Factoring large integers would break RSA.
Factoring



Quantum computers can factor integers in
polynomial (quadratic) time [Shor’94].
Similar approach also solves discrete
logarithm by quantum algorithm.
Today: Shor’s algorithm.
Outline
1) Computational model.
2) Quantum parallelism and quantum
interference.
3) Simon’s algorithm.
4) Shor’s algorithm.
Basic ideas



State space consisting of n (quantum) bits.
Elementary gates on 1 or 2 (qu)bits.
Efficiently computable = poly-size circuits.
Classical circuits
X1
X2
X3

X5
^
^

Result
Quantum circuit
H
H
H
H
Gates on quantum bits
Elementary gates (1)


Hadamard gate
1

| 0  2 | 0  
H 
1
 | 1 
|0

2
Phase shift
 | 0  | 0 
Z 
| 1   | 1 
1
2
1
2
|1 
|1 
Elementary gates (2)

Rotation by angle 
| 0  ei | 0 
T 
i
| 1  e | 1 

Controlled NOT
 00

 01
CNOT  
 10
 11

 00
 01
 11
 10
Universality

Any quantum computation can be
performed by a circuit consisting of
Hadamard, phase, rotation by /8 and
controlled NOT gates.
Classical vs. quantum circuits


We have a classical circuit.
Can we construct a quantum circuit that
computes the same function?
Reversibility


Assume f(x)=f(y)=z.
If
U x  | z 

U y  | z 
then

U( x  y )  0

U not unitary.
Reversibility
We can transform a classical circuit
for F to quantum circuit.
|x>
|0>
|x>
F
|F(x)>
Add extra input initialized to 0.
Example
Quantum
Classical
x
y
^
|x>
|x>
|y>
|y>
|0>
|xy>
|a>
|a(xy)>
Toffoli gate.
Quantum parallelism
|x>
|x>
|0>
|f(x)>


By linearity,
x |x> |0>
 |x> |f(x)>
x
Many evaluations of f in unit time.
Quantum parallelism

Once we measure
 |x> |f(x)>
x
we get one particular x and f(x).
 Same as if we evaluated f on a random x.
Quantum parallelism


Is it useful?
We cannot obtain all values f(x) from
 |x> |f(x)>
x

because quantum states cannot be
measured completely.
We can obtain quantities that depend on
many f(x).
Quantum interference

Hadamard transform:

 H | 0 

 H | 1 

1
|0 
2
1
|0 
2
1
|1 
2
1
|1 
2
1
 1

H
|0
| 1   | 0 
2
 2

Quantum interference


Negative interference: |1> and -|1> cancel
out one another.
Positive interference: |0> and |0> add up to
a higher probability.
Parallelism+interference




Use quantum parallelism to compute many
f(x).
Use interference to obtain information that
depends on many values f(x).
Requires algebraic structure.
Ideal for number-theoretic problems
(factoring).
Order finding



The order of aZN * modulo N is the
smallest integer r>0 such that
ar1 (mod N)
For example, order of 4 mod 7 is 3:
41  4, 42 =162, 43 =641 (mod 7).
Factoring reduces to order-finding.
Reduction



If ar1(mod N), then N divides ar-1.
If r even, ar-1=(ar/2-1)(ar/2+1).
If N is product of two or more primes,
gcd(ar/2-1, N)
is a nontrivial factor of N with probability
at least 1/2.
Shor’s algorithm
Repeat O(log n) times:




Generate random a{1, …, N-1};
Check if (a, N)=1;
r = order(a);
If r even, check (ar/2-1, N).
Period finding

Function F:NN
|x>
F
|0>

|x>
|F(x)>
such that F(x)=F(x+r) for all x.
Find smallest r.
Simon’s problem

Function F:{0, 1}n {0, 1}n.
|x>
|0>


F
|x>
|F(x)>
F(x+y)=F(x) for all x, + bitwise addition.
Find y.
Algorithm [Simon, 1994]
|0>
H
H
H
H
H
|0>
F
|y>
H
|f(x)>
Repeat n times and combine results y1,..., yn.
Hadamard transform
1

| 0  2 | 0  
H 
1
 | 1 
|0

2
1
2
1
2
|1 
|1 
Hadamard on n qubits
|0>
H
1
2
|0>
H
1
2
n
|0
1
|0
1
1
1
 1

|0 
|0
|1  
2
 2

2n
n
2
2
|1 
|1 
| x 
x0 ,1n
Simon’s algorithm step-by-step
|0>
H
H
H
H
H
F
|y>
H
|F(x)>
|0>
1
2n
| x  | 0 
x0,1n
1
2
n
 | x  | F ( x) 
x0,1n
Measuring F(x)



Partial measurement.
We get some value y=F(x).
The state 1
| x  | F ( x) 
2

n

x0,1n
collapses to part consistent with y=F(x).
| x  | y 
F ( x ) y
Last step

We now have the state

How do we get z?
Measuring the first register would give
only one of x and x+z.

(| x   | x  z ) | y 
Simon’s algorithm
|0>
H
H
H
H
H
F
|y>
H
|f(x)>
|0>
(| x   | x  z )
Hadamard transform
1

| 0  2 | 0  
H 
1
 | 1 
|0

2
H | x 
1
2
|0
1
2
1
2
1
2
|1 
|1 
(1) x | 1 
Hadamard transform
|x1>
|x2>
...
|xn>
H
1
2
1
H
2
...
H
1
2
|0
1
2
1
|0
2
...
|0
1
2
(1)
x1
x2
|1 
xn
|1 
(1)
(1)
|1 
x y
| x1 x2 ...xn    (1) i i | y1 y 2 ...y n 
y1 y2 ...yn
Hadamard transform
x y
| x    (1) i i | y1 y 2 ...y n 
y1 y2 ...yn
 (x  z ) y
i
i i | y y ...y 
| x  z    (1)
1 2
n
y1 y2 ...yn
Signs are the same iff zi yi= 0 mod 2.
Summary

Measuring the final state gives a vector y
such that
 yi zi  0 (mod2)

n-1 such constraints uniquely determine z,
with high probability.
Summary


Quantum parallelism: computing F for
many values simultaneously.
Quantum interference: Hadamard
transform.
Period finding

Function F:NN
|x>
F
|0>

such that F(x)=F(x+r) for all x.
Find r.
|x>
|F(x)>
Algorithm [Simon, 1994]
|0>
H
H
H
H
H
F
H
|0>
Repeat n times and combine results y1,..., yn.
Algorithm [Shor, 1994]
|0>
QFT
F
QFT
|0>
Find factor by continued fraction expansion.
Shor’s algorithm step-by-step
|0>
QFT
QFT
F
|0>
1
M
| x |0

M
x 1
1
M
| x  | F ( x) 

M
x 1
Shor’s algorithm step by step

Measuring the second register leaves the
first register in a state consisting of all x
with the same F(x):
|d>+|d+r>+…+|d+ir>
Quantum Fourier transform
M 1 2 i j k
1
M
T| j
e
|k 

M i 0
If M=2, this is Hadamard transform.
QFT detects periods

Assume r divides M.

M

 d  d  r  ...  d    1r
|  
M / r 
 r

1
r 1

Then,

If j relatively prime with r,
M
T   a j j 
r
j 0
jM

gcd M,
r

 M
 .
 r




QFT detects periods

Assume r does not divide M.
 M  d  1
  d  d  r  ...  d  
r

r



Then, most of T| consists of |k> with
jM
k
r
QFT detects periods
r does not
divide M
r divides M
M 2M
0
r
r
3M
r
M
0
r
Can we find r?
2 M 3M
r
r
Continued fraction expansion


Number theory algorithm.
Given k, M, finds j, r such that
jM
k
r

is smallest among all j and r  r0.
If M=(r2), correct w.h.p.
Summary of Shor’s factoring





Reduce factoring to period-finding.
Generate a quantum state with period r.
In the easy case, QFT transforms a state
with period r into multiples of M/r.
General case: same but approximately.
Continued fraction algorithm finds the
closest multiple of M/r.
Hidden subgroup

Function F:GS
|x>
F
|0>

|x>
|F(x)>
such that F(g)=F(hg) iff hH.
Find H.
Hidden subgroup





Captures a lot of problems.
Simon’s problem: G={0, 1}n, H={0n, z}.
Shor’s period-finding: G=Z, H=rZ
(multiples of r).
Discrete logarithm: G=Z2.
Pell’s equation [Hallgren, 2002]: G=R.
Discrete log


Given N, g and x, compute r such that
grx (mod N).
Another hard problem relevant to crypto
(Diffie-Hellman).
Discrete log



Define F(y, z)=gyxz mod N.
G=Z2.
H={y,z | y+zr =0 mod N-1} because
gyxz=gy+rz and gN-1=1.
Status of hidden subgroup


Quantum polynomial time for Abelian G.
Open for non-Abelian G (except a few
groups G with simple structure).
Graph Isomorphism
G2
G1
?

Graph Isomorphism
• G: all permutations of vertices.
• F() = (G).
• H - permutations that fix G.
Hidden subgroup



Graph Isomorphism reduces to hidden
subgroup for non-Abelian groups.
Approximating shortest vector in lattice
also reduces to HSP.
Solving HSP by quantum algorithm
remains open for almost all non-Abelian
groups.