Quantum Gradient Algorithm for General Polynomials
- URL: http://arxiv.org/abs/2004.11086v1
- Date: Thu, 23 Apr 2020 11:28:45 GMT
- Title: Quantum Gradient Algorithm for General Polynomials
- Authors: Keren Li, Pan Gao, Shijie Wei, Jiancun Gao, Guilu Long
- Abstract summary: Gradient-based algorithms, popular strategies to optimization problems, are essential for many modern machine-learning techniques.
We propose a quantum gradient algorithm for optimizing numericals with the dressed amplitude.
For the potential values in high-dimension optimizations, this quantum algorithm is supposed to facilitate gradient-optimizations.
- Score: 5.008814514502094
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- 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.
Related papers
- Fast, Scalable, Warm-Start Semidefinite Programming with Spectral
Bundling and Sketching [53.91395791840179]
We present Unified Spectral Bundling with Sketching (USBS), a provably correct, fast and scalable algorithm for solving massive SDPs.
USBS provides a 500x speed-up over the state-of-the-art scalable SDP solver on an instance with over 2 billion decision variables.
arXiv Detail & Related papers (2023-12-19T02:27:22Z) - Pure Quantum Gradient Descent Algorithm and Full Quantum Variational
Eigensolver [0.7149735232319818]
gradient-based gradient descent algorithm is a widely adopted optimization method.
We propose a novel quantum-based gradient calculation method that requires only a single oracle calculation.
We successfully implemented the quantum gradient descent algorithm and applied it to the Variational Quantum Eigensolver (VQE)
arXiv Detail & Related papers (2023-05-07T05:52:41Z) - Stochastic optimization algorithms for quantum applications [0.0]
We review the use of first-order, second-order, and quantum natural gradient optimization methods, and propose new algorithms defined in the field of complex numbers.
The performance of all methods is evaluated by means of their application to variational quantum eigensolver, quantum control of quantum states, and quantum state estimation.
arXiv Detail & Related papers (2022-03-11T16:17:05Z) - Progress towards analytically optimal angles in quantum approximate
optimisation [0.0]
The Quantum Approximate optimisation algorithm is a $p$ layer, time-variable split operator method executed on a quantum processor.
We prove that optimal parameters for $p=1$ layer reduce to one free variable and in the thermodynamic limit, we recover optimal angles.
We moreover demonstrate that conditions for vanishing gradients of the overlap function share a similar form which leads to a linear relation between circuit parameters, independent on the number of qubits.
arXiv Detail & Related papers (2021-09-23T18:00:13Z) - Quadratic Unconstrained Binary Optimisation via Quantum-Inspired
Annealing [58.720142291102135]
We present a classical algorithm to find approximate solutions to instances of quadratic unconstrained binary optimisation.
We benchmark our approach for large scale problem instances with tuneable hardness and planted solutions.
arXiv Detail & Related papers (2021-08-18T09:26:17Z) - Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
We introduce a new variational quantum algorithm that benefits from two innovations: multi-basis graph complexity and nonlinear activation functions.
Our results in increased optimization performance, two increase in effective landscapes and a reduction in measurement progress.
arXiv Detail & Related papers (2021-06-24T20:16:02Z) - Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
We present a constructive algorithm for generating quantum circuits with time-independent depth.
We highlight our algorithm for special classes of models, including Anderson localization in one dimensional transverse field XY model.
In addition to providing exact circuits for a broad set of spin and fermionic models, our algorithm provides broad analytic and numerical insight into optimal Hamiltonian simulations.
arXiv Detail & Related papers (2021-04-01T19:06:00Z) - Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
Variisy hybrid quantum-classical algorithms are powerful tools to maximize the use of Noisy Intermediate Scale Quantum devices.
We propose a strategy for such ansatze used in variational quantum algorithms, which we call "Efficient Circuit Training" (PECT)
Instead of optimizing all of the ansatz parameters at once, PECT launches a sequence of variational algorithms.
arXiv Detail & Related papers (2020-10-01T18:14:11Z) - Quantum speedups of some general-purpose numerical optimisation
algorithms [0.03078691410268859]
We show that many techniques for global optimisation under a Lipschitz constraint can be accelerated near-quadratically.
Second, we show that backtracking line search, an ingredient in quasi-Newton optimisation algorithms, can be accelerated up to quadratically.
Third, we show that a component of the Nelder-Mead algorithm can be accelerated by up to a multiplicative factor of $O(sqrtn)$.
arXiv Detail & Related papers (2020-04-14T14:04:47Z) - Cross Entropy Hyperparameter Optimization for Constrained Problem
Hamiltonians Applied to QAOA [68.11912614360878]
Hybrid quantum-classical algorithms such as Quantum Approximate Optimization Algorithm (QAOA) are considered as one of the most encouraging approaches for taking advantage of near-term quantum computers in practical applications.
Such algorithms are usually implemented in a variational form, combining a classical optimization method with a quantum machine to find good solutions to an optimization problem.
In this study we apply a Cross-Entropy method to shape this landscape, which allows the classical parameter to find better parameters more easily and hence results in an improved performance.
arXiv Detail & Related papers (2020-03-11T13:52:41Z) - Efficient phase-factor evaluation in quantum signal processing [1.3614427997190908]
Quantum signal processing (QSP) is a powerful quantum algorithm to exactly implement matrixs on quantum computers.
There is so far no classically stable algorithm allowing computation of the phase factors that are needed to build QSP circuits.
We present here an optimization based method that can accurately compute the phase factors using standard double precision arithmetic operations.
arXiv Detail & Related papers (2020-02-26T17:23:55Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.