标题： 函数凸性的量子算法 显示英文标题

标题： Quantum Algorithm For Testing Convexity of Function

摘要： 函数是数学中的基本对象，在不同领域有着广泛的应用，通常根据其定义域和值域的某些性质进行分类。 一个实值函数的重要性质是它的凸性，在许多领域中起着非常关键的作用，例如热力学和几何学。 受量子计算最近进展以及追求量子优势的启发，我们提出了一种用于测试多项式函数凸性的量子算法，这些函数在多个上下文中经常出现，例如优化、机器学习、物理学等。 我们证明，与经典计算机相比，量子计算机可以以超多项式速度揭示凸性属性，相对于变量数量而言。 作为推论，我们在 Rebentrost 等人早期工作 [New J. Phys.\textbf{21}073023 (2019)] 中构建的量子牛顿法上提供了显著的改进和扩展。 我们进一步在更广泛的背景下讨论了我们的算法，例如在流形几何结构研究中的潜在应用，变分量子算法训练景观的测试，以及优化中的梯度下降/牛顿法。 显示英文摘要

摘要： Functions are a fundamental object in mathematics, with countless applications to different fields, and are usually classified based on certain properties, given their domains and images. An important property of a real-valued function is its convexity, which plays a very crucial role in many areas, such as thermodynamics and geometry. Motivated by recent advances in quantum computation as well as the quest for quantum advantage, we give a quantum algorithm for testing convexity of polynomial functions, which appears frequently in multiple contexts, such as optimization, machine learning, physics, etc. We show that quantum computers can reveal the convexity property superpolynomially faster than classical computers with respect to number of variables. As a corollary, we provide a significant improvement and extension on quantum Newton's method constructed in earlier work of Rebentrost et al [New J. Phys. \textbf{21} 073023 (2019)]. We further discuss our algorithm in a broader context, such as potential application in the study of geometric structure of manifold, testing training landscape of variational quantum algorithm and also gradient descent/Newton's method for optimization.