A quantum searching model finding one of the edges of a subgraph in a complete graph
A quantum searching model finding one of the edges of a subgraph in a complete graph
复制标题
DOI：
10.1007/s11128-022-03553-2
复制
发表时间：
2022-02
影响因子：
2.5
通讯作者：
Y. Yoshie;Kiyoto Yoshino
中科院分区：
文献类型：
--
作者：
Y. Yoshie;Kiyoto Yoshino
Some of the quantum searching models have been given by perturbed quantum walks. Driving some perturbed quantum walks, we may quickly find one of the targets with high probability. In this paper, we address a discrete-time quantum walk. We construct a quantum searching model finding one of the edges of a given subgraph in a complete graph. How to construct our model is that we label the arcs byor, and define a perturbed quantum walk by the sign function on the set of arcs. After that, we detect one of the edges labeledby the induced sign function as fast as possible. This idea was firstly proposed by Segawa (Quantum Inf Process 20:182, 2021). They only addressed the case where the subgraph forms a matching, and obtained by a combinatorial argument that the time of finding one of the edges of the subgraph is quadratically faster than a classical searching model. In this paper, we show that the model is valid for any subgraph, i.e., we obtain by spectral analysis a quadratic speed-up for finding one of the edges of the subgraph in a complete graph.
