Parameterized Quantum Query Algorithms for Graph Problems
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909281087913984 |
|---|---|
| author | Terao, Tatsuya Mori, Ryuhei |
| author_facet | Terao, Tatsuya Mori, Ryuhei |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_03864 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Parameterized Quantum Query Algorithms for Graph Problems Terao, Tatsuya Mori, Ryuhei Quantum Physics Data Structures and Algorithms 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. |
| title | Parameterized Quantum Query Algorithms for Graph Problems |
| topic | Quantum Physics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2408.03864 |