#
Quantum walks and a new quantum algorithm for element distinctness

Andris Ambainis (Univ. Latvia)

## Abstract

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 |