Scribbled note at the 2nd half the lecture
(neither previewed nor approved by the speaker)

CCNY Colloqium, Physics Department MR418
March 08, 2006 4:00 PM

Title: Quantum Walks
Prof Mark Hillery, Hunter College, CUNY 

Compare the classical random walk (diffusion property)
and quantum random walk property which HAS interference effect (see
survey [1]). Introduce the basic technique simulation
on the physics of wave function, say complex plane, of
quantum random walk -- walk the line or walk the graph 
(analoguous to computer science terminology). The physical 
analogy is to 'build a beam splitter' which can be simulated 
by computer program. 

Various models of quantum random walks are proposed on the application 
of unitary operators and how they effect the 'quantum random walk'. 
Two algorithms are selected for discussion and experiments are shown: 

1. Deutsch-Jozsa algorithm to evaluate boolean
function f(x) =0 or 1 where 0<=x <2^n -1. So x -->
Black Box --> f(x). Two types of functions are analyzed:
a) constant function
b) balanced function if { f(x) = 0,  1/2 times ;
                          f(x) = 1, 1/2 times }
Question: how does one determine the Box ?

2. Grover's search algorithm
f(x) = 0 when x in x_0 ; 1 when x =x_0. Grover algorithm performs an 
unstructured search on x_0 where f(x) =1. 

Based on a priori probability and overlaps of states, an example on how 
unitary evolution transforms boolean sets is shown in [3]. Three 
different kinds of measurement can be simulated: Von Neumann Projective
measurement, and positive-operator valued measure. 

Q & A session:
Quantum walks on graphs and quantum scattering theory has promises for 
2-SAT problems, convex body problems, combinatorial problems etc. Bound of Grover 
algorithm is in fact optimal. Hypercube model may not have a better bound.
Some open issues, for efficient probabilistic approximation algorithm,
are 'initial condition', 'localization', discrete time walk, continuous time walk.

Cited references on arxiv.org
1. Julia Kempe, Quantum random walks, an introduction overview. 2003
2. Edgar Feldman and Mark Hillery, Quantum walks on graphs and 
quantum scattering theory. 2004
3. Janos Bergou and Mark Hillery, 2005