Continuous-Time Quantum Search on Balanced Trees
Continuous-Time Quantum Search on Balanced Trees
复制标题
平衡树上的连续时间量子搜索
DOI：
10.1103/physreva.93.032305
复制
发表时间：
2016
影响因子：
2.9
通讯作者：
S. Boettcher
中科院分区：
文献类型：
--
作者：
Pascal Philipp;Luís Tarrataca;S. Boettcher
我们研究网络异构性对量子搜索算法性能的影响。为此，我们研究了树上的量子搜索，以寻找连续时间量子行走所采用的预言哈密顿公式。我们使用分析和数值参数来表明，随着搜索站点从树的根部向叶子移动，渐近运行时间的指数 $\sim N^{\beta}$ 从 $\beta=0.5$ 均匀变化到 $\beta=1$。这些结果意味着平衡树上的量子搜索算法的时间复杂度与搜索站点的某些基于路径的中心性度量密切相关。
We examine the effect of network heterogeneity on the performance of quantum search algorithms. To this end, we study quantum search on a tree for the oracle Hamiltonian formulation employed by continuous-time quantum walks. We use analytical and numerical arguments to show that the exponent of the asymptotic running time $\sim N^{\beta}$ changes uniformly from $\beta=0.5$ to $\beta=1$ as the searched-for site is moved from the root of the tree towards the leaves. These results imply that the time complexity of the quantum search algorithm on a balanced tree is closely correlated with certain path-based centrality measures of the searched-for site.