Abstract: The difficulty of solving a problem is often input dependent. For example, if you are searching an unordered list for an item, it is easier to find one if there are multiple copies. Quantum algorithms should also do better on easier inputs, but prior work for an important class of query algorithms only gives an improvement if you know ahead of time that you have an easier input. We designed an algorithm that matches the complexity (up to log factors) of the prior algorithm, but without knowing the difficulty of the input in advance. This work opens the door for average-case analyses of a broad range of quantum query problems. (Joint work with Noel Anderson and Jay-U Chung.
==========
All seminars are hosted as webinars on Zoom at 1:00 PM MST on Fridays, and can be accessed at these links:
Note: Attendance for the Zoom Webinar is capped at 500 participants on a first come first serve basis. Please connect on time to guarantee your participation. The YouTube link is unlimited.