标题： 时间和空间高效的量子检测循环和测试二分图算法 显示英文标题

标题： Time and Space Efficient Quantum Algorithms for Detecting Cycles and Testing Bipartiteness

摘要： 我们研究了两个图问题的空间和时间高效的量子算法： - 判断一个$n$顶点的图是否是森林，以及它是否是二分图。 通过将问题归约为 s-t 连通性问题，我们在邻接矩阵模型中描述了用于判定这两个性质的量子算法，运行时间为$\tilde{O}(n^{3/2})$，并且使用了$O(\log n)$个经典比特和量子比特作为存储空间。 然后，我们在邻接数组模型中给出了用于判定这两个性质的量子算法，这些算法运行时间为$\tilde{O}(n\sqrt{d_m})$，同样需要$O(\log n)$的空间，其中$d_m$是输入图中任意顶点的最大度数。 显示英文摘要

摘要： We study space and time efficient quantum algorithms for two graph problems -- deciding whether an $n$-vertex graph is a forest, and whether it is bipartite. Via a reduction to the s-t connectivity problem, we describe quantum algorithms for deciding both properties in $\tilde{O}(n^{3/2})$ time and using $O(\log n)$ classical and quantum bits of storage in the adjacency matrix model. We then present quantum algorithms for deciding the two properties in the adjacency array model, which run in time $\tilde{O}(n\sqrt{d_m})$ and also require $O(\log n)$ space, where $d_m$ is the maximum degree of any vertex in the input graph.