论文标题
量子Legendre-Fenchel变换
Quantum Legendre-Fenchel Transform
论文作者
论文摘要
我们提出了一种量子算法来计算离散的Legendre-Fenchel变换。给定对以$ n $点评估的凸函数的访问，该算法对其相应的离散Legendre-fenchel变换输出了量子力学表示，在转换空间中评估了$ k $点。对于固定的双重空间，预期的运行时间尺度为$ O（\sqrtκ\，\ m artrm {polylog}（n，k））$，其中$κ$是函数的条件数。如果双重空间的离散化使用等于$ n $的$ K $自适应地选择，则运行时间将减少到$ O（\ Mathrm {polylog}（n））$。我们解释了如何将提出的算法扩展到多元设置，并证明查询复杂性的下限，这表明我们的量子算法是最佳的polygarogarithmic因子。对于具有$κ= 1 $的多元函数，量子算法计算Legendre-Fenchel变换的量子力学表示，$ K $点的速度比任何经典算法都可以更快地计算。
We present a quantum algorithm to compute the discrete Legendre-Fenchel transform. Given access to a convex function evaluated at $N$ points, the algorithm outputs a quantum-mechanical representation of its corresponding discrete Legendre-Fenchel transform evaluated at $K$ points in the transformed space. For a fixed regular discretization of the dual space the expected running time scales as $O(\sqrtκ\,\mathrm{polylog}(N,K))$, where $κ$ is the condition number of the function. If the discretization of the dual space is chosen adaptively with $K$ equal to $N$, the running time reduces to $O(\mathrm{polylog}(N))$. We explain how to extend the presented algorithm to the multivariate setting and prove lower bounds for the query complexity, showing that our quantum algorithm is optimal up to polylogarithmic factors. For multivariate functions with $κ=1$, the quantum algorithm computes a quantum-mechanical representation of the Legendre-Fenchel transform at $K$ points exponentially faster than any classical algorithm can compute it at a single point.
