Quantum Computation and Information Seminar 

14/10/2005, 15:00 — 16:00 — Room P4.35, Mathematics Building
Hélio Pais, Instituto Superior Técnico

Quantum string matching

A brief overview on classical algorithms for the match-count problem is given. A quantum algorithm for finding the maximum match-count between two strings is presented. The expected run time of the proposed algorithm for strings of size n is shown to be $O(n)$, which is a lower bound for the problem at hand. Joint ongoing work with P. Mateus.