Tatsuya Terao, Ryuhei Mori
Published 2024-08-07Version 1
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.
Comments: 32 pages, 4 figures, abstract shortened to meet arXiv requirement; to appear in ESA'24
Quantum query complexity of some graph problems
Lower Bounds on Error Exponents via a New Quantum Decoder
Lower bounds on concurrence and negativity from a trace inequality
![QR code for arXiv:2408.03864 [quant-ph]](http://oss.arxitics.com/images/favicon.svg)