Quantum divide and conquer

Add to your list(s) Download to your calendar using vCal

• Andrew Childs (University of Maryland)
• Tuesday 28 March 2023, 15:00-16:15
• Zoom.

If you have a question about this talk, please contact Sergii Strelchuk.

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 Robin Kothari, Matt Kovacs-Deak, Aarthi Sundaram, and Daochen Wang (arXiv:2210.06419).

Zoom link: https://us02web.zoom.us/j/85407695986?pwd=TFNOcFk5RzNneUQwbGxCaU9pVEF5dz09

This talk is part of the CQIF Seminar series.

This talk is included in these lists:

• All CMS events
• CMS Events
• CQIF Seminar
• DAMTP info aggregator
• Hanchen DaDaDash
• Interested Talks
• Zoom
• bld31

Note that ex-directory lists are not shown.