⚛️ quantum physics

Quantum Query Complexity of Maximum Degree and its Generalizations

This paper establishes tight $\Theta(n^{3/2})$ quantum query bounds for finding maximum-degree vertices in tournaments and undirected graphs, while also providing an $O(n^{2-1/(k+1)})$ algorithm and conditional lower bounds for the Maximum $(k,n-k)$ -Cut problem, demonstrating its strict hardness relative to maximum degree for $k \geq 3$ .

Original authors: Amin Shiraz Gilani, Nikhil S. Mande, Subhasree Patro, Nithish Raja

Published 2026-10-12

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Amin Shiraz Gilani, Nikhil S. Mande, Subhasree Patro, Nithish Raja

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of computer science, there is a fundamental question about how much information a machine needs to gather to solve a problem. Imagine you are handed a map of a city, but you cannot see the whole thing at once. You can only ask a guide specific questions: "Is there a road connecting this intersection to that one?" The goal is to find a specific feature of the city, like the busiest intersection, using as few questions as possible. This is the essence of query complexity. For decades, scientists have studied how classical computers, which ask questions one by one, perform these tasks. However, a newer type of computer, known as a quantum computer, has a unique ability. It can ask many questions at the same time by existing in a state of superposition, effectively checking multiple possibilities in a single step. This power promises to solve certain problems much faster than ever before, but for many basic tasks, the exact speed limit of these quantum machines remained a mystery.

A team of researchers has now closed the book on several of these mysteries, specifically regarding how to find the most connected points in a network. They focused on two main scenarios: a standard map where connections go both ways, and a tournament-style map where every pair of points has a one-way connection, like a rock-paper-scissors outcome between every pair of players. The central question was simple: how many queries does a quantum computer need to find the single point with the most connections, or to calculate the highest number of connections any point has? Before this work, scientists knew a method existed that would solve the problem by asking roughly the square root of the total number of points, multiplied by the total number of points again. They suspected this was the best possible speed, but they could not prove it. This new study provides that proof. The researchers demonstrated that for finding the most connected point in either type of network, the quantum computer cannot do better than a specific mathematical limit. They showed that the number of questions required grows at a rate that is exactly proportional to the total number of points multiplied by the square root of that number. This confirms that the known method is indeed the fastest possible way to solve this problem, leaving no room for a faster quantum shortcut.

The team did not stop at the most connected point. They also investigated a more complex variation of the problem: finding a group of a specific size that, when separated from the rest of the network, cuts the maximum number of connections. For a group of just one point, this is the same as finding the most connected point. But as the group size increases, the problem becomes significantly harder. The researchers developed a new quantum algorithm that can solve this for any fixed group size, and they proved that this algorithm is highly efficient. However, they also discovered that as the group size grows, the problem becomes strictly harder than simply finding the single most connected point. To prove this, they created a bridge between this cutting problem and another difficult puzzle involving finding a specific pattern of connections within a larger set. They showed that if you can solve the cutting problem efficiently, you can also solve this pattern-matching puzzle. By analyzing the difficulty of the pattern-matching puzzle, they established that the cutting problem requires more computational effort than the simple degree problem, with the difficulty increasing in a precise, predictable way as the group size changes.

The researchers were careful to distinguish between what they had proven and what they suspected. For the basic task of finding the most connected point, the result is absolute; they have mathematically proven that no faster method exists. For the more complex cutting problems, they provided a strong upper limit on how fast a computer can go, and they proved that the problem is strictly harder than the simple version. They also proposed a hypothesis about the difficulty of the underlying pattern-matching puzzle. If this hypothesis is true, then their upper limit for the cutting problem is also the exact lower limit, meaning their algorithm is the best possible. While this specific part relies on a conjecture, the core finding—that the simple problem has a fixed, proven speed limit and that the complex version is inherently more difficult—stands as a solid, proven fact. This work clarifies the boundaries of quantum speed, showing exactly where the power of quantum computing hits a wall for these fundamental graph problems, and providing a clear map for what is possible and what is not.

Technical Summary: Quantum Query Complexity of Maximum Degree and its Generalizations

Problem Statement
This work investigates the bounded-error quantum query complexity of fundamental graph optimization problems within the adjacency-matrix model. The authors address three primary questions:

What is the query complexity of finding a maximum-degree vertex (or computing the maximum degree) in an $n$ -vertex undirected graph?
What is the query complexity of finding a maximum-out-degree vertex (or computing the maximum out-degree) in an $n$ -vertex tournament?
What is the query complexity of the Maximum $(k, n-k)$ -Cut problem, which seeks a subset of vertices $S$ of size exactly $k$ that maximizes the number of edges between $S$ and $V \setminus S$ ?

