Quantum gradient algorithm for general polynomials
Quantum gradient algorithm for general polynomials
复制标题
一般多项式的量子梯度算法
DOI：
10.1103/physreva.103.042403
复制
发表时间：
2021-04-01
影响因子：
2.9
通讯作者：
Long, Guilu
中科院分区：
文献类型：
--
作者：
Gao, Pan;Li, Keren;Long, Guilu
基于遗传算法是解决优化问题的常用策略，是许多现代机器学习技术的基础。理论上，某些代价函数的极值点可以沿梯度方向沿着迭代地找到。计算$d$维问题的梯度所需的时间是$\mathcal{O}（poly（d））$的水平，这可以通过量子技术来提高，有利于高维数据处理，特别是优化参数数量以亿计的现代机器学习工程。在这里，我们提出了一个量子梯度算法优化一般多项式与dressed振幅编码，旨在解决快速收敛的多项式问题的时间和内存消耗在$\mathcal{O}（poly（\log{d}））$。此外，通过数值仿真，在考虑初始化、操作和截断过程中的噪声或扰动的情况下，对协议的性能进行了检验。对于高维优化中的势值，该量子梯度算法可以方便地进行多项式优化，可以作为未来实用量子计算机的子程序。
Gradient-based algorithms, popular strategies to optimization problems, are essential for many modern machine-learning techniques. Theoretically, extreme points of certain cost functions can be found iteratively along the directions of the gradient. The time required to calculating the gradient of $d$-dimensional problems is at a level of $\mathcal{O}(poly(d))$, which could be boosted by quantum techniques, benefiting the high-dimensional data processing, especially the modern machine-learning engineering with the number of optimized parameters being in billions. Here, we propose a quantum gradient algorithm for optimizing general polynomials with the dressed amplitude encoding, aiming at solving fast-convergence polynomials problems within both time and memory consumption in $\mathcal{O}(poly (\log{d}))$. Furthermore, numerical simulations are carried out to inspect the performance of this protocol by considering the noises or perturbations from initialization, operation and truncation. For the potential values in high-dimension optimizations, this quantum gradient algorithm is supposed to facilitate the polynomial-optimizations, being a subroutine for future practical quantum computer.