Limitation of Quantum Walk Approach to the Maximum Matching Problem

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²\). 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.