Rational degree is polynomially related to degree

arXiv:2601.08727 · cs.CC, cs.DM, quant-ph · Submitted 2026-01-13 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: Today's paper: "Rational degree is polynomially related to degree".

Mira: deg(f) ≤ Oe(rdeg(f) 3) for every Boolean function f, where deg(f) is the degree of f and rdeg(f) is the rational degree of f.

Kai: First, who's behind it and why it matters.

Title and authors: Kai: So, to recap, we're talking about "Rational degree is polynomially related to degree," and the authors are focusing on establishing that there's a polynomial relationship between the standard complexity measure of a Boolean function, deg(f), and its rational degree, rdeg(f).

Mira: They are doing this by defining and linking several other measures like sign degree and nondeterministic degree to create a path between these two concepts. It’s an effort to give us a more unified framework for understanding function complexity.

Lev: I'm still thinking about the practical side, Kai; if this relationship holds, does it mean we can predict the difficulty of implementing certain quantum algorithms based on just analyzing the function's rational degree?

Kai: They are trying to show that this relationship is robust and holds for every Boolean function, which means it’s not just an interesting case study but a general property of these functions.

Mira: The authors are using tools like Fact three which shows rdeg(f) equals the maximum of the nondeterministic degrees of f and its negation, to establish this fundamental link between them.

Lev: If we can rely on that identity, then our focus shifts to whether those other complexity measures they use—like block sensitivity—are actually computable or estimable in a realistic setting.

Kai: They are providing a set of lemmas that bridge these different measures together, showing how the relationships propagate and eventually lead to the main result in Theorem four.

Mira: It seems like they're building up the proof layer by layer, starting from definitions and moving towards the final polynomial bound on standard degree in terms of rational degree.

Lev: So, if we can trust this layered approach, then what’s the immediate implication for quantum error correction research right now? Does it give us any new tools?

Kai: It suggests a new way to characterize functions that might be hard for certain quantum algorithms because they have high rational degrees, which is something we need to know when designing robust systems.

Mira: That’s exactly the point; understanding the rational degree gives us a more precise algebraic tool than just looking at the standard degree alone.

The paper's summary: Kai: Moving on to the summary of "Rational degree is polynomially related to degree," it boils down to proving that deg(f) is bounded by a polynomial in rdeg(f), specifically they prove deg(f) ≤ Oe(rdeg(f) three), which resolves a major open problem.

Mira: That cubic relationship is the core finding; it means that the standard degree doesn't grow arbitrarily fast compared to the rational degree, which was previously unknown in this context.

Lev: A cubic bound is better than exponential growth, but we still need to consider what kind of physical resources that implies for running a quantum circuit on hardware.

Kai: The authors also show intermediate results, like deg(f) ≤ sixteen rdeg(f) four in Section three which serves as a stepping stone to prove the main result later on, showing how they build up the argument.

Mira: Those intermediate bounds are useful because they show the path of reasoning; they demonstrate precisely how the techniques used in that earlier section are necessary to achieve the stronger final bound.

Lev: If we can follow that path, then we can start thinking about what kind of overhead this implies for simulating a function with high rational degree on a quantum computer.

Kai: It suggests that if you have a function with high rational degree, you don't necessarily need an exponentially large classical representation to describe it; you can use one related polynomially.

Mira: That’s the big picture; it connects the algebraic structure of polynomials directly to the complexity of representing functions in a way that is relevant for quantum computation.

The paper's improvements: Kai: Now we look at what they suggest as improvements, and they move beyond just the initial cubic relationship to more refined bounds involving randomized certificate complexity and fractional block sensitivity.

Mira: They are introducing these new measures because they believe that these measures offer a finer granularity for analyzing the function's structure, allowing them to get closer to the true complexity of a specific task.

Lev: From an experimental perspective, if we can use those refined measures, does it mean we can design algorithms that are more resilient against noise than just relying on the initial cubic bound?

Kai: Yes, because Theorem six gives a tighter result: D(f) ≤ O rdeg(f) RC↓min(f) log n. That involves a potential function argument where the complexity measure drops by at least three-fourths every time you perform a query.

Mira: That potential function argument is crucial; it shows that the algorithm isn't just making progress in a linear fashion, but it’s showing an exponential decay in some sense over the course of its execution.

Lev: If we can get that kind of decay, then we could potentially run longer sequences of queries on a noisy machine and still maintain useful results before errors accumulate too much.

Kai: They also establish a lower bound on sign degree using minimum fractional block sensitivity in Theorem seven showing fbsmin(f) ≤ π2/two deg±(f)two which helps us constrain the complexity measures we've been tracking.

