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
• Authors: Rahul Sarkar, Theodore J. Yoder
• 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

• 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.