While a straightforward quantum algorithm using quantum maximum finding [DH96] yields an $O(n^{3/2})$ upper bound for the first two problems, the tightness of this bound and the complexity of the generalized cut problem remained open or partially unresolved.

Methodology
The paper employs a combination of direct reductions, composed function analysis, and quantum walk techniques:

Lower Bounds via Composed Functions: To establish lower bounds for Maximum Degree ( $MD_n$ ) and Maximum Out-Degree ( $MOD_n$ ), the authors reduce from the composed Boolean function $OR_m \circ PrMaj_m$ . Here, $PrMaj_m$ is a promise majority function distinguishing between Hamming weights $m/2$ and $m/2+1$ . The authors construct specific graph instances (an undirected graph $G_x$ and a tournament $T_x$ ) where the maximum degree or out-degree depends directly on the output of $OR_m \circ PrMaj_m$ . By leveraging the composition theorem $Q(f \circ g) = \Omega(Q(f)Q(g))$ [LMR+11] and known lower bounds for $OR$ and $PrMaj$, they derive the complexity.
Reductions to Graph Collision: For the Maximum $(k, n-k)$ -Cut problem, the authors introduce a reduction to the $k$ -Graph Collision problem ( $GCG_k$ ). This problem asks whether the marked vertices of a known graph $G$ contain a $k$ -clique. The authors construct a graph $H_x$ where the maximum $k$ -cut size is maximized if and only if the marked vertices form a $k$ -clique in the underlying graph. This establishes a relationship $Q(MaxCut_{k, 3N}) = \Omega(N \cdot Q(GCG_k))$ .
Upper Bounds via Quantum Walks: For the upper bound on Maximum $(k, n-k)$ -Cut, the authors utilize the MNRS quantum walk framework [MNRS11] on the Johnson graph $J(n, r)$ . The algorithm searches for a subset of size $k$ that induces a large cut. By carefully selecting parameters and using binary search over the possible cut sizes (bounded by the sum of the $k$ largest degrees), they achieve a query complexity dependent on $k$ .

Key Contributions and Results

Tight Bounds for Maximum Degree and Out-Degree:
- The authors prove that the quantum query complexity for finding a maximum-degree vertex in an undirected graph is $\Theta(n^{3/2})$ (Theorem 1.1).
- Similarly, they prove the complexity for finding a maximum-out-degree vertex in a tournament is $\Theta(n^{3/2})$ (Theorem 1.2).
- These results resolve a conjecture by Mande, Paraashar, and Saurabh [MPS23] regarding the tightness of the tournament bound. The lower bounds hold even for the weaker task of computing only the numerical value of the maximum degree/out-degree.
Maximum $(k, n-k)$ -Cut Complexity:
- Upper Bound: For every constant $k \ge 1$ , the authors provide an algorithm with query complexity $O(n^{2 - 1/(k+1)})$ (Theorem 1.3). This improves upon the trivial $O(n^2)$ bound for $k \ge 2$ .
- Unconditional Lower Bounds: By combining their reduction with existing lower bounds for $k$ -Graph Collision [GZ26], they establish unconditional lower bounds for $k \ge 3$ with exponents strictly larger than $3/2$ . Specifically, for $k=3, 4, 5$ , the lower bounds are $\Omega(n^{14/9-o(1)})$ , $\Omega(n^{19/12-o(1)})$ , and $\Omega(n^{8/5-o(1)})$ , respectively (Corollary 1.4). This demonstrates that Maximum $(k, n-k)$ -Cut is strictly harder than computing the maximum degree for $k \ge 3$ .
- Conditional Tightness: The authors propose a conjecture (Conjecture 1.5) that the quantum query complexity of $k$ -Graph Collision is $\Omega(N^{1 - 1/(k+1)})$ . Assuming this conjecture, the upper bound for Maximum $(k, n-k)$ -Cut is tight, yielding $\Theta(n^{2 - 1/(k+1)})$ (Corollary 1.6).

Significance
The paper provides definitive answers to the quantum query complexity of basic degree-finding problems, confirming that the $O(n^{3/2})$ approach is optimal. Furthermore, it extends the study of graph optimization to parameterized cut problems, revealing a hierarchy of difficulty based on the parameter $k$ . The work highlights that while quantum algorithms offer speedups, the complexity of finding optimal cuts grows significantly with the size of the cut set $k$ , surpassing the complexity of simple degree maximization. The reduction to $k$ -Graph Collision serves as a bridge connecting subgraph detection problems to graph optimization, suggesting that the hardness of the latter is intrinsically linked to the former.

Note: The authors acknowledge that some proof arguments were developed through iterative discussions with AI tools (OpenAI's ChatGPT), specifically regarding the lower-bound argument for the tournament problem and graph-collision-based bounds, though the final constructions and proofs are the responsibility of the authors.

More like this