Density theorems with applications in quantum signal processing

• URL: http://arxiv.org/abs/2111.07182v3
• Date: Thu, 7 Apr 2022 21:52:15 GMT
• Title: Density theorems with applications in quantum signal processing
• Abstract summary: We study the approximation capabilities of two families of univariates that arise in applications of quantum signal processing. We propose two subfamilies of monotone and non-monotone approximations. For the non-monotone case, under some additional assumptions, we provide an iterative algorithm that finds the optimal approximation.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We study the approximation capabilities of two families of univariate polynomials that arise in applications of quantum signal processing. Although approximation only in the domain $[0,1]$ is physically desired, these polynomial families are defined by bound constraints not just in $[0,1]$, but also with additional bound constraints outside $[0,1]$. One might wonder then if these additional constraints inhibit their approximation properties within $[0,1]$. The main result of this paper is that this is not the case -- the additional constraints do not hinder the ability of these polynomial families to approximate arbitrarily well any continuous function $f:[0,1] \rightarrow [0,1]$ in the supremum norm, provided $f$ also matches any polynomial in the family at $0$ and $1$. We additionally study the specific problem of approximating the step function on $[0,1]$ (with the step from $0$ to $1$ occurring at $x=\frac{1}{2}$) using one of these families, and propose two subfamilies of monotone and non-monotone approximations. For the non-monotone case, under some additional assumptions, we provide an iterative heuristic algorithm that finds the optimal polynomial approximation.

Related papers

• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  We study tradeoff between solution quality and stability when elements arrive over time.<n>Our algorithm has a future implementation for rational oracle$ with $O(varepsilon-1)$ recourse and separate the existence of universal-price certificates from their efficient algorithms.
  arXiv  Detail & Related papers  (2026-09-09T10:13:43Z)
• A solution to the Erdős Problem #1040 [0.0]
  We prove that $vartheta(K)$ for every closed infinite set $FsubsetmathbbC$ transfinite diameter at least one, answering the vanishing question in Erds Problem 1040.
  arXiv  Detail & Related papers  (2026-09-05T12:11:52Z)
