NCTS (South)


DATE2009-04-20

TIME12:00

PLACER203, 2F, NCTS, NCKU

FIELDQuantum Information Science

SPEAKER Prof. Jingbo Wang - School of Physics, University of Western Australia

TITLEQuantum random walk and its application

ABSTRACTQuantum random walk represents a generalised version of the well-known classical random walk. Regardless of their apparent connection, the dynamics of quantum random walk is often non-intuitive and far deviate from its classical counterpart. For example, it has been proven to provide an exponential algorithmic speedup for traversing a randomised glued-tree graph. In this seminar, I will first give a general introduction to quantum random walk and then discuss its possible applications. In particular, I will present a possible quantum algorithm aimed to solve the Graph Isomorphism problem. This is a long-standing open problem in mathematics with applications in many areas of science and engineering. This seminar will be informal and as non-mathematical as possible (suitable for a general audience). No prior knowledge about quantum random walk or graph isomorphism is assumed.