Transcript Slide 1

Grover’s Search Algorithm
Goal: Make the needle big enough
There are N objects: x1, x2, . . . , xN
We have a function f(x) and an index k such that
f(xi) = 0 when xi ≠ xk
f(xk) = 1
Goal: Find k
Classical method: Evaluate f(x1), f(x2), . . .
until you get f(x) = 1.
Expected time: N/2
Form a complex vector space with basis x1, x2, . . . , xN
Two operators:
U: xj
(-1)f(xj) xj
and
D= 2P – I , where
P = (1/N)
111...1
111...1
111...1
111...1
D is “inversion about average”
Start with (1,4,3,7,0)
Average is (3,3,3,3,3)
D (1,4,3,7,0) = (5,2,3,-1,6)
Successively apply U, D, U, D, U, D , . . .
Example: (1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
Suppose k=10 is the index we’re looking for.
U(1, 1, 1, 1, 1, 1, 1, 1, 1, 1) = (1, 1, 1, 1, 1, 1, 1, 1, 1, -1)
Apply D. Note: average entry is 0.8
(.6, .6, .6, .6, .6, .6, .6, .6, .6, 2.6)
Apply U: (.6, .6, .6, .6, .6, .6, .6, .6, .6, -2.6)
Apply D. Note: average entry is 0.28
(-.04, -.04, -.04, -.04, -.04, -.04, -.04, -.04, -.04, 3.16)
(0,0, . . . ,1)
DUv
v
q
(1,1, . . . , 1) = start
(1,1, . . . ,1,0)/(N-1)1/2
sin ( q/2) = 1/N1/2
q/2 ≈ 1/N1/2
After (p N1/2)/4 steps, we obtain a vector almost parallel to (0,0, . . . , 1).
D, U are unitary, so lengths don’t change. Therefore, the vector
has a large coefficient on the sought-after vector and all other coefficients are small.
Quantum Version:
The indices 1, 2, . . . , N represent the possible states of a system.
Start with a linear combination of these states with all coefficients equal.
Apply DU approximately (p N1/2)/4 times.
The result is a linear combination of states where the sought-after state
has a large coefficient and the other states have small coefficients.
Observe this vector.
Basic principle: The probability of an observation yielding a state
is proportional to the square of the absolute value of the coefficient of that state.
With high probability, we find the desired index k.
We have searched through N objects in around N1/2 steps
Successively apply U, D, U, D, U, D , . . .
Example: (1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
Suppose k=10 is the index we’re looking for.
U(1, 1, 1, 1, 1, 1, 1, 1, 1, 1) = (1, 1, 1, 1, 1, 1, 1, 1, 1, -1)
Apply D. Note: average entry is 0.8
(.6, .6, .6, .6, .6, .6, .6, .6, .6, 2.6)
Apply U: (.6, .6, .6, .6, .6, .6, .6, .6, .6, -2.6)
Apply D. Note: average entry is 0.28
(-.04, -.04, -.04, -.04, -.04, -.04, -.04, -.04, -.04, 3.16)
Factoring
Let’s factor 91
Choose a random number, say 5.
Compute the powers of 5 mod 91:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, . . . , 24, 25, 26
1, 5, 25, 34, 79, 31, 64, 47, 53, 83, 51, 73, 1, 5, 25, . . . , 1, 5, 25
The sequence is periodic. In this case, it has period 12.
Suppose we determine that the period is 12.
Then we know that 512 = 1 mod 91
We can use this information to factor 91.
Write 12 = 22 3
Compute
53 = 34 mod 91
56 = 342 = 64 mod 91
512 = 642 = 1 mod 91
Basic Fact: If x2 = 1 mod n and x ≠ 1 mod n,
then gcd(x-1, n) is a non-trivial factor of n.
Compute gcd(64 – 1, 91) = 7, which is a factor of 91.
In general, whenever we have a relation ar = 1 mod n, there is
a good chance we can use the above procedure to factor n.
How do we find r ???
Choose a power of 2 between 912 and 2x912:
912 < 214 = 16384 < 2x912
Compute a sequence of pairs
(0,1), (1,5), (2, 25), (3, 34), . . . , (12,1), (13,5), . . . , (16383,34)
In the quantum world, these are represented by
a linear combination of 16384 equally likely states.
Observe the second coordinate of these pairs and obtain a
random answer, say, 25.
This means we have the pairs
(2,25), (14, 25), (26, 25), . . . , (16382,25)
and all are equally likely.
Ignore the second coordinate, so we have a sequence
2, 14, 26, 38, . . . , 16382.
Quantum Fourier Transform
Let a0, a1, a2, . . . , a16383
independent vectors .
be a sequence of linear
For a number x, define F(x) = (1/128)
∑0≤c<16834 e2picx/16834 ac
This is an element of a 16384-dimensional complex vector space.
Extend F by linearity to evaluate F on a linear combination of states:
On our sequence 2, 14, 26, . . . , 16382, we get
F(2) + F(14) + F(26) + . . . + F(16382)
The coefficient of ac is (1/128) ∑0≤x<16834, x=2 (mod 12) e2picx/16834
Suppose instead that the sequence is 2, 10, 18, 26, . . . , 16378,
which is periodic with period 8 (= a divisor of 16384).
Then the coefficient of ac is
(1/128)
∑
2picx/16834
e
0≤x<16834, x=2 (mod 8)
This is 0 when c ≠ 0, 2048, 4096, 6144, 8192, 10240, 12288, 14336
(the multiples of 16384/period)
When the period P is not a divisor of 16384, we expect a “noisy” version
of this situation: The coefficient of ac is approximately 0
when c is not a multiple of 16384/P
For the sequence 2, 14, 26, 38, . . . , 16382, here is a graph of the squares of
the absolute values of the coefficients of ac
Here is a close-up near for the coefficients of ac for c near 6827
Suppose instead that the sequence is 2, 10, 18, 26, . . . , 16378,
which is periodic with period 8. The squares of the absolute values
of the coefficients of ac are
The non-zero coefficients are at
0, 2048, 4096, 6144, 8192, 10240, 12288, 14336
(the multiples of 16384/period)
For the sequence 2, 14, 26, 38, . . . , 16382, here is a graph of the
squares of the absolute values of the coefficients of ac
The peaks are at multiples of the frequency.
Here is a close-up near for the coefficients of ac for c near 6827
Observe: Suppose we get 6826.
Let P be the period we are looking for
(P=12 in our example)
6826 ≈ (k) (Frequency) = (k)(16384/P ), for some integer k.
_____
6826
16384
≈
__
k
P
We need to approximate a number by a
rational number (namely, k/p)
with small denominator.
Continued Fractions!!
6826
_____
16384
=
__________________
1
2 + _____________
1
2 + _________
1
2 + ______
1
170+1
__
4
Stop before the 170:
__________
1
2 + _______
1
2 + __
1
2
=
___
5
12
Therefore, it is probable that
k = __
5
__
P
12
Therefore, P = 12 (or a small multiple of 12).
Check: 512 = 1 mod 91.
Write 12 = 22 3
Compute
53 = 34 mod 91
56 = 342 = 64 mod 91
512 = 642 = 1 mod 91
Compute gcd(64 – 1, 91) = 7, which is a factor of 91.
Quantum computers can also solve the
Discrete Logarithm Problem:
Let p be a prime, and let g and h be nonzero mod p.
Solve gx = h (mod p).
Consider the map Z x Z ->
(Z/pZ)x
(a,b) -> gah-b
The kernel is the multiples of (x,1) mod p-1.
Lattice-Based Cryptography Seems to be Quantum Resistant
That’s Quantum Computing
Is there Relativistic Computing?