• Algorithms with Polynomially-Improved Approximation Factors for the $2 \ ightarrow q$ Norm, and Applications [13.39372872460586]
  The $2 rightarrow q$ norm of a matrix $X in mathbbRn times d$ is defined as $lVert X rVert_2 rightarrow q = sup_lVert v rVert = 1 lVert Xv rVert_q$.<n>We show that a simple spectral algorithm can achieve an approximation factor better than $2sqrtlog n$, assuming the Exponential Time Hypothesis (FOCS'
  arXiv  Detail & Related papers  (2026-05-24T23:56:06Z)
• On the Approximate Non-Deterministic Degree of Total Boolean Functions [0.2864713389096699]
  approximate non-deterministic degree of a function $f$, $mathsfndeg_(f)$ (written $mathsfN_(f)$ for brevity)<n>The rational degree conjecture, open for over three decades, was recently resolved by Kothari, KovacsDeak, Wang, and Yang.
  arXiv  Detail & Related papers  (2026-05-22T07:52:09Z)
• A Note on Non-Negative $L_1$-Approximating Polynomials [10.871533496245716]
  We study the existence of textitnon-negative $L$-approximations with respect to Gaussian distributions.<n>These non-negative approxingimats have recently found uses in smoothed learning from positive-only examples.
  arXiv  Detail & Related papers  (2026-05-08T17:55:39Z)
• Spectrally Corrected Polynomial Approximation for Quantum Singular Value Transformation [0.0]
  We propose a spectral correction that exploits prior knowledge of $K$ eigenvalues of $bA$.<n>Experiments on the 1DSC equation demonstrate up to a $5times$ reduction in circuit depth relative to the base, at unit fidelity and improved compliance error.
  arXiv  Detail & Related papers  (2026-03-04T12:40:53Z)
• Covering a Few Submodular Constraints and Applications [1.649938899766112]
  We consider the problem of covering multiple submodular constraints.<n>For covering multiple submodular constraints we obtain a randomized bi-criteria approximation that for any given integer $alpha ge 1$ outputs a set $S$ such that $f_i(S) ge$ $(1-1/ealpha -epsilon)b_i$ for each $i in [r]$ and $mathbbE[c(S)] le (1+epsilon)alpha cdot sfOPT$.
  arXiv  Detail & Related papers  (2025-07-14T03:32:42Z)
• Guessing Efficiently for Constrained Subspace Approximation [49.83981776254246]
  We introduce a general framework for constrained subspace approximation. We show it provides new algorithms for partition-constrained subspace approximation with applications to $k$-means clustering, and projected non-negative matrix factorization.
  arXiv  Detail & Related papers  (2025-04-29T15:56:48Z)
• Low-degree approximation of QAC$^0$ circuits [0.0]
  We show that the parity function cannot be computed in QAC$0$. We also show that any QAC circuit of depth $d$ that approximately computes parity on $n$ bits requires $2widetildeOmega(n1/d)$.
  arXiv  Detail & Related papers  (2024-11-01T19:04:13Z)
• On Maximal Families of Binary Polynomials with Pairwise Linear Common Factors [1.249418440326334]
  We characterize maximal families over the binary field $mathbbF$. Our findings prompt several more open questions, which we plan to address in an extended version of this work.
  arXiv  Detail & Related papers  (2024-05-14T16:30:28Z)
• A polynomial quantum computing algorithm for solving the dualization problem [75.38606213726906]
  Given two monotone prime functions $f:0,1n to 0,1$ and $g:0,1n to 0,1$ the dualization problem consists in determining if $g$ is the dual of $f$. We present a quantum computing algorithm that solves the decision version of the dualization problem in time.
  arXiv  Detail & Related papers  (2023-08-28T18:12:54Z)
• The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
  For every $delta>0,$ we construct CNF and formulas of size with approximate degree $Omega(n1-delta),$ essentially matching the trivial upper bound of $n. We show that for every $delta>0$, these models require $Omega(n1-delta)$, $Omega(n/4kk2)1-delta$, and $Omega(n/4kk2)1-delta$, respectively.
  arXiv  Detail & Related papers  (2022-09-04T10:01:39Z)
• Shallow neural network representation of polynomials [91.3755431537592]
  We show that $d$-variables of degreeR$ can be represented on $[0,1]d$ as shallow neural networks of width $d+1+sum_r=2Rbinomr+d-1d-1d-1[binomr+d-1d-1d-1[binomr+d-1d-1d-1[binomr+d-1d-1d-1d-1[binomr+d-1d-1d-1d-1
  arXiv  Detail & Related papers  (2022-08-17T08:14:52Z)
• A general approximation lower bound in $L^p$ norm, with applications to feed-forward neural networks [0.0]
  We study the fundamental limits to the expressive power of neural networks. We first prove a general lower bound on how well functions in $F$ can be approximated in $Lp(mu)$ norm. We then instantiate this bound to the case where $G$ corresponds to a piecewise-polynomial feed-forward neural network.
  arXiv  Detail & Related papers  (2022-06-09T09:01:05Z)
• A Variational Quantum Algorithm For Approximating Convex Roofs [0.0]
  entanglement measures are first defined for pure states of a bipartite Hilbert space, and then extended to mixed states via the convex roof extension. We produce a sequence of extensions that we call $f$-$d$ extensions, for $d in mathbbN$. We introduce a quantum variational algorithm which aims to approximate the $f$-$d$ extensions of entanglement measures defined on pure states.
  arXiv  Detail & Related papers  (2022-03-04T02:30:35Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  One of its most powerful and successful modalities approximates every distribution to an $ell$ distance essentially at most a constant times larger than its closest $t$-piece degree-$d_$. We provide a method that estimates this number near-optimally, hence helps approach the best possible approximation.
  arXiv  Detail & Related papers  (2022-02-15T03:49:28Z)
• Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain [11.562923882714093]
  We study the problem of finding approximate first-order stationary points in optimization problems of the form $min_x in max_y in Y f(x,y) Our approach relies upon replacing the function $f(x,cdot)$ with its $kth order Taylor approximation (in $y$) and finding a near-stationary point in $Y$.
  arXiv  Detail & Related papers  (2021-10-08T07:46:18Z)
• Submodular + Concave [53.208470310734825]
  It has been well established that first order optimization methods can converge to the maximal objective value of concave functions. In this work, we initiate the determinant of the smooth functions convex body $$F(x) = G(x) +C(x)$. This class of functions is an extension of both concave and continuous DR-submodular functions for which no guarantee is known.
  arXiv  Detail & Related papers  (2021-06-09T01:59:55Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  We show that there exists an $epsilon$-cover for $S$ of cardinality $M = (k/epsilon)O_d(k1/d)$. Building on our structural result, we obtain significantly improved learning algorithms for several fundamental high-dimensional probabilistic models hidden variables.
  arXiv  Detail & Related papers  (2020-12-14T18:14:08Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.