论文标题
利用量子查询算法中的未知结构
Leveraging Unknown Structure in Quantum Query Algorithms
论文作者
论文摘要
当保证输入具有一定的结构时，用于功能评估的量子跨度程序算法通常会降低查询复杂性。我们设计了修改后的跨度程序算法，即使没有提前有希望，也可以将这些加速度持续存在，我们将这种方法扩展到了更一般的状态转换问题。例如，有一个跨度程序算法决定是否在$ n $ vertex图中连接了两个顶点，通常用$ o（n^{3/2}）$ QUERIES QUERIES，但如果有的话，如果有的话，如果有$ o（\ sqrt {k} n）$ QUERIES，如果有的话，如果有$ k $ k $ k $ edges。我们的算法使用$ \ tilde {o}（\ sqrt {k} n）$ QUERIES来解决此问题，如果最多有$ k $ edges的路径，而没有提前不知道$ k $。
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(\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$ ahead of time.
