arXiv:2610.13906
Quantum Query Complexity of Maximum Degree and its Generalizations
Amin Shiraz Gilani, Nikhil S. Mande, Subhasree Patro, Nithish Raja
Abstract
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\geq 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\geq 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.
AI Summary
The paper studies bounded-error quantum query complexity of exact graph optimization in the adjacency-matrix model: finding a maximum-degree vertex in an undirected graph, finding a maximum-out-degree vertex in a tournament, and computing the largest cut whose smaller designated side has exactly $k$ vertices. For both maximum-degree problems it establishes tight $\Theta(n^{3/2})$ bounds, including when only the maximum degree value is required. The tournament result resolves a previously stated conjecture; the undirected bound was implicit in earlier work. The lower bounds encode $\mathrm{OR}_m\circ\mathrm{PrMaj}_m$ into degrees, where promise majority distinguishes Hamming weights $m/2$ and $m/2+1$. Query-preserving graph constructions and quantum query composition give $\Omega(m^{3/2})$; quantum maximum finding supplies matching upper bounds. For Maximum $(k,n-k)$-Cut, the paper gives an $O(n^{2-1/(k+1)})$-query algorithm for every fixed $k$. It combines a Johnson-graph quantum walk storing vertex neighborhoods with a degree-based interval containing the optimum. A reduction from $k$-Graph Collision composed with promise majority proves $\Omega(N\,Q(\mathsf{GC}_k^G))$ for cuts on $3N$ vertices. Existing clique-collision bounds yield unconditional lower bounds strictly above $n^{3/2}$ for fixed $k\geq3$, including $n^{14/9-o(1)}$, $n^{19/12-o(1)}$, and $n^{8/5-o(1)}$ for $k=3,4,5$. Matching cut lower bounds remain conditional on a proposed worst-case $k$-Graph Collision conjecture, generalizing the standard graph-collision conjecture. The results concern query complexity, not computational running time.
We used OpenAI’s ChatGPT (GPT-5.5 and GPT-5.6) in developing some of the proofs and in editing the exposition.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.