Quantum Query Complexity of Maximum Degree and its Generalizations
Abstract
We study the quantum query complexity of several basic graph problems. 1) We prove a tight Θ(n3/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 Θ(n3/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≥ 1, we give an O(n2−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≥ 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.
Related
- Near-Optimal Separations of Certificate Complexity from Randomized and Quantum Query Complexity
- Near-optimal quantum query lower bounds on bipartiteness and expansion testing in the bounded-degree graph model
- Quantum Query Complexity Beyond the Worst Case
- Quantum Query Complexity of Tournament Solutions
- Optimal query complexity for fractional quantum evolution
BibTeX
@misc{gilani2026quantum,
title = {{Quantum Query Complexity of Maximum Degree and its Generalizations}},
author = {Amin Shiraz Gilani and Nikhil S. Mande and Subhasree Patro and Nithish Raja},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.13906},
eprint = {2610.13906},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.13906},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Quantum Query Complexity of Maximum Degree and its Generalizations
AU - Amin Shiraz Gilani
AU - Nikhil S. Mande
AU - Subhasree Patro
AU - Nithish Raja
PY - 2026
DA - 2026/10/09
PB - arXiv
DO - 10.48550/arxiv.2610.13906
UR - https://arxiv.org/abs/2610.13906
AB - 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≥ 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≥ 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.
ER -