Evaluation of exponential sums and Riemann zeta function on quantum computer

• URL: http://arxiv.org/abs/2002.11094v1
• Date: Tue, 25 Feb 2020 18:45:40 GMT
• Title: Evaluation of exponential sums and Riemann zeta function on quantum computer
• Authors: Sandeep Tyagi
• Abstract summary: We show that exponential sums (ES) of the form beginequation* S(f, N)= sum_k=0N-1 sqrtw_k e2 pi i f(k), endequation* can be efficiently carried out with a quantum computer (QC) We present alternative methods to find $lvert S(f,N) rvert$ on a QC directly.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We show that exponential sums (ES) of the form \begin{equation*} S(f, N)= \sum_{k=0}^{N-1} \sqrt{w_k} e^{2 \pi i f(k)}, \end{equation*} can be efficiently carried out with a quantum computer (QC). Here $N$ can be exponentially large, $w_k$ are real numbers such that sum $S_w(M)=\sum_{k=0}^{M-1} w_k$ can be calculated in a closed form for any $M$, $S_w(N)=1$ and $f(x)$ is a real function, that is assumed to be easily implementable on a QC. As an application of the technique, we show that Riemann zeta (RZ) function, $\zeta(\sigma+ i t)$ in the critical strip, $\{0 \le \sigma <1, t \in \mathbb{R} \}$, can be obtained in polyLog(t) time. In another setting, we show that RZ function can be obtained with a scaling $t^{1/D}$, where $D \ge 2$ is any integer. These methods provide a vast improvement over the best known classical algorithms; best of which is known to scale as $t^{4/13}$. We present alternative methods to find $\lvert S(f,N) \rvert$ on a QC directly. This method relies on finding the magnitude $A=\lvert \sum_0^{N-1} a_k \rvert$ of a $n$-qubit quantum state with $a_k$ as amplitudes in the computational basis. We present two different ways to do obtain $A$. Finally, a brief discussion of phase/amplitude estimation methods is presented.

Related papers

• Efficient Continual Finite-Sum Minimization [52.5238287567572]
  We propose a key twist into the finite-sum minimization, dubbed as continual finite-sum minimization. Our approach significantly improves upon the $mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$ requires. We also prove that there is no natural first-order method with $mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$, establishing that the first-order complexity of our method is nearly tight.
  arXiv  Detail & Related papers  (2024-06-07T08:26:31Z)
• Variance-Reduced Fast Krasnoselkii-Mann Methods for Finite-Sum Root-Finding Problems [8.0153031008486]
  We propose a new class of fast Krasnoselkii--Mann methods with variance reduction to solve a finite-sum co-coercive equation $Gx = 0$. Our algorithm is single-loop and leverages a new family of unbiased variance-reduced estimators specifically designed for a wider class of root-finding algorithms. numerical experiments validate our algorithms and demonstrate their promising performance compared to state-of-the-art methods.
  arXiv  Detail & Related papers  (2024-06-04T15:23:29Z)
• Optimal Estimator for Linear Regression with Shuffled Labels [17.99906229036223]
  This paper considers the task of linear regression with shuffled labels. $mathbf Y in mathbb Rntimes m, mathbf Pi in mathbb Rntimes p, mathbf B in mathbb Rptimes m$, and $mathbf Win mathbb Rntimes m$, respectively.
  arXiv  Detail & Related papers  (2023-10-02T16:44:47Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  We introduce efficient $(1+varepsilon)$-approximation algorithms for the binary matrix factorization (BMF) problem. The goal is to approximate $mathbfA$ as a product of low-rank factors. Our techniques generalize to other common variants of the BMF problem.
  arXiv  Detail & Related papers  (2023-06-02T18:55:27Z)
• An Over-parameterized Exponential Regression [18.57735939471469]
  Recent developments in the field of Large Language Models (LLMs) have sparked interest in the use of exponential activation functions. We define the neural function $F: mathbbRd times m times mathbbRd times mathbbRd times mathbbRd times mathbbRd times mathbbRd times mathbbRd times mathbbRd
  arXiv  Detail & Related papers  (2023-03-29T07:29:07Z)
• $L^p$ sampling numbers for the Fourier-analytic Barron space [0.0]
  We study functions that can be written as [ f(x) = int_mathbbRd F(xi), e2 pi i langle x, xi rangle, d xi quad textwith quad int_mathbbRd |F(xi)| cdot (1 + |xi|)sigma, d xi infty. For $
  arXiv  Detail & Related papers  (2022-08-16T08:41:48Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations. The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
  arXiv  Detail & Related papers  (2022-06-17T17:55:43Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  We prove that any (deterministic or randomized) algorithm which learns $mathscrF_nd$ with $L$-accuracy $varepsilon$ requires at least $Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon) satisfies the two-sided estimate $$c (1-varepsilon)2dlog
  arXiv  Detail & Related papers  (2022-03-17T23:52:08Z)
• Unique Games hardness of Quantum Max-Cut, and a conjectured vector-valued Borell's inequality [6.621324975749854]
  We show that the noise stability of a function $f:mathbbRn to -1, 1$ is the expected value of $f(boldsymbolx) cdot f(boldsymboly)$. We conjecture that the expected value of $langle f(boldsymbolx), f(boldsymboly)rangle$ is minimized by the function $f(x) = x_leq k / Vert x_leq k /
  arXiv  Detail & Related papers  (2021-11-01T20:45:42Z)
• Random matrices in service of ML footprint: ternary random features with no performance loss [55.30329197651178]
  We show that the eigenspectrum of $bf K$ is independent of the distribution of the i.i.d. entries of $bf w$. We propose a novel random technique, called Ternary Random Feature (TRF) The computation of the proposed random features requires no multiplication and a factor of $b$ less bits for storage compared to classical random features.
  arXiv  Detail & Related papers  (2021-10-05T09:33:49Z)
• Spiked Covariance Estimation from Modulo-Reduced Measurements [14.569322713960494]
  We develop and analyze an algorithm that, for most directions $bfu$ and $nu=mathrmpoly(k)$, estimates $bfu$ to high accuracy using $n=mathrmpoly(k)$ measurements. Numerical experiments show that the developed algorithm performs well even in a non-asymptotic setting.
  arXiv  Detail & Related papers  (2021-10-04T02:10:47Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  Given an MDP with $S$ states, $A$ actions, the discount factor $gamma in (0,1)$, and an approximation threshold $epsilon > 0$, we provide a model-free algorithm to learn an $epsilon$-optimal policy. For small enough $epsilon$, we show an improved algorithm with sample complexity.
  arXiv  Detail & Related papers  (2020-06-06T13:34:41Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  We exploit the finite noise structure of finite sums to derive a matching $O(n2)$-upper bound under the global oracle model. Following a similar approach, we propose a novel adaptation of SVRG which is both emphcompatible with oracles, and achieves complexity bounds of $tildeO(n2+nsqrtL/mu)log (1/epsilon)$ and $O(nsqrtL/epsilon)$, for $mu>0$ and $mu=0$
  arXiv  Detail & Related papers  (2020-02-09T03:39:46Z)

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.