Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2303.03921 · Leibniz international proceedings in informatics

Approximate Degree Lower Bounds for Oracle Identification Problems

Mark Bun, Nadiia Voronova

Published Jan 1, 2023• 0 citations
arXivHTMLPDF

Abstract

The approximate degree of a Boolean function is the minimum degree of real polynomial that approximates it pointwise. For any Boolean function, its approximate degree serves as a lower bound on its quantum query complexity, and generically lifts to a quantum communication lower bound for a related function. We introduce a framework for proving approximate degree lower bounds for certain oracle identification problems, where the goal is to recover a hidden binary string $x \in \{0, 1\}^n$ given possibly non-standard oracle access to it. Our lower bounds apply to decision versions of these problems, where the goal is to compute the parity of $x$. We apply our framework to the ordered search and hidden string problems, proving nearly tight approximate degree lower bounds of $Ω(n/\log^2 n)$ for each. These lower bounds generalize to the weakly unbounded error setting, giving a new quantum query lower bound for the hidden string problem in this regime. Our lower bounds are driven by randomized communication upper bounds for the greater-than and equality functions.

DOI
10.4230/lipics.tqc.2023.1

Related papers

Algorithmic Polynomials

Alexander A. Sherstov

The approximate degree of a Boolean function $f(x_{1},x_{2},\ldots,x_{n})$ is the minimum degree of a real polynomial that approximates $f$ pointwise within $1/3$. Upper bounds on approximate degree have a variety of applications in learning theory, differential privacy, and algorithm design in general. Nearly all known upper bounds on approximate degree arise in an existential manner from bounds on quantum query complexity. We develop a first-principles, classical approach to the polynomial approximation of Boolean functions. We use it to give the first constructive upper bounds on the approximate degree of several fundamental problems: - $O\bigl(n^{\frac{3}{4}-\frac{1}{4(2^{k}-1)}}\bigr)$ for the $k$-element distinctness problem; - $O(n^{1-\frac{1}{k+1}})$ for the $k$-subset sum problem; - $O(n^{1-\frac{1}{k+1}})$ for any $k$-DNF or $k$-CNF formula; - $O(n^{3/4})$ for the surjectivity problem. In all cases, we obtain explicit, closed-form approximating polynomials that are unrelated to the quantum arguments from previous work. Our first three results match the bounds from quantum query complexity. Our fourth result improves polynomially on the $Θ(n)$ quantum query complexity of the problem and refutes the conjecture by several experts that surjectivity has approximate degree $Ω(n)$. In particular, we exhibit the first natural problem with a polynomial gap between approximate degree and quantum query complexity.

arXiv:1801.04607•Jan 14, 2018•0 citations

Algorithmic Polynomials

Alexander A. Sherstov

The approximate degree of a Boolean function $f(x_{1},x_{2},\ldots,x_{n})$ is the minimum degree of a real polynomial that approximates $f$ pointwise within $1/3$. Upper bounds on approximate degree have a variety of applications in learning theory, differential privacy, and algorithm design in general. Nearly all known upper bounds on approximate degree arise in an existential manner from bounds on quantum query complexity. We develop a novel, first-principles approach to the polynomial approximation of Boolean functions. We use it to give the first constructive upper bounds on the approximate degree of several fundamental problems: $O(n^{\frac{3}{4}-\frac{1}{4(2^{k}-1)}})$ for the $k$-element distinctness problem; $O(n^{1-\frac{1}{k+1}})$ for the $k$-subset sum problem; $O(n^{1-\frac{1}{k+1}})$ for any $k$-DNF or $k$-CNF formula; and $O(n^{3/4})$ for the surjectivity problem. In all cases, we obtain explicit, closed-form approximating polynomials that are unrelated to the quantum arguments from previous work. Our first three results match the bounds from quantum query complexity. Our fourth result improves polynomially on the $\Theta(n)$ quantum query complexity of the problem and refutes the conjecture by several experts that surjectivity has approximate degree $\Omega(n)$. In particular, we exhibit the first natural problem with a polynomial gap between approximate degree and quantum query complexity.

SIAM Journal on Computing•Jan 1, 2020•4 citations

A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$

Mark Bun, Justin Thaler

