Parameterized Quantum Query Algorithms for Graph Problems

Abstract

In this paper, we consider the parameterized quantum query complexity for graph problems. We design parameterized quantum query algorithms for $k$-vertex cover and $k$-matching problems, and present lower bounds on the parameterized quantum query complexity. Then, we show that our quantum query algorithms are optimal up to a constant factor when the parameters are small.

32 pages, 4 figures, abstract shortened to meet arXiv requirement; to appear in ESA'24