Quantum algorithms for exponential sums and the evaluation of the Riemann zeta function

Abstract

We give quantum algorithms for estimating weighted exponential sums $S(f,w,N)={\sum }_{k=0}^{N-1}{w}_k{e}^{2\ddot{I}€if(k)}$, with $w_k\ge 0$, ${\sum }_k{w}_k=1$, and $N=2^n$ exponentially large. Under two explicit oracle assumptions -- efficiently computable prefix sums for the weights, enabling Grover--Rudolph state preparation, and a fixed-point circuit for $f$ -- amplitude estimation yields $S$ to additive error $\epsilon$ with $O({\epsilon }^{-1}\log (1/{\hat{I}}^3))$ oracle uses and $\mathrm{polylog}(N)$ gates per use; all bounds are full gate complexities, and the saving over classical sampling is quadratic in $1/\epsilon$. Applying this to the Riemann--Siegel formula, we prove that $\hat{I}\P (\ddot{I}ƒ+it)$ in the critical strip can be estimated to accuracy $\hat{I}´$ with $\tilde{O}(t^{(1-\ddot{I}ƒ)/2}\hat{I}{´}^{-1})$ gates, hence $\tilde{O}(t^{1/4}\hat{I}{´}^{-1})$ on the critical line, where $\tilde{O}$ suppresses factors polylogarithmic in $t/\hat{I}´$. At fixed accuracy this improves on the $t^{1/2}$ Riemann--Siegel cost and on the best rigorous classical algorithm's $t^{4/13+o(1)}$; the quantum algorithm is advantageous precisely when $\hat{I}´\gg t^{-3/52}$, which covers the accuracy needed to locate and count zeros. We show that a $\mathrm{polylog}(t)$ algorithm does not follow from these techniques -- undoing the normalization costs the ${\ell }^1$ mass ${\sum }_{k\le N}{k}^{-\ddot{I}ƒ}=\hat{I}˜(t^{(1-\ddot{I}ƒ)/2})$ of the main sum -- and that Hiary-type block decompositions cannot improve the quantum query complexity. We also give an estimator for the magnitude of the amplitude sum $|{\sum }_k{a}_k|$ of any efficiently preparable state, and review the required amplitude- and phase-estimation subroutines.

Topics & keywords