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

Springer eBooks

Polynomial Approximations

Osama M. Raisuddin, Suvranu De

Published Nov 14, 2025• 0 citations
Publisher
DOI
10.1007/978-3-032-03325-3_2

Related papers

On Polynomial Approximations to AC 0 .

Srikanth Srinivasan

Electronic colloquium on computational complexity•Jan 1, 2016•0 citations

Deterministic Approximate Counting for Degree-222 Polynomial Threshold Functions

De, Anindya, Diakonikolas, Ilias, Rocco A. Servedio

We give a {\em deterministic} algorithm for approximately computing the fraction of Boolean assignments that satisfy a degree-$2$ polynomial threshold function. Given a degree-2 input polynomial $p(x_1,\dots,x_n)$ and a parameter $\eps > 0$, the algorithm approximates \[ \Pr_{x \sim \{-1,1\}^n}[p(x) \geq 0] \] to within an additive $\pm \eps$ in time $\poly(n,2^{\poly(1/\eps)})$. Note that it is NP-hard to determine whether the above probability is nonzero, so any sort of multiplicative approximation is almost certainly impossible even for efficient randomized algorithms. This is the first deterministic algorithm for this counting problem in which the running time is polynomial in $n$ for $\eps= o(1)$. For "regular" polynomials $p$ (those in which no individual variable's influence is large compared to the sum of all $n$ variable influences) our algorithm runs in $\poly(n,1/\eps)$ time. The algorithm also runs in $\poly(n,1/\eps)$ time to approximate $\Pr_{x \sim N(0,1)^n}[p(x) \geq 0]$ to within an additive $\pm \eps$, for any degree-2 polynomial $p$. As an application of our counting result, we give a deterministic FPT multiplicative $(1 \pm \eps)$-approximation algorithm to approximate the $k$-th absolute moment $\E_{x \sim \{-1,1\}^n}[|p(x)^k|]$ of a degree-2 polynomial. The algorithm's running time is of the form $\poly(n) \cdot f(k,1/\eps)$.

arXiv:1311.7105•Nov 27, 2013•5 citations

Approximation Methods

Bruce Cameron Reed

Springer eBooks•Jan 1, 2022•0 citations

Approximation Methods

K. Tamvakis

Undergraduate texts in physics•Jan 1, 2019•0 citations

Quadratically Shallow Quantum Circuits for Hamiltonian Functions

Park, Youngjun, Min-Sung Kang, Chae-Yeun Park +1 more

Many quantum algorithms for ground-state preparation and energy estimation require the implementation of high-degree polynomials of a Hamiltonian to achieve better convergence rates. Their circuit implementation typically relies on quantum signal processing (QSP), whose circuit depth is proportional to the degree of the polynomial. Previous studies exploit the Chebyshev polynomial approximation, which requires a Chebyshev series of degree $O(\sqrt{n\ln(1/δ)})$ for an $n$-degree polynomial, where $δ$ is the approximation error. However, the approximation is limited to only a few functions, including monomials, truncated exponential, Gaussian, and error functions. In this work, we present the most generalized function approximation methods for $δ$-approximating linear combinations or products of polynomial-approximable functions with quadratically reduced-degree polynomials. We extend the list of polynomial-approximable functions by showing that the functions of cosine and sine can also be $δ$-approximated by quadratically reduced-degree Laurent polynomials. We demonstrate that various Hamiltonian functions for quantum ground-state preparation and energy estimation can be implemented with quadratically shallow circuits.

arXiv:2510.04059•Oct 5, 2025•1 citation

A Dual Polynomial for OR

Robert Špalek

We reprove that the approximate degree of the OR function on n bits is Omega(sqrt(n)). We consider a linear program which is feasible if and only if there is an approximate polynomial for a given function, and apply the duality theory. The duality theory says that the primal program has no solution if and only if its dual has a solution. Therefore one can prove the nonexistence of an approximate polynomial by exhibiting a dual solution, coined the dual polynomial. We construct such a polynomial.

arXiv:0803.4516•Mar 31, 2008•37 citations
We give a {\em deterministic} algorithm for approximately computing the fraction of Boolean assignments that satisfy a degree-222 polynomial threshold function. Given a degree-2 input polynomial p(x1,…,xn)p(x_1,\dots,x_n)p(x1​,…,xn​) and a parameter $\eps > 0$, the algorithm approximates Pr⁡x∼{−1,1}n[p(x)≥0] \Pr_{x \sim \{-1,1\}^n}[p(x) \geq 0] Prx∼{−1,1}n​[p(x)≥0] to within an additive $\pm \eps$ in time $\poly(n,2^{\poly(1/\eps)})$. Note that it is NP-hard to determine whether the above probability is nonzero, so any sort of multiplicative approximation is almost certainly impossible even for efficient randomized algorithms. This is the first deterministic algorithm for this counting problem in which the running time is polynomial in nnn for $\eps= o(1)$. For "regular" polynomials ppp (those in which no individual variable's influence is large compared to the sum of all nnn variable influences) our algorithm runs in $\poly(n,1/\eps)$ time. The algorithm also runs in $\poly(n,1/\eps)$ time to approximate Pr⁡x∼N(0,1)n[p(x)≥0]\Pr_{x \sim N(0,1)^n}[p(x) \geq 0]Prx∼N(0,1)n​[p(x)≥0] to within an additive $\pm \eps$, for any degree-2 polynomial ppp. As an application of our counting result, we give a deterministic FPT multiplicative $(1 \pm \eps)$-approximation algorithm to approximate the kkk-th absolute moment $\E_{x \sim \{-1,1\}^n}[|p(x)^k|]$ of a degree-2 polynomial. The algorithm's running time is of the form $\poly(n) \cdot f(k,1/\eps)$.
Many quantum algorithms for ground-state preparation and energy estimation require the implementation of high-degree polynomials of a Hamiltonian to achieve better convergence rates. Their circuit implementation typically relies on quantum signal processing (QSP), whose circuit depth is proportional to the degree of the polynomial. Previous studies exploit the Chebyshev polynomial approximation, which requires a Chebyshev series of degree O(nln⁡(1/δ))O(\sqrt{n\ln(1/δ)})O(nln(1/δ)​) for an nnn-degree polynomial, where δδδ is the approximation error. However, the approximation is limited to only a few functions, including monomials, truncated exponential, Gaussian, and error functions. In this work, we present the most generalized function approximation methods for δδδ-approximating linear combinations or products of polynomial-approximable functions with quadratically reduced-degree polynomials. We extend the list of polynomial-approximable functions by showing that the functions of cosine and sine can also be δδδ-approximated by quadratically reduced-degree Laurent polynomials. We demonstrate that various Hamiltonian functions for quantum ground-state preparation and energy estimation can be implemented with quadratically shallow circuits.