The second EQSI Colloquium will take place on Tuesday, May 16, 17:00 CET with a talk "Quantum divide and conquer" by Andrew M. Childs.
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).
Talk schedule:
Tuesday, March 21, 2023 5pm CET (EQSI Colloquium): Ashley Montanaro (Phasecraft and University of Bristol), Near-term quantum algorithms for optimization (Watch on Youtube).
Monday, April 17, 2023, 5pm CET (EQSI Seminar): Freek Witteveen (University of Copenhagen), The minimal canonical form of a tensor network
Tuesday, May 16, 2023, 5pm CET (EQSI Colloquium): Andrew Childs (University of Maryland), TBA
Monday, June 19, 2023, 5pm CET (EQSI Seminar): Speaker and title TBA
Recordings of the EQSI Colloquium talks will be available on the EQSI Youtube channel.