Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2510.26246 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909878143942656 |
|---|---|
| author | Júnior, Alcides Gomes Andrade Matsubayashi, Akira |
| author_facet | Júnior, Alcides Gomes Andrade Matsubayashi, Akira |
| contents | The Maximum Matching problem has a quantum query complexity lower bound of $Ω(n^{3/2})$ for graphs on $n$ vertices represented by an adjacency matrix. The current best quantum algorithm has the query complexity $O(n^{7/4})$, which is an improvement over the trivial bound $O(n^2)$. Constructing a quantum algorithm for this problem with a query complexity improving the upper bound $O(n^{7/4})$ is an open problem. The quantum walk technique is a general framework for constructing quantum algorithms by transforming a classical random walk search into a quantum search, and has been successfully applied to constructing an algorithm with a tight query complexity for another problem. In this work we show that the quantum walk technique fails to produce a fast algorithm improving the known (or even the trivial) upper bound on the query complexity. Specifically, if a quantum walk algorithm designed with the known technique solves the Maximum Matching problem using $O(n^{2-ε})$ queries with any constant $ε>0$, and if the underlying classical random walk is independent of an input graph, then the guaranteed time complexity is larger than any polynomial of $n$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_26246 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Limitation of Quantum Walk Approach to the Maximum Matching Problem Júnior, Alcides Gomes Andrade Matsubayashi, Akira Quantum Physics Computational Complexity F.2.3 The Maximum Matching problem has a quantum query complexity lower bound of $Ω(n^{3/2})$ for graphs on $n$ vertices represented by an adjacency matrix. The current best quantum algorithm has the query complexity $O(n^{7/4})$, which is an improvement over the trivial bound $O(n^2)$. Constructing a quantum algorithm for this problem with a query complexity improving the upper bound $O(n^{7/4})$ is an open problem. The quantum walk technique is a general framework for constructing quantum algorithms by transforming a classical random walk search into a quantum search, and has been successfully applied to constructing an algorithm with a tight query complexity for another problem. In this work we show that the quantum walk technique fails to produce a fast algorithm improving the known (or even the trivial) upper bound on the query complexity. Specifically, if a quantum walk algorithm designed with the known technique solves the Maximum Matching problem using $O(n^{2-ε})$ queries with any constant $ε>0$, and if the underlying classical random walk is independent of an input graph, then the guaranteed time complexity is larger than any polynomial of $n$. |
| title | Limitation of Quantum Walk Approach to the Maximum Matching Problem |
| topic | Quantum Physics Computational Complexity F.2.3 |
| url | https://arxiv.org/abs/2510.26246 |