论文标题
量子搜索模型在完整的图中找到子图的边缘之一
A quantum searching model finding one of the edges of a subgraph in a complete graph
论文作者
论文摘要
某些量子搜索模型已通过扰动的量子步道给出。驾驶一些扰动的量子步行，我们可能很快找到一个概率很高的目标之一。在本文中，我们构建了一个量子搜索模型，在完整的图中找到了给定子图的边缘之一。如何构建我们的模型是，我们将ARCS标记为$+1 $或$ -1 $，并通过ARCS集的标志功能定义了一个扰动的量子步行。之后，我们检测到一个用诱导标志功能标记为$ -1 $的边缘之一。 Segawa等人首先提出了这个想法。在2021年。它们仅解决了子图形成匹配的情况，并通过组合参数获得的情况是，查找子图的一个边缘的时间比经典搜索模型快四倍地四边形。在本文中，我们表明该模型对任何子图有效，即，通过光谱分析获得了二次加速，用于在完整的图中找到一个子图的边缘之一。
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 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 by $+1$ or $-1$, and define a perturbed quantum walk by the sign function on the set of arcs. After that, we detect one of the edges labeled $-1$ by the induced sign function as fast as possible. This idea was firstly proposed by Segawa et al. in 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.
