Limitation of Quantum Walk Approach to the Maximum Matching Problem

Alcides Gomes Andrade Júnior, Akira Matsubayashi

The Maximum Matching problem has a quantum query complexity lower bound of $\Omega (n^{3/2})$ for graphs on $n$ vertices represented by an adjacency matrix. The current best quantum algo…