Transcript Quantum random walks – new method for designing quantum

Quantum random walks – new
method for designing
quantum algorithms
Andris Ambainis
University of Latvia
Quantum computing


New model of computing, based on
quantum mechanics.
More powerful than conventional
(classical) computing.
Talk outline
1.
2.
3.
Main results of quantum computing.
The model.
Quantum algorithms based on
quantum walks.
Shor’s algorithm




Factoring: given N=pq, find p and q.
1/3)
O(n
Best algorithm - 2
, n – number of
digits.
Quantum algorithm - O(n3) [Shor, 94].
Cryptosystems based on hardness of
factoring/discrete log become insecure.
Grover's search
0 1 0 ... 0
x1 x2 x3
xN





Find i such that xi=1.
Queries: ask i, get xi.
Classically, N queries required.
Quantum: O(N) queries [Grover, 96].
Speeds up any search problem.
NP-complete problems


Does this graph
have a Hamiltonian
cycle?
Hamiltonian cycles
are:
 Easy to verify;
 Hard to find (too
many possibilities).
Quantum algorithm
0 1 0 ... 0
x1 x2 x3
xN



Let N – number of possible Hamiltonian
cycles.
Black box = algorithm that verifies if
the ith candidate – Hamiltonian cycle.
Quantum algorithm with O(N) steps.
Applicable to any search problem
Pell’s equation



Given d, find the smallest solution (x, y)
to x2-dy2=1.
Probably harder than factoring and
discrete logarithm.
Best classical algorithms:


O( N1/ 3 )
2
2O(N)
for factoring;
for discrete logarithm.
Hallgren, 2001: Quantum algorithm for Pell’s equation.
Number theory and algebraic
problems

Polynomial time quantum algorithms:





Factoring [Shor, 94]
Discrete logarithm [Shor, 94];
Pell’s equation [Hallgren, 02].
Principal ideal problem [Hallgren, 02].
Computing the unit group [Hallgren, 05].
Grover's search
0 1 0 ... 0
x1 x2 x3
xN





Find i such that xi=1.
Queries: ask i, get xi.
Classically, N queries required.
Quantum: O(N) queries [Grover, 96].
Speeds up any search problem.
Amplitude amplification
[Brassard et al., 01]





Algorithm A that finds a certain object
with probability .
How many repetitions to achieve
probability 2/3?
Classically, (1/).
Quantum: O(1/).
“Quantum black box”.
One way to design quantum
algorithms
Amplify quantumly:
Search procedure
Classical algorithm + amplitude amplification
Quantum counting
0 1 0 ... 0
x1 x2 x3
xN




Determine the fraction of xi=1.
E.g., distinguish whether the fraction is
1/2- or 1/2+.
Classical random sampling: O(1/2) steps.
Quantum: O(1/) steps.
Can be used for more complicated statistics.
Element distinctness
7 9 2 ... 1
x1 x2 x3
xN




Numbers x1, x2, ..., xN.
Determine if two of them are equal.
Classically: N queries.
Quantum: O(N2/3).
Triangle finding [Magniez,
Santha, Szegedy, 03]





Graph G with n vertices.
n2 variables xij; xij=1 if
there is an edge (i, j).
Does G contain a
triangle?
Classically: O(n2).
Quantum: O(n1.3).
The model of quantum
computing
Probabilistic computation
1
0.6

0.1
2
3
4
0.1
0.2

Probabilistic system
with finite state space.
Current state:
probabilities pi to be in
state i.
p
i
i
1
Quantum computation
1
0.4+0.3i
-0.7
2
3
4
0.3

0.4-0.1i
Current state:
amplitudes i to be in
state i.

2
i
1
i
For most purposes, real
(but negative) amplitudes
suffice.
Probabilistic computation
1

1/3
2
2/3
4
3
Pick the next state,
depending on the
current one.
Probabilistic computation
1

1/3
2
2/3
4
3
Transitions: rij probabilities to move
from i to j.
p' j   pi rij
i
Probabilistic computation
 Probability vector (p1, …, pM).
 Transitions:
 p'1 


 ...  
 p' 
 M
 r11 ... r1M   p1 

 
 ... ... ...   ... 
r
p 
...
r
MM   M 
 M1
transition probabilities
after the transition
before the transition
Allowed transitions
 p'1   r11 ... r1M  p1 

 


 ...    ... ... ...  ... 
 p'   r



 M   M 1 ... rMM  pM 

R –stochastic:

If i pi = 1, then i p’i = 1.
Quantum computation
 Amplitude vector (1, …, M),   i  1.
i
 Transitions:
2
  '1   u11 ... u1M   1 


 ...    ... ... ...   ... 
 '   uM 1 ... uMM   M 
 M
transition matrix
after the transition
before the transition
Allowed transitions
  '1   u11 ... u1M   1 


 ...    ... ... ...   ... 
 '   uM 1 ... uMM   M 
 M

U – unitary:
2
 If
  i  1 , then
i
 '
i
i
2
1 .
Geometric interpretation
2
 1
 (1, …, M),  i

i
1
0

- vectors on the unit
sphere.
Transformations
that
2
preserve   i  1
i
- rotations of the unit
sphere.
Summary so far


Quantum  probabilistic with complex
probabilities.
2
Instead of i pi = 1 we have   i  1
i
(l2 norm instead of l1).
How do we go from quantum world
to conventional world?
Measurement
Quantum state:
1 1 + 2 2 + … + M M
Measurement
1
2
|
|
prob. 1
2
|2|2
…
M
|M|2
Quantum walks and quantum
algorithms
1.
2.
3.
Quantum random walks.
Grover’s quantum search algorithm.
Quantum walks + quantum
algorithms.
Random walk on line
...
-2
-1
0
1
2


...
Start at location 0.
At each step, move
left with probability
½, right with
probability ½.
Random walk on line
...


-2
-1
0
1
2
...
State (x, d), x –location, d-direction.
At each step,



Let d=left with prob. ½, d=right w. prob. ½.
(x, left) => (x-1, left);
(x, right) => (x+1, right).
Quantum walk on line
...

-2
-1
0
1
2
...
States |x, d, x –location, d-direction.

 | x, left 
“Coin flip”: 
| x, right 

Shift:
1
| x, left  
2
1
| x, left  
2
1
| x, right 
2
1
| x, right 
2
 x, left  x  1, left

 x, right  x  1, right
Quantum walk on line
Left:
...
-2
-1
0
1
2
...
...
-2
-1
0
1
2
...
Right:
Quantum walk on line
Left:
...
-2
-1
0
1
2
...
...
-2
-1
0
1
2
...
Right:
Quantum walk on line
Left:
...
-2
-1
0
1
2
...
...
-2
-1
0
1
2
...
Right:
Quantum walk on line
Left:
...
-2
-1
0
...
-2
-1
0
1
2
...
2
...
Right:
Quantum walk on line
Left:
...
-2
-1
0
1
...
-2
-1
0
1
2
...
Right:
...
Quantum walk on line
Left:
...
-2
-1
0
1
...
-2
-1
0
1
2
...
Right:
...
Quantum walk on line
Left:
...
-2
-1
0
1
...
-2
-1
0
1
2
...
Right:
...
Quantum walk on line
Left:
1/2
1/8
... -3 -2
-1
0
1/8
1
2 3 ...
1/8
Right:
... -3 -2
-1
1/8
0
1
2
...
Classical vs. quantum
Run for t steps, measure the final location.
3.50E -01
0.2
0.18
3.00E -01
0.16
2.50E -01
0.14
0.12
2.00E -01
0.1
1.50E -01
0.08
1.00E -01
0.06
0.04
5.00E -02
0.02
0.00E +00
1
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
17
Distance: (N)
Distance: (N)
21
Grover’s quantum search
algorithm
Grover's search
0 1 0 ... 0
x1 x2 x3
xN


Find i such that xi=1.
Queries: ask i, get xi.
Queries in the quantum world


States |1, |2, …, |N.
Query:


|i  |i, if xi=0;
|i  -|i, if xi=1;
(a state with amplitude 1 at location i gets mapped
to a state with amplitude –1 at i)
Queries in the quantum world
…
12 3 … N
xi=1
…
12
…
Grover’s algorithm


N times repeat:
4
 Query;
 Diffusion transformation:
2

 1 
N

 2
 N
 ...
 2

 N
2
N
2
1 
N
...
2
N
...
...
...
...






2
1 
N
2
N
2
N
...
Analysis of Grover’s algorithm

1
N
For simplicity, assume exactly one i:xi=1.
1st query
…

1
N
1
N
…
Diffusion transformation
3
N
D
1
N

1
N
1
N
…

…
1
N
Inversion against average
2nd query

3
N
3
N
1
N
1
N
1
N
…

1
N

3
N
…
2nd diffusion
5
N
3
N
3
N
1
N
1
N
…

1
N

1
N

3
N

3
N
…
Grover: summary



Query+diffusion increases the
amplitude of i:xi=1, decreases the
amplitude of i:xi=0.

After  4 N repetitions the amplitude
of i: xi=1 is almost 1.
Measuring at this point gives the
solution i.
Why N?
Probabilities vs. amplitudes
Probabilities:
 1/N probability to
query the right i in 1
step.
 N steps to obtain
the probability 1.
Amplitudes:
 The amplitude of the
right i is 1/N.
 Each query+diffusion
increases it by 2/N.
 After N steps it
becomes 1.
Measurement: amplitude 1  probability 12=1.
Search on grids



Grid with N elements.
Task: find the location
storing a certain value.
In one step, we can
check the current
location or move
distance 1.
[Benioff, 2000]



n* n grid.
Distance between
opposite corners = 2n.
Grover’s algorithm takes
n n n
steps.
 No quantum speedup.
Quantum walks solve this problem!
Quantum walk search
[Szegedy, 04]
1

3
2


4
5
6

Finite search space.
Some elements might
be marked.
Find a marked element!
Perform a random walk,
stop after finding a
marked element.
Conditions on Markov chain
1

3
2
4
5
6


Random walk must be
symmetric: pxy=pyx.
Start state = uniformly
random state.
T = expected time to
reach marked state, if
there is one.
Main result [Szegedy, 04]
Theorem Assume that:
1.
There are no marked states, or
2.
A marked state is reached in expected
time at most T.
A quantum algorithm can distinguish the
two cases in time O(T).
Quadratic speedup for a variety of problems.
Application 1
N states.
 Is there a marked state?
 Random walk: at each
step move to a randomly
chosen vertex.
 Finds a marked vertex in
N expected steps.
Quantum: O(N) steps [Grover]

Application 2: search on grids


Random walk: at each
step move to a random
neighbour.
Finding marked state:
O(N log N) steps.
Quantum algorithm:
[A, Kempe, Rivosh, 2005]
Application 3: element
distinctness
7 9 2 ... 1
x1 x2 x3
xN




Numbers x1, x2, ..., xN.
Determine if two of them are equal.
Well studied problem in classical CS.
Classically: N steps.
Johnson graph
{1, 2, 3}
{1, 2, 4}
{1, 3, 5}
{2, 3, 4}
{3, 4, 5}


Vertices: sets S, |S|=k,
S{1, 2, …, N}.
Edges: (S, T), for S, T
that differ only in 1
element.
Random walk
{1, 2, 3}
{1, 2, 4}

{1, 3, 5}

{2, 3, 4}
{3, 4, 5}


Marked vertices = those
for which S contains i, j:
xi = xj.
Random walk in which
we maintain xi, iS.
K queries to start;
1 query to move to
adjacent vertex.
Search by random walk

{1, 2, 3}
{1, 2, 4}
{1, 3, 5}
Time to find a marked
vertex:


{2, 3, 4}
K queries to start;
 N 2  moving steps.


O

K


{3, 4, 5}
 N 
Quantum: O 
 k
Quantum algorithm
{1, 2, 3}

Quantum time:
K queries to start;

 N  moving steps.
O

 k

{1, 2, 4}
{1, 3, 5}

{2, 3, 4}
{3, 4, 5}
K=N2/3
Total:
N 

O k 

k

O(N2/3)
Triangle finding [Magniez,
Santha, Szegedy, 03]





Graph G with n vertices.
n2 variables xij; xij=1 if
there is an edge (i, j).
Does G contain a
triangle?
Classically: O(n2).
Quantum: O(n1.3).
Matrix multiplication
[Buhrman, Špalek, 05]

A, B, C – n*n matrices.
Finding C=AB: O(n2.37…) steps;

Given A, B and C, we can test AB=C in:



O(n2) steps by a probabilistic algorithm;
O(n5/3) steps by a quantum algorithm.
Inside the Szegedy’s black box
How do we turn random walks
into quantum algorithms?
Quantum walk
1


3
2
4
5
6

State space with states |i.
Starting state
1 M
i

M i 1
Quantum walk with two
transition rules:


“usual” for unmarked vertices;
“special” for marked.
Quantum walk algorithm

No marked vertices:

The starting state is
unchanged.

Some marked vertices:


The starting state is
changed at the marked
vertices.
Changes spread and
accumulate.
Run for sufficiently many steps, test if
the system is still in the starting state.
As in Grover’s search…
5
N
3
N
3
N
1
N
1
N
…

1
N

1
N

3
N

3
N
…
Mathematics
 p1 
  - vector of probabilities
 ... 
p 
1 step: P’ = MP
 M
k steps: P’ = MkP
Eigenvectors and eigenvalues of M,
M – transition matrix.
Mathematics II
Eigenvectors of M: v1, …, vN.
M vi= i vi
Mt vi= (i)t vi
Express starting distribution via eigenvectors:
P   i vi
i
M P    i i  vi
t
t
i
Mathematics III

Random walk


Probability matrix M;
Expected time T to
hit a marked vertex.

Quantum walk


Unitary matrix U;
Time T’ at which the
state becomes
sufficiently different from
the starting state.
 
T' O T
Other applications of quantum
walks
“Glued trees” [Childs et al.,
02]


Two full binary trees
of depth d;
Randomly connect
leaves of the two
graphs.
“Glued trees” [Childs et al.,
02]




Start position: the left
root.
Task: find the other
root.
Vertices and edges
not labeled.
2d+2-2 vertices.
Any classical algorithm takes (cd) steps.
“Glued trees” [Childs et al.,
02]


Perform a quantum
walk, starting from
the left root.
After O(d2) steps, a
quantum walk is at
the right root.
Exponential speedup: O(d2) vs (cd).
[A, Childs, et al., 07]


AND

OR
x1
OR
x2
x3
x4
AND-OR formula of size M.
Variables accessed by
queries: ask i, get xi.
Theorem Any formula can
be evaluated with
O(M1/2+o(1)) queries.
Speedup for anything that can
be expressed as a formula
Conclusion



Quantum walks can be used to design
quantum algorithms for many problems.
Quantum walk search: create a classical
random walk, quantize it with a
speedup.
“Quantum black box” within a classical
algorithm.
Building a quantum computer



Classical computer operates on bits (0
or 1).
Quantum bit: a system with basis states
|0, |1, general state 0|0+ 1|1.
Need physical systems that act like
quantum bits…
10s of candidates…
NMR quantum computing (IBM, Waterloo,
etc.)



Quantum computer =
molecule.
Quantum bits =
nuclear spins.
Operations performed
using magnetic fields.
Spin – property that determines how
the particle behave in a magnetic field
0, 1
NMR quantum computing

12 quantum bits (IQC):


Creating a certain
quantum state.
7 quantum bits (IBM):


Factoring 15;
Grover’s search among
4 items.
Quantum cryptography


QKD device of
Id Quantique
(Geneva)


Secure data
transmission, using
quantum mechanics.
Only requires single
quantum bits.
Implemented over
200km distance.
Available commercially.