Quantum Gradient Algorithm for General Polynomials

Abstract

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.

(5+10)pages + (3+1) figures. Comments are always welcome

References in corpus (28)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum Machine Learning
• Elementary gates for quantum computation
• The density-matrix renormalization group in the age of matrix product states
• Quantum algorithm for solving linear systems of equations
• End to End Learning for Self-Driving Cars
• Solving the Quantum Many-Body Problem with Artificial Neural Networks
• Deep Learning Face Representation by Joint Identification-Verification
• Quantum principal component analysis
• Evaluating analytic gradients on quantum hardware
• Quantum random access memory
• Many-body quantum state tomography with neural networks
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Learning phase transitions by confusion
• Discovering Phase Transitions with Unsupervised Learning
• On the relationship between continuous- and discrete-time quantum walk
• Quantum Entanglement in Neural Network States
• Hamiltonian simulation with nearly optimal dependence on all parameters
• Architectures for a quantum random access memory
• Hybrid Quantum-Classical Approach to Quantum Optimal Control
• A quantum linear system algorithm for dense matrices
• Quantum Entanglement in Deep Learning Architectures
• Gradient Descent Finds Global Minima of Deep Neural Networks
• Quantum gradient descent for linear systems and least squares
• Fast quantum algorithm for numerical gradient estimation
• Optimizing quantum optimization algorithms via faster quantum gradient computation
• Insensitive Stochastic Gradient Twin Support Vector Machine for Large Scale Problems
• Gradient Descent based Optimization Algorithms for Deep Learning Models Training

Cited by in corpus (3)

• Quantum gradient descent algorithms for nonequilibrium steady states and linear algebraic systems
• Random coordinate descent: a simple alternative for optimizing parameterized quantum circuits
• Towards a NISQ Algorithm to Simulate Hermitian Matrix Exponentiation