论文标题
在签名图上对匹配的量子搜索
Quantum search of matching on signed graphs
论文作者
论文摘要
我们构建了由量子步行驱动的签名边缘的量子搜索模型。此量子步行的时间演化操作员提供了一个加权邻接矩阵，该矩阵通过将符号分配到每个边缘引起。这个标志可以被认为是所谓的边缘着色。然后，作为一个应用程序，在任意边缘着色下，在完整的图上给出了匹配，我们考虑从完整图的边缘集对彩色边缘进行量子搜索。我们表明，此量子步行在$ O（N^{\ frac {2-α} {2-α} {2}}} $的时间复杂性内找到有色边缘，概率$ 1-O（1）$（1）$，而相应的随机步行图会在$ O（N^{2-α} $的时间复杂性范围内找到$（n^{2-α}）$ n $ n of ed n $ ed n niging n of Edgens的时间复杂性。 \leα\ le 1 $。
We construct a quantum searching model of a signed edge driven by a quantum walk. The time evolution operator of this quantum walk provides a weighted adjacency matrix induced by the assignment of sign to each edge. This sign can be regarded as so called the edge coloring. Then as an application, under an arbitrary edge coloring which gives a matching on a complete graph, we consider a quantum search of a colored edge from the edge set of a complete graph. We show that this quantum walk finds a colored edge within the time complexity of $O(n^{\frac{2-α}{2}})$ with probability $1-o(1)$ while the corresponding random walk on the line graph finds them within the time complexity of $O(n^{2-α})$ if we set the number of the edges of the matching by $O(n^α)$ for $0 \le α\le 1$.
