{"id":"arxiv/2610.13906","url":"https://arxiv.org/abs/2610.13906","tags":["quant-ph","cs.CC"],"score":0,"title":"Quantum Query Complexity of Maximum Degree and its Generalizations","domain":"quant-ph","source":"arxiv","authors":["Amin Shiraz Gilani","Nikhil S. Mande","Subhasree Patro","Nithish Raja"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-10-09","reactions":{}}