#  Seminar: Andrew Childs (University of Maryland): "Quantum divide and conquer" 

 



####  calendar\_today Date and Time 

 **February 28, 2023** 

 09:30AM - 09:30AM EST 

####  pin\_drop Location 

 **https://harvard.zoom.us/j/779283357?pwd=MitXVm1pYUlJVzZqT3lwV2pCT1ZUQT09**  



 

 



 

   ![Andrew Childs](/sites/g/files/omnuum6611/files/styles/hwp_1_1__360x360_scale/public/mathpicture/files/andrew_childs.jpg?itok=Q5wBiwd2) 

 

  
Speaker: Andrew Childs (University of Maryland)  
**Title:** Quantum divide and conquer  
**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 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).



 

 

---

 Attachments- [  picture\_as\_pdf  23-2-28\_andrew\_childs\_seminar.pdf ](/sites/g/files/omnuum6611/files/mathpicture/files/23-2-28_andrew_childs_seminar.pdf)
 
---

 



 

 

 Share on:- [     Facebook ](#)
- [     Twitter ](#)
- [     Linkedin ](#)
 


 Save: [ Add to calendar calendar\_today ](https://mathpicture.fas.harvard.edu/node/1663719/event-feed.ics)  Copy link link