ヨシノ　キヨト   吉野　聖人    所属   東邦大学  理学部 情報科学科    職種   講師
論文種別	原著
言語種別	英語
査読の有無	査読あり
表題	A quantum searching model finding one of the edges of a subgraph in a complete graph
掲載誌名	正式名：Quantum Information Processing
巻・号・頁	21(6),pp.222-222
著者・共著者	Yusuke Yoshie,Kiyoto Yoshino
担当区分	筆頭著者
発行年月	2022/02/03
概要	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.
DOI	10.1007/s11128-022-03553-2
arXiv ID	arXiv:2202.01464
DBLP ID	journals/qip/YoshieY22
PermalinkURL	http://arxiv.org/abs/2202.01464v2
researchmap用URL	http://arxiv.org/pdf/2202.01464v2