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 Θ(n 3/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 Θ(n 3/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 at least 1, we give an O(n 2-1/(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 at least 3, this yields unconditional lower bounds with exponents strictly larger than 3/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.