 ERATO QCI Project HOME |
 EQIS'03 TOP |
Quantum walks are quantum counterparts of classical Markov chains. Quantum walks can behave very differently from classical Markov chains and are useful for designing new quantum algorithms. In the first part of the talk, we will survey the definitions and main results about quantum walks.
In the second part of this talk, we will show how to use a quantum walk to design a new quantum algorithm for element distinctness, a classical computer science problem. In element distinctness problem, we are given n numbers and have to find out if they are all distinct. The new quantum algorithm solves element distinctness in O(n^{2/3}) time. This improves over previous quantum algorithm by Buhrman et al. and matches the lower bound of Shi.
|
ERATO QCI Project HOME |
EQIS'03 TOP |