Mira: So, these improvements show that the relationship isn't just a one-size-fits-all cubic bound; there are structural variations that allow for even better analysis based on more detailed metrics.

Conclusion: Kai: Wrapping up this discussion on "Rational degree is polynomially related to degree," the paper shows that we have a solid polynomial relationship, deg(f) ≤ Oe(rdeg(f) three), and they’ve shown how to derive tighter bounds using refined complexity measures.

Mira: The main implication is that rational degree gives us an algebraic handle on postselected quantum query complexity, which is what PostQ0(f) actually equals, which links this abstract concept to a measurable quantity.

Lev: For my work, the practical implication is that knowing this relationship allows us to predict the query requirements for exact postselected algorithms with much greater accuracy than before.

Kai: Ultimately, the paper provides a framework for analyzing Boolean functions in terms of their rational degree, which has implications for how we think about learning and modeling data at scale.

Mira: It’s a powerful tool because it connects fundamental algebraic properties to complexity measures that are relevant across different areas of theoretical computer science.

Lev: I'm just glad we could talk through the details of this paper, because knowing what can be built is half the battle when you're designing experiments.

Robin Kothari, Matt Kovacs-Deak, Daochen Wang, Rain Zimin Yang

University of Maryland · University of British Columbia

cs.CC, cs.DM, quant-ph

Submitted: 2026-01-13

Updated: 2026-09-28

Comments: 28 pages; v2: added an author, improved main result; v3: added new result on approximate nondeterministic degree

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 87/100

The gist: deg(f) ≤ Oe(rdeg(f) 3) for every Boolean function f, where deg(f) is the degree of f and rdeg(f) is the rational degree of f.

Key concepts

Degree of a Boolean Function (deg(f))
This is the minimum degree of any polynomial 'r' such that when you evaluate 'r' on all possible inputs, the output exactly matches the function f. It measures how complex the function is in terms of polynomial representation.
Rational Degree (rdeg(f))
This measure is defined based on representing a Boolean function f as a fraction p/q. The rational degree is the minimum value of max(degree(p), degree(q)) required for such a representation. It captures the complexity when functions are viewed through rational expressions.
Nondeterministic Degree (ndeg(f))
This is a measure derived from polynomials that are non-zero only when the function f evaluates to one. The paper uses this concept, along with its counterpart for the negation of f, to define and relate the rational degree.
Decision Tree Complexity (D(f))
This complexity measure relates to how many queries are needed in a deterministic algorithm. The paper shows that D(f) can be bounded by a function of both the standard degree and the rational degree, providing an upper limit on query counts.

Terminology

Summary

deg(f) ≤ Oe(rdeg(f) 3) for every Boolean function f, where deg(f) is the degree of f and rdeg(f) is the rational degree of f.

The paper proves a polynomial relationship between the standard degree of a Boolean function and its rational degree, resolving an open problem concerning their complexity measures in quantum query complexity. This result establishes that rational degree can be polynomially related to standard degree, which has implications for understanding various complexity measures and provides bounds on deterministic query algorithms for Boolean functions.

Definitions and Relationships

The paper first defines the two key measures: the degree of a Boolean function, deg(f), as the minimum value of deg(r) such that f = r on all inputs; and the rational degree, rdeg(f), as the minimum value of max(deg(p), deg(q)) such that f = p/q on all inputs. The relationship is established by noting that rdeg(f) ≤ deg(f). Furthermore, the paper introduces related measures: sign degree (deg±(f)), defined via polynomials agreeing in sign with (-1)f, and nondeterministic degree (ndeg(f)), defined via polynomials that are non-zero exactly when f is one. A crucial identity is presented as Fact 3: rdeg(f) = max(ndeg(f), ndeg(¬f)).

Key Techniques for the Proof

The proof relies on relating rational degree to other complexity measures, specifically nondeterministic degrees. The paper utilizes three complexity measures: block sensitivity (bsx(f)), hitting set size, and decision tree complexity (D(f)). A central tool is a characterization of rational degree in terms of nondeterministic degrees: Fact 3 shows that rdeg(f) = max(ndeg(f), ndeg(¬f)). The proof then proceeds by relating these measures through several lemmas. For instance, Lemma 2 establishes the relationship deg±(f)/2 ≤ rdeg(f).

The Main Result and Algorithm Construction

