- This event has passed.
Quantum BC Seminar Series – Dr. Daochen Wang
March 12 @ 2:00 pm - 3:00 pm
Join us on Tuesday, March 12 at 2pm for a seminar by Dr. Daochen Wang from the University of British Columbia. The title of his seminar is Quantum Divide and Conquer.
Join on Zoom:
https://ubc.zoom.us/j/69443327772?pwd=TGhhTXFIQ3ZiUmNrN0pUa3FObTNydz09
Meeting ID: 694 4332 7772 Passcode: 996727
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 Andrew M. Childs, Robin Kothari, Matt Kovacs-Deak, and Aarthi Sundaram (arXiv:2210.06419).
Bio:
Dr. Daochen Wang obtained his PhD in Applied Mathematics from the University of Maryland under advisors Andrew Childs and Carl Miller. Before that, he obtained his Bachelors and Masters from the University of Cambridge.
Dr. Wang since moved to Vancouver to start as an Assistant Professor with the Department of Computer Science at the University of British Columbia this past October. He will research quantum computation and information.
He is interested in the structures beneath quantum speed-ups, algorithm design, and real-world applications. Recently Daochen has also become interested in quantum cryptography.