Source-linked AI summary
Quantum Query Complexity of Maximum Degree and its Generalizations
Amin Shiraz Gilani, Nikhil S. Mande, Subhasree Patro, Nithish Raja
TL;DR
The paper addresses unresolved quantum query complexity questions for maximum-degree graph problems and Maximum (k, n−k)-Cut. It uses reductions to prove tight bounds for maximum degree and tournament maximum out-degree, and establishes cut bounds with conditional tightness.
Problem
The quantum query complexity of finding a maximum-degree vertex in an undirected graph, finding a maximum-out-degree vertex in a tournament, and solving Maximum (k, n−k)-Cut remained unresolved.
Source: §1 · p. 2Method
The paper reduces composed ORm ◦ PrMajm instances to degree problems and uses a k-Graph Collision reduction for Maximum (k, n−k)-Cut.
Source: §1 · p. 3Results
Both maximum-degree tasks have quantum query complexity Θ(n^3/2), and the paper establishes upper and unconditional lower bounds for Maximum (k, n−k)-Cut.
Source: §1.1 · p. 3, §1 · p. 3Takeaways & Limitations
The tournament bound resolves the tightness question of Mande, Paraashar, and Saurabh, while the degree lower bounds also apply to computing only the maximum degree or out-degree.
Source: §1 · p. 3, §1.1 · p. 3
Abstract
from arXiv · showhide
We study the quantum query complexity of several basic graph problems. 1) We prove a tight $\Theta(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 $\Theta(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.
1 Introduction
The paper proves tight quantum query bounds for maximum degree and tournament maximum out-degree, then establishes upper and lower bounds for Maximum (k, n−k)-Cut. Its cut lower bounds use a reduction involving k-Graph Collision, with matching bounds conditional on a conjecture.
1.1 Our results
- Θ(n^3/2) quantum queries are necessary and sufficient for finding a maximum-degree vertex in an undirected graph and a maximum-out-degree vertex in a tournament.The lower bounds also hold when computing only the maximum degree or maximum out-degree.Source: §1.1 · p. 3
N · Q(GCG
- For k = 3, 4, and 5, the reduction yields unconditional lower bounds of n^(14/9−o(1)), n^(19/12−o(1)), and n^(8/5−o(1)), respectively.These bounds use lower bounds for clique collision by Gilani and Zhou [GZ26, Theorem 1.2].Source: N · Q(GCG · p. 4
- Assuming the conjecture that k-Graph Collision has worst-case complexity Ω(N^(1−1/(k+1))), the cut reduction gives a tight bound for Maximum (k, n−k)-Cut.The paper conjectures this lower bound for every constant k ≥ 2.Source: N · Q(GCG · p. 4
1.2 Our techniques
- The maximum-degree and maximum-out-degree lower bounds follow from reductions from ORm ◦ PrMajm, whose query complexity is Ω(m^3/2).The tournament result resolves the tightness question of Mande, Paraashar, and Saurabh.Source: §1.2 · pp. 4–5
- For constant k, Maximum (k, n−k)-Cut can be computed with O(n^(2−1/(k+1))) queries by narrowing its value to an interval and testing thresholds.The interval comes from the sum of the k largest degrees and the cut of those selected vertices.Source: §1.2 · p. 5
- The cut lower-bound reduction encodes marked vertices through degrees and makes a cut of size 3kN/2 + k possible exactly for a marked k-clique.The reduction is query-preserving from k-Graph Collision composed with PrMajN to Maximum (k, 3N)-Cut.Source: §1.2 · pp. 6–7
2 Preliminaries
The preliminaries establish graph notation and the quantum query model, then collect the problem definitions, standard query bounds, and quantum-walk framework used later.
N · Q(GCG
- Graph notation encodes undirected graphs and tournaments as Boolean strings and defines degree, out-degree, cuts, and regular tournaments.The section also fixes standard set and asymptotic notation.Source: N · Q(GCG · p. 7
2.1 Functions and relations of interest
- Maximum (k,n−k)-Cut maximizes the boundary of a k-vertex set, while OR and Promise Majority provide Boolean functions used in query reductions.Promise Majority distinguishes inputs of weight n/2 from n/2 + 1.Source: §2.1 · pp. 7–8
2.2 Quantum query complexity
- The query model defines bounded-error quantum query complexity; standard results give Q(OR_n)=Ω(√n), Q(PrMaj_n)=Ω(n), and quantum maximum finding uses O(√|S|) queries.The section also states a composition lower bound for quantum query complexity.Source: §2.1 · p. 7, §2.2 · p. 8
2.3 Quantum walk on Johnson graph
- The MNRS quantum-walk framework searches marked states using setup, update, and checking costs on an ergodic reversible chain; the Johnson graph walk has a uniform stationary distribution.Johnson-graph states are r-element subsets, adjacent when one element is replaced.Source: §2.3 · p. 9
3 Computing maximum out-degree in a tournament
The section proves that finding a maximum-out-degree vertex in an n-vertex tournament takes Θ(n^3/2) quantum queries. Its lower bound reduces a composed OR and Promise Majority problem, and its upper bound uses quantum maximum finding.
Theorem 1.2
- Θ(n^3/2) quantum queries are necessary and sufficient to find a maximum-out-degree vertex in an n-vertex tournament.The theorem states the bounded-error query complexity as Q(MOD_n)=Θ(n^3/2).Source: §3 · p. 10
Lower bound
- For arbitrary n, padding the largest eligible instance of size 3a+1 preserves the Ω(n^3/2) lower bound because that size is Θ(n).The added vertices receive edges directed from every old vertex toward each new vertex.Source: §3 · p. 10
Upper bound
- Computing one vertex's out-degree takes n−1 queries, so quantum maximum finding gives an O(n^3/2)-query upper bound.The algorithm evaluates out-degree across the n vertices and then computes the selected vertex's out-degree.Source: §3 · p. 10
Reduction
- Each input block's weight sets its paired vertices' out-degrees: weight a/2 gives both 3a/2, while weight a/2+1 splits them into 3a/2+1 and 3a/2−1.The construction uses fixed regular tournaments on its vertex groups.Source: §3 · p. 11
Lower bound
- The cited result gives Q(OR_a ◦ PrMaj_a) ≤ Q(MOD_{3a+1}) + 3a, equivalently Q(MOD_{3a+1}) ≥ Q(OR_a ◦ PrMaj_a) − 3a, via an almost query-preserving reduction.Source: §3 · pp. 10–11
4 Computing the maximum degree of an undirected graph
The section gives a direct reduction-based proof that finding a maximum-degree vertex in an n-vertex undirected graph takes Θ(n^3/2) quantum queries. It also supplies the matching upper bound using quantum maximum finding.
Theorem 1.1
- Θ(n^3/2) bounded-error quantum queries are necessary and sufficient to find a maximum-degree vertex in an n-vertex undirected graph.The lower bound was implicit in Apers and Lee [AL21, Theorem 37].Source: §4 · p. 12
Lower bound
- The lower bound extends to arbitrary n by padding a graph on 4⌊n/4⌋ vertices with isolated vertices, without losing a valid maximum-degree output.The padded instance size remains Θ(n).Source: §4 · p. 12
Upper bound
- Computing a specified vertex's degree takes n−1 queries, so quantum maximum finding gives an O(n^3/2)-query upper bound.The algorithm evaluates degree over the n vertices.Source: §4 · p. 12
Lower bound
- The reduction turns OR_{n/2}◦PrMaj_{n/2} into maximum-degree finding: edge queries cost one input query, and at most n−1 more queries test whether the output degree is 3n/4.The output-degree test distinguishes the two cases in the reduction.Source: §4 · p. 13
5 Generalizing the notion of maximum degree
For constant k, Maximum (k,n−k)-Cut has an upper bound of O(n^{2−1/(k+1)}) queries and a lower bound of Ω(n^{3/2}). The section gives a threshold algorithm and a reduction from graph collision to establish lower bounds.
5 Generalizing the notion of maximum degree
- For every constant k≥1, Q(MaxCut_k,n) is Ω(n^{3/2}) and O(n^{2−1/(k+1)}).When k=1, this problem is maximum degree.Source: §5 · p. 13, N · Q(GCG · p. 13
N · Q(GCG
- The threshold test decides whether MaxCut_k,n(G)≥t using O(n^{2−1/(k+1)}) quantum queries.For k≤log n, it searches the Johnson graph J(n,r), marking subsets containing a k-set whose cut reaches t.Source: N · Q(GCG · pp. 13–14
- For k≤log n, summing the degrees of the k highest-degree vertices brackets the optimum within k(k−1), enabling binary search over thresholds.The degree sum is at most A, while the selected vertices' cut is at least A−k(k−1).Source: N · Q(GCG · pp. 14–15
5.2 Lower bounds via graph collision
- A query-preserving reduction makes the maximum cut reach k(3n/2+1) exactly when the input graph has a k-clique of marked vertices.The construction uses degree differences to encode marked vertices and penalizes non-edges within the selected set.Source: §5.2 · pp. 15–16
- Applying the reduction with G=K_n yields an unconditional Ω(n^{3/2}) lower bound for every constant k≥1.Padding with isolated vertices extends the construction to arbitrary sufficiently large n.Source: §5.2 · p. 17
AI Statement
The authors report using ChatGPT in developing some proofs and editing the exposition. They state that they checked and refined the arguments and take responsibility for the results and proofs.
AI Statement
- The authors used ChatGPT in developing some proofs and editing the exposition, then checked and refined the arguments and take responsibility for the results and proofs.The passage says the maximum-out-degree lower-bound argument was first supplied as a row-and-column-sum problem and later presented as a reduction from OR◦PrMaj.Source: AI Statement · p. 18