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

07/01/2005, 15:00 — 16:00 — Sala P4.35, Pavilhão de Matemática
Paulo Mateus, Instituto Superior Técnico

Quantum pattern matching using entanglement

A quantum algorithm for pattern matching is proposed and its complexity is analysed. The time complexity of the algorithm for matching (with nonvanishing probability) a pattern of size $M$ with a sequence of size $N$ is $O(\log (N)\sqrt{N}M)$. Entanglement is essential to attain time complexity and moreover, to consider patterns with gaps. Joint work with Y. Omar.