论文标题
量子计算机上指数和riemann zeta功能的评估
Evaluation of exponential sums and Riemann zeta function on quantum computer
论文作者
论文摘要
我们表明表单\ begin {equation*} s（f，n）= \ sum_ {k = 0}^{n-1} \ sqrt {w_k} e^{2πif（k）}，\ end End {equation*}的指数总和（e）在这里$ n $可以指数级大，$ w_k $是实数，使得可以以任何$ m $，$ s_w（n）= 1 $ f（x）$以封闭形式以封闭形式以封闭形式以封闭形式以封闭形式以封闭形式计算出来。作为该技术的应用，我们表明riemann zeta（rz）函数，$ζ（σ+ i t）$在关键带中，$ \ {0 \ leσ<1，t \ in \ mathbb {r} \} $可以在polog（t）时间中获得。在另一种环境中，我们显示可以通过缩放$ t^{1/d} $获得RZ函数，其中$ d \ ge 2 $是任何整数。这些方法对最知名的古典算法有了极大的改进。其中最好的据称是缩放为$ t^{4/13} $。我们提供了替代方法，可以直接在QC上找到$ \ lvert S（f，n）\ rvert $。此方法依赖于查找幅度$ a = \ lvert \ sum_0^{n-1} a_k \ rvert $ a $ n $ qubit量子状态，$ a_k $作为计算中的振幅。我们提出了两种获得$ a $的不同方法。最后，简要讨论了相/振幅估计方法。
We show that exponential sums (ES) of the form \begin{equation*} S(f, N)= \sum_{k=0}^{N-1} \sqrt{w_k} e^{2 π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, $ζ(σ+ i t)$ in the critical strip, $\{0 \le σ<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.
