Seminario - Quantum Longest Common Substring with quadratic speed-up

Alle ore 10:50, nell'aula Anile 124, la prof.ssa Arianna Pavone, Università di Palermo terrà un seminario dal titolo "Quantum Longest Common Substring with quadratic speed-up"

 

The Longest Common Substring (LCS) is a classical problem in computer science, representing fundamental challenges in string processing. Such problem can be solved in linear time using a classical model of computation, relying on the use of suffix trees. Very recently, two sublinear algorithms for LCS and LPS in the quantum query model have been presented by Le Gall and Seddighin. However, while the query model is fascinating from a theoretical standpoint, its practical applicability becomes limited when it comes to crafting algorithms meant for actual execution on real hardware. In this talk we present, for the first time, a quantum algorithm for both LCS and LPS working in the circuit model of computation with qadratic speed-up with respect to the calssical solution. We also present actual implementations of the two algorithms as quantum circuits.