Quantum Query Complexity of Maximum Degree and its Generalizations

We study the quantum query complexity of several basic graph problems. 1) We prove a tight $\mathrm{\Theta }(n^{3\mathrm{/}2})$ bound for finding a maximum-out-degree vertex in an $n$-vertex tournament, resolving a conjecture of Mande, Paraashar, and Saurabh [FSTTCS’23]. 2) Using the same proof idea, we give a direct proof that finding a maximum-degree vertex in an $n$-vertex undirected graph requires $\mathrm{\Theta }(n^{3\mathrm{/}2})$ quantum queries, a bound implicit in the work of Apers and Lee [CCC’21]. Both lower bounds above hold even for computing only the maximum degree or maximum out-degree. 3) We also study Maximum $(k,n-k)$-Cut, which asks for the largest cut with one side of size $k$. For every constant $k\ge 1$, we give an $O(n^{2-1\mathrm{/}(k+1)})$-query quantum algorithm. 4) We establish a reduction to Maximum $(k,n-k)$-Cut involving $k$-Graph Collision, which asks whether the marked vertices of a known graph contain a $k$-clique. For $k\ge 3$, this yields unconditional lower bounds with exponents strictly larger than $3\mathrm{/}2$, showing that this problem is strictly harder than computing maximum degree. Additionally, under a conjecture we propose for $k$-Graph Collision, the reduction yields a lower bound matching our upper bound above.