Leveraging Unknown Structure in Quantum Query Algorithms
share
Quantum span program algorithms for function evaluation commonly have reduced query complexity when promised that the input has a certain structure. We design a modified span program algorithm to show these speed-ups persist even without having 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(√(k)n) queries if promised that, if there is a path, there is one with at most k edges. Our algorithm uses Õ(√(k)n) queries to solve this problem if there is a path with at most k edges, without knowing k ahead of time.
READ FULL TEXT