Quantum divide and conquer

CS/MATH Seminar - Daochen Wang QuICS, UMD Zoom or join to watch in QNC 1201

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 quantum speedup 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 Andrew M. Childs, Robin Kothari, Matt Kovacs-Deak, and Aarthi Sundaram (arXiv:2210.06419).

Join Zoom Meeting

https://uwaterloo.zoom.us/j/94812483356?pwd=WmpXVFJRRi9kK1BTS1B5YnhnS3phZz09

Meeting ID: 948 1248 3356

Passcode: 064505

Add event to calendar