报告题目: |
Quantum walk based search algorithms |
报告人: |
Miklos Santha |
|
Universite Paris Sud, Laboratoire de Recherche en Informatique
France
|
报告时间: |
2008-04-23 16:30 |
报告地点: |
Room 4-603, FIT Building, Tsinghua University |
主办单位: |
ITCS, Tsinghua University |
简介: |
In this survey talk we give an intuitive treatment of the discrete time quantization of classical Markov chains. Grover search and the quantum walk based search algorithms of Ambainis, Szegedy and Magniez/Nayak/Roland/Santha will be stated as quantum analogues of classical search procedures. We present a rather detailed description of the MNRS algorithm. Finally, in the query complexity model, we show how quantum walks can be applied to the following search problems: Element Distinctness, Matrix Product Verification, Restricted Range Associativity, Triangle, and Group Commutativity.
Miklos Santha is a research director of Information Research Lab in Paris-Sud University. His fields of interest are theoretical computer science, quantum and approximation algorithms.
|
|
