Southwest Quantum Information and Technology

Improved quantum query algorithms on non-worst-case inputs

Presenting Author: Shelby Kimmel, Middlebury College
Contributing Author(s): Noel Anderson Jay-U Chung Da-Yeon Koh Chloe Ye

Quantum span program algorithms for function evaluation sometimes have reduced query complexity when promised that the input has a certain structure. We design a modified span program algorithm to show these improvements persist even without a promise ahead of time, and we extend this approach to the more general problem of state conversion. For example, there is a span program algorithm that decides whether two vertices are connected in an \(n\)-vertex graph with \(O(n^{3/2})\) queries in general, but with \(O(\sqrt{k}n)\) queries if promised that, if there is a path, there is one with at most \(k\) edges. Our algorithm uses \(\tilde{O}(\sqrt{k}n)\) queries to solve this problem if there is a path with at most \(k\) edges, without knowing \(k\) in advance.

Read this article online: https://arxiv.org/abs/2012.01276

(Session 5 : Thursday from 5:00 pm - 7:00 pm)