Title:Â On Quantum Query Complexity, Divide-and-Conquer, and Regular Languages Speaker:Â Â Matt Kovacs-Deak (QuICS) Time:Â Â Wednesday, May 15, 2024 - 3:00pm Location:Â Â ATL 3100A
Our recent work investigated the use of divide-and-conquer strategies in the design of quantum query algorithms. Following a brief review of these findings, this talk will focus on ongoing work aimed at strengthening one of our earlier results. In particular, we will propose a randomized quantum query algorithm for checking membership in a specific regular language. The analysis of this algorithm will be discussed, with an emphasis on some of the technical details. We conclude with some of the potential implications of our research. Specifically, we will briefly discuss how we hope to strengthen a result of Aaronson, Grier and Schaeffer on the query complexity of star-free regular languages.