澳门新葡亰平台游戏 学术动态

【学术预告】Controlled quantum search on structured databases

Grover's algorithm provides a quadratic quantum speedup for searches on unsorted databases, and a simple approach via continuous-time quantum walk (CTQW) can also achieve the quantum speedup on certain graphs like the complete graphs. However, a standard approach via CTQW cannot achieve the same quantum advantage on databases with tree structures like the telephone directories. We propose quantum algorithms to search on databases with tree structures via generalized CTQWs. In order to find a marked vertex on a balanced tree of height $r$ with $N$ vertices, we adopt a multi-stage search process with suitable jumping rates at each stage. A success probability close to $100\%$ is achieved and a runtime with the dominant term proportional to $N^{(2r-1)/2r}$ is obtained when the branching factor is large. We further find that the number of stages can be actually controlled while keeping the high success probability. By adjusting the edge weights on the graphs, we can merge the multi-stage search process into a single stage, and achieve an optimal runtime $\Theta(\sqrt{N})$! Our search algorithms also work for real trees with unbalanced structures and are quite robust against various kinds of small perturbations.