The main result is proven in Theorem 4, which states that D(f) ≤ 4 deg±(f)2rdeg(f)2, or equivalently D(f) ≤ Oe(rdeg(f)3). This upper bound is achieved by constructing a deterministic query algorithm (Algorithm 1). This algorithm iteratively queries a hitting set of either the nondeterministic representation of f or its negation ¬f, based on which polynomial has the lower degree at each step. The total number of queries is bounded by 4 deg±(f)2rdeg(f)2.

Advanced Complexity Measures and Tight Bounds

The paper explores more refined complexity measures to improve the bound. It introduces randomized certificate complexity (RCx(f)) and fractional block sensitivity (fbsx(f)). A key result is Theorem 6, which provides a tighter bound: D(f) ≤ O rdeg(f) RC↓min(f) log n. This involves a potential function argument (Lemma 6), which shows that the complexity measure decreases by at least 3/4 at each step of the algorithm. The paper also establishes a lower bound on sign degree using minimum fractional block sensitivity, Theorem 7, showing fbsmin(f) ≤ π2/2 deg±(f)2.

Implications and Open Problems

The work concludes by framing the result as an effective Hypercube Nullstellensatz (Theorem 10), which provides a polynomial bound on the degrees of polynomials used in a specific algebraic identity. The paper also discusses implications for other complexity measures, such as influence (Inf[f]), showing that rdeg(f) ≥ Ω(log n) for functions depending on all variables. Finally, it conjectures that there exists a family of Boolean functions where D(f) ≥ Ω(rdeg(f)3), suggesting the current bound is asymptotically tight up to a log n factor. The appendix further shows that rational degree exactly equals the zero-error postselected quantum query complexity, PostQ0(f).

The gist

deg(f) ≤ Oe(rdeg(f) 3) for every Boolean function f, where deg(f) is the degree of f and rdeg(f) is the rational degree of f.

How it works

  1. The proof relates rational degree to nondeterministic degrees via Fact 3: rdeg(f) = max(ndeg(f), ndeg(¬f)).

  2. Theorem 4 provides the main upper bound D(f) ≤ 4 deg±(f)2rdeg(f)2, achieved by a deterministic query algorithm (Algorithm 1).

  3. The proof utilizes complexity measures like block sensitivity and hitting sets to relate the degree bounds to these measures (Lemma 2 and Lemma 3).

Improvements for AI systems

Based on the provided research paper, here are specific improvements for AI systems that leverage these theoretical results:

The core contribution of this paper is establishing a tight polynomial relationship between classical Boolean function degree, rational degree, and various quantum complexity measures (like exact postselected quantum query complexity). This suggests new avenues for analyzing the computational hardness and query requirements of learning algorithms.

Here are specific improvements categorized by application:

  1. Ablation/Model Selection in Learning Algorithms

  2. Query Complexity Analysis for Oracle-Based Learning

  3. Certificate-Based Verification and Robustness

  4. Quantum Machine Learning (QML) Model Design

The improved AI system, built upon these insights, would be capable of performing the following specific tasks:

  1. Ablation/Model Selection in Learning Algorithms: The system could use the established polynomial bounds (e.g., Theorem 8: Degree(f) ≤ O(rdeg(f)3)) to dynamically select the most efficient model complexity for a learning task (e.g., classification or regression). If a problem is known to have high rational degree, the system can immediately infer that a simple real polynomial representation is insufficient, prompting it to use more complex, non-linear representations or higher-order neural network architectures.

  2. Query Complexity Analysis for Oracle-Based Learning: The system could rigorously bound the number of queries required by an algorithm learning a Boolean function from an oracle. By relating the classical degree to the rational degree (Theorem 8), it can provide tighter, more accurate query complexity bounds than those based solely on standard polynomial degree measures. For instance, if the problem structure implies a high rational degree, the system can predict that exact postselected quantum query algorithms will require significantly more queries than classical polynomial algorithms.

  3. Certificate-Based Verification and Robustness: The system could utilize the connection between deterministic query complexity and certificate complexity (Theorem 4: D(f) ≤ O(rdeg(f)3)). This allows for the design of verification protocols where the number of queries is bounded not just by the function's intrinsic degree, but by a measure related to its structural sensitivity (like sign degree). This would lead to more robust and query-efficient verification methods for complex decision boundaries.

  4. Quantum Machine Learning (QML) Model Design: The system can use the result that rational degree characterizes exact postselected quantum query complexity (Fact 4). This allows the system to design QML circuits or quantum circuits for specific tasks where postselection is key, by directly targeting a desired rational degree bound. Instead of searching through general quantum circuit spaces, it can use this algebraic property to prune the search space and find an optimal quantum model that meets a required complexity target (e.g., finding the minimum number of queries needed for exact postselection on a specific dataset).

Sources

Related papers