Seminário de Computação e Informação Quântica 

14/10/2005, 15:00 — 16:00 — Sala P4.35, Pavilhão de Matemática
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.