The approximate degree of a Boolean function $f \colon \{-1, 1\}^n \rightarrow \{-1, 1\}$ is the least degree of a real polynomial that approximates $f$ pointwise to error at most $1/3$. We introduce a generic method for increasing the approximate degree of a given function, while preserving its computability by constant-depth circuits. Specifically, we show how to transform any Boolean function $f$ with approximate degree $d$ into a function $F$ on $O(n \cdot \operatorname{polylog}(n))$ variables with approximate degree at least $D = Ω(n^{1/3} \cdot d^{2/3})$. In particular, if $d= n^{1-Ω(1)}$, then $D$ is polynomially larger than $d$. Moreover, if $f$ is computed by a polynomial-size Boolean circuit of constant depth, then so is $F$. By recursively applying our transformation, for any constant $δ> 0$ we exhibit an AC$^0$ function of approximate degree $Ω(n^{1-δ})$. This improves over the best previous lower bound of $Ω(n^{2/3})$ due to Aaronson and Shi (J. ACM 2004), and nearly matches the trivial upper bound of $n$ that holds for any function. Our lower bounds also apply to (quasipolynomial-size) DNFs of polylogarithmic width. We describe several applications of these results. We give: * For any constant $δ> 0$, an $Ω(n^{1-δ})$ lower bound on the quantum communication complexity of a function in AC$^0$. * A Boolean function $f$ with approximate degree at least $C(f)^{2-o(1)}$, where $C(f)$ is the certificate complexity of $f$. This separation is optimal up to the $o(1)$ term in the exponent. * Improved secret sharing schemes with reconstruction procedures in AC$^0$.

arXiv:1703.05784•Mar 16, 2017•0 citations

Classical Lower Bounds from Quantum Upper Bounds

Shalev Ben-David, Adam Bouland, Ankit Garg +1 more

We prove lower bounds on complexity measures, such as the approximate degree of a Boolean function and the approximate rank of a Boolean matrix, using quantum arguments. We prove these lower bounds using a quantum query algorithm for the combinatorial group testing problem. We show that for any function f, the approximate degree of computing the OR of n copies of f is Omega(sqrt n) times the approximate degree of f, which is optimal. No such general result was known prior to our work, and even the lower bound for the OR of ANDs function was only resolved in 2013. We then prove an analogous result in communication complexity, showing that the logarithm of the approximate rank (or more precisely, the approximate gamma-2 norm) of F: X x Y to 0,1 grows by a factor of Omega (sqrtn) when we take the OR of n copies of F, which is also essentially optimal. As a corollary, we give a new proof of Razborov's celebrated Omega(sqrtn) lower bound on the quantum communication complexity of the disjointness problem. Finally, we generalize both these results from composition with the OR function to composition with arbitrary symmetric functions, yielding nearly optimal lower bounds in this setting as well.

Annual Symposium on Foundations of Computer Science•Oct 1, 2018•9 citations

A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$

Mark Bun, Justin Thaler

The approximate degree of a Boolean function $f \colon \{-1, 1\}^n \rightarrow \{-1, 1\}$ is the least degree of a real polynomial that approximates $f$ pointwise to error at most 1/3. We introduce a generic method for increasing the approximate degree of a given function, while preserving its computability by constant-depth circuits. Specifically, we show how to transform any Boolean function $f$ with approximate degree $d$ into a function $F$ on $O(n \cdot \mathrm{polylog}(n))$ variables with approximate degree at least $D = \Omega(n^{1/3} \cdot d^{2/3})$. In particular, if $d= n^{1-\Omega(1)}$, then $D$ is polynomially larger than $d$. Moreover, if $f$ is computed by a polynomial-size Boolean circuit of constant depth, then so is $F$. By recursively applying our transformation, for any constant $\delta > 0$ we exhibit an AC$^0$ function of approximate degree $\Omega(n^{1-\delta})$. This improves upon the best previous lower bound of $\Omega(n^{2/3})$ due to Aaronson and Shi [ J. ACM, 51 (2004), pp. 595--605] and nearly matches the trivial upper bound of $n$ that holds for any function. Our lower bounds also apply to (quasipolynomial-size) disjunctive normal forms of polylogarithmic width. We describe several applications of these results and provide the following: (i) for any constant $\delta > 0$, an $\Omega(n^{1-\delta})$ lower bound on the quantum communication complexity of a function in AC$^0$; (ii) a Boolean function $f$ with approximate degree at least $C(f)^{2-o(1)}$, where $C(f)$ is the certificate complexity of $f$; this separation is optimal up to the $o(1)$ term in the exponent; (iii) improved secret sharing schemes with reconstruction procedures in AC$^0$.

SIAM Journal on Computing•Oct 22, 2019•6 citations

The polynomial method strikes back: tight quantum query bounds via dual polynomials

Mark Bun, Robin Kothari, Justin Thaler

The approximate degree of a Boolean function f is the least degree of a real polynomial that approximates f pointwise to error at most 1/3. The approximate degree of f is known to be a lower bound on the quantum query complexity of f (Beals et al., FOCS 1998 and J. ACM 2001).

