Join us on Zoom:
Link: https://zoom.us/j/91734351612?pwd=K2ZKNnE3d2h6TTBUYUZqS2xjYVVwdz09
(Meeting ID: 917 4657 5742 - Passcode: 170827)
Abstract
The divide-and-conquer framework, used extensively in classical algorithm design, recursively breaks a problem into smaller subproblems, along with some auxiliary work, to give a recurrence relation for the classical complexity. We describe a quantum divide-and-conquer framework that, in certain cases, yields quantumspeedup through an analogous recurrence relation for the quantum query complexity. We apply this framework to obtain near-optimal quantum query complexities for various string problems, such as (i) recognizing regular languages; (ii) decision versions of String Rotation and String Suffix; and natural parameterized versions of (iii) Longest Increasing Subsequence and (iv) Longest Common Subsequence.
Based on joint work with Robin Kothari, Matt Kovacs-Deak, Aarthi Sundaram, and Daochen Wang (arXiv:2210.06419).
About EQSI
European Quantum Software Institute (EQSI) is an initiative for quantum software research and education in Europe.
The initiative unites 6 leading research institutions to conduct joint research projects and educational and outreach activities, in collaboration with providers of quantum computing infrastructure and industry partners interested in developing quantum algorithms.
EQSI activities include annual workshops and monthly online seminars.
Subscribe to the EQSI mailing list to receive the announcements of the EQSI Colloquium, as well as other news and events from EQSI: https://mlists.ist.utl.pt/mailman/listinfo/groups.pqi.eqsi-info