arXiv:1710.09079•ACM Symposium on Theory of Computing (STOC)•Jun 20, 2018•39 citations
The approximate degree of a Boolean function is the minimum degree of real polynomial that approximates it pointwise. For any Boolean function, its approximate degree serves as a lower bound on its quantum query complexity, and generically lifts to a quantum communication lower bound for a related function. We introduce a framework for proving approximate degree lower bounds for certain oracle identification problems, where the goal is to recover a hidden binary string x∈{0,1}nx \in \{0, 1\}^nx∈{0,1}n given possibly non-standard oracle access to it. Our lower bounds apply to decision versions of these problems, where the goal is to compute the parity of xxx. We apply our framework to the ordered search and hidden string problems, proving nearly tight approximate degree lower bounds of Ω(n/log⁡2n)Ω(n/\log^2 n)Ω(n/log2n) for each. These lower bounds generalize to the weakly unbounded error setting, giving a new quantum query lower bound for the hidden string problem in this regime. Our lower bounds are driven by randomized communication upper bounds for the greater-than and equality functions.
The approximate degree of a Boolean function f(x1,x2,…,xn)f(x_{1},x_{2},\ldots,x_{n})f(x1​,x2​,…,xn​) is the minimum degree of a real polynomial that approximates fff pointwise within 1/31/31/3. Upper bounds on approximate degree have a variety of applications in learning theory, differential privacy, and algorithm design in general. Nearly all known upper bounds on approximate degree arise in an existential manner from bounds on quantum query complexity. We develop a first-principles, classical approach to the polynomial approximation of Boolean functions. We use it to give the first constructive upper bounds on the approximate degree of several fundamental problems: - O(n34−14(2k−1))O\bigl(n^{\frac{3}{4}-\frac{1}{4(2^{k}-1)}}\bigr)O(n43​−4(2k−1)1​) for the kkk-element distinctness problem; - O(n1−1k+1)O(n^{1-\frac{1}{k+1}})O(n1−k+11​) for the kkk-subset sum problem; - O(n1−1k+1)O(n^{1-\frac{1}{k+1}})O(n1−k+11​) for any kkk-DNF or kkk-CNF formula; - O(n3/4)O(n^{3/4})O(n3/4) for the surjectivity problem. In all cases, we obtain explicit, closed-form approximating polynomials that are unrelated to the quantum arguments from previous work. Our first three results match the bounds from quantum query complexity. Our fourth result improves polynomially on the Θ(n)Θ(n)Θ(n) quantum query complexity of the problem and refutes the conjecture by several experts that surjectivity has approximate degree Ω(n)Ω(n)Ω(n). In particular, we exhibit the first natural problem with a polynomial gap between approximate degree and quantum query complexity.
The approximate degree of a Boolean function f(x1,x2,…,xn)f(x_{1},x_{2},\ldots,x_{n})f(x1​,x2​,…,xn​) is the minimum degree of a real polynomial that approximates fff pointwise within 1/31/31/3. Upper bounds on approximate degree have a variety of applications in learning theory, differential privacy, and algorithm design in general. Nearly all known upper bounds on approximate degree arise in an existential manner from bounds on quantum query complexity. We develop a novel, first-principles approach to the polynomial approximation of Boolean functions. We use it to give the first constructive upper bounds on the approximate degree of several fundamental problems: O(n34−14(2k−1))O(n^{\frac{3}{4}-\frac{1}{4(2^{k}-1)}})O(n43​−4(2k−1)1​) for the kkk-element distinctness problem; O(n1−1k+1)O(n^{1-\frac{1}{k+1}})O(n1−k+11​) for the kkk-subset sum problem; O(n1−1k+1)O(n^{1-\frac{1}{k+1}})O(n1−k+11​) for any kkk-DNF or kkk-CNF formula; and O(n3/4)O(n^{3/4})O(n3/4) for the surjectivity problem. In all cases, we obtain explicit, closed-form approximating polynomials that are unrelated to the quantum arguments from previous work. Our first three results match the bounds from quantum query complexity. Our fourth result improves polynomially on the Θ(n)\Theta(n)Θ(n) quantum query complexity of the problem and refutes the conjecture by several experts that surjectivity has approximate degree Ω(n)\Omega(n)Ω(n). In particular, we exhibit the first natural problem with a polynomial gap between approximate degree and quantum query complexity.
A Nearly Optimal Lower Bound on the Approximate Degree of AC0^00
The approximate degree of a Boolean function f ⁣:{−1,1}n→{−1,1}f \colon \{-1, 1\}^n \rightarrow \{-1, 1\}f:{−1,1}n→{−1,1} is the least degree of a real polynomial that approximates fff pointwise to error at most 1/31/31/3. We introduce a generic method for increasing the approximate degree of a given function, while preserving its computability by constant-depth circuits. Specifically, we show how to transform any Boolean function fff with approximate degree ddd into a function FFF on O(n⋅polylog⁡(n))O(n \cdot \operatorname{polylog}(n))O(n⋅polylog(n)) variables with approximate degree at least D=Ω(n1/3⋅d2/3)D = Ω(n^{1/3} \cdot d^{2/3})D=Ω(n1/3⋅d2/3). In particular, if d=n1−Ω(1)d= n^{1-Ω(1)}d=n1−Ω(1), then DDD is polynomially larger than ddd. Moreover, if fff is computed by a polynomial-size Boolean circuit of constant depth, then so is FFF. By recursively applying our transformation, for any constant δ>0δ> 0δ>0 we exhibit an AC0^00 function of approximate degree Ω(n1−δ)Ω(n^{1-δ})Ω(n1−δ). This improves over the best previous lower bound of Ω(n2/3)Ω(n^{2/3})Ω(n2/3) due to Aaronson and Shi (J. ACM 2004), and nearly matches the trivial upper bound of nnn that holds for any function. Our lower bounds also apply to (quasipolynomial-size) DNFs of polylogarithmic width. We describe several applications of these results. We give: * For any constant δ>0δ> 0δ>0, an Ω(n1−δ)Ω(n^{1-δ})Ω(n1−δ) lower bound on the quantum communication complexity of a function in AC0^00. * A Boolean function fff with approximate degree at least C(f)2−o(1)C(f)^{2-o(1)}C(f)2−o(1), where C(f)C(f)C(f) is the certificate complexity of fff. This separation is optimal up to the o(1)o(1)o(1) term in the exponent. * Improved secret sharing schemes with reconstruction procedures in AC0^00.
We prove lower bounds on complexity measures, such as the approximate degree of a Boolean function and the approximate rank of a Boolean matrix, using quantum arguments. We prove these lower bounds using a quantum query algorithm for the combinatorial group testing problem. We show that for any function f, the approximate degree of computing the OR of n copies of f is Omega(sqrt n) times the approximate degree of f, which is optimal. No such general result was known prior to our work, and even the lower bound for the OR of ANDs function was only resolved in 2013. We then prove an analogous result in communication complexity, showing that the logarithm of the approximate rank (or more precisely, the approximate gamma-2 norm) of F: X x Y to 0,1 grows by a factor of Omega (sqrtn) when we take the OR of n copies of F, which is also essentially optimal. As a corollary, we give a new proof of Razborov's celebrated Omega(sqrtn) lower bound on the quantum communication complexity of the disjointness problem. Finally, we generalize both these results from composition with the OR function to composition with arbitrary symmetric functions, yielding nearly optimal lower bounds in this setting as well.
A Nearly Optimal Lower Bound on the Approximate Degree of AC0^00
The approximate degree of a Boolean function f ⁣:{−1,1}n→{−1,1}f \colon \{-1, 1\}^n \rightarrow \{-1, 1\}f:{−1,1}n→{−1,1} is the least degree of a real polynomial that approximates fff pointwise to error at most 1/3. We introduce a generic method for increasing the approximate degree of a given function, while preserving its computability by constant-depth circuits. Specifically, we show how to transform any Boolean function fff with approximate degree ddd into a function FFF on O(n⋅polylog(n))O(n \cdot \mathrm{polylog}(n))O(n⋅polylog(n)) variables with approximate degree at least D=Ω(n1/3⋅d2/3)D = \Omega(n^{1/3} \cdot d^{2/3})D=Ω(n1/3⋅d2/3). In particular, if d=n1−Ω(1)d= n^{1-\Omega(1)}d=n1−Ω(1), then DDD is polynomially larger than ddd. Moreover, if fff is computed by a polynomial-size Boolean circuit of constant depth, then so is FFF. By recursively applying our transformation, for any constant δ>0\delta > 0δ>0 we exhibit an AC0^00 function of approximate degree Ω(n1−δ)\Omega(n^{1-\delta})Ω(n1−δ). This improves upon the best previous lower bound of Ω(n2/3)\Omega(n^{2/3})Ω(n2/3) due to Aaronson and Shi [ J. ACM, 51 (2004), pp. 595--605] and nearly matches the trivial upper bound of nnn that holds for any function. Our lower bounds also apply to (quasipolynomial-size) disjunctive normal forms of polylogarithmic width. We describe several applications of these results and provide the following: (i) for any constant δ>0\delta > 0δ>0, an Ω(n1−δ)\Omega(n^{1-\delta})Ω(n1−δ) lower bound on the quantum communication complexity of a function in AC0^00; (ii) a Boolean function fff with approximate degree at least C(f)2−o(1)C(f)^{2-o(1)}C(f)2−o(1), where C(f)C(f)C(f) is the certificate complexity of fff; this separation is optimal up to the o(1)o(1)o(1) term in the exponent; (iii) improved secret sharing schemes with reconstruction procedures in AC0^00.