Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Science China Physics Mechanics and Astronomy

Exponential speedup of quantum newton optimization algorithm for general polynomials

Heng Fan

Published Aug 27, 2021• 3 citations
Publisher
DOI
10.1007/s11433-021-1769-1

Related papers

Quantum second-order optimization algorithm for general polynomials

Pan Gao, Keren Li, Shijie Wei +1 more

Science China Physics Mechanics and Astronomy•Sep 2, 2021•25 citations

Quantum-classical truncated Newton method for high-dimensional energy landscapes

Leonard Wossnig, Sebastian Tschiatschek, Stefan Zohren

We develop a quantum-classical hybrid algorithm for function optimization that is particularly useful in the training of neural networks since it makes use of particular aspects of high-dimensional energy landscapes. Due to a recent formulation of semi-supervised learning as an optimization problem, the algorithm can further be used to find the optimal model parameters for deep generative models. In particular, we present a truncated saddle-free Newton's method based on recent insight from optimization, analysis of deep neural networks and random matrix theory. By combining these with the specific quantum subroutines we are able to exhaust quantum computing in order to arrive at a new quantum-classical hybrid algorithm design. Our algorithm is expected to perform at least as well as existing classical algorithms while achieving a polynomial speedup. The speedup is limited by the required classical read-out. Omitting this requirement can in theory lead to an exponential speedup.

arXiv:1710.07063•Oct 19, 2017•2 citations

Exponential Quantum Speedup in Simulating Coupled Classical Oscillators

Ryan Babbush, Dominic William Berry, Robin Kothari +2 more

We present a quantum algorithm for simulating the classical dynamics of 2 n coupled oscillators (e.g., 2 n masses coupled by springs).Our approach leverages a mapping between the Schrödinger equation and Newton's equation for harmonic potentials such that the amplitudes of the evolved quantum state encode the momenta and displacements of the classical oscillators.When individual masses and spring constants can be efficiently queried, and when the initial state can be efficiently prepared, the complexity of our quantum algorithm is polynomial in n, almost linear in the evolution time, and sublinear in the sparsity.As an example application, we apply our quantum algorithm to efficiently estimate the kinetic energy of an oscillator at any time.We show that any classical algorithm solving this same problem is inefficient and must make 2 ΩðnÞ queries to the oracle, and when the oracles are instantiated by efficient quantum circuits, the problem is bounded-error quantum polynomial time complete.Thus, our approach solves a potentially practical application with an exponential speedup over classical computers.Finally, we show that under similar conditions our approach can efficiently simulate more general classical harmonic systems with 2 n modes.

arXiv:2303.13012•Physical Review X•Dec 4, 2023•104 citations

Robust Polynomials and Quantum Algorithms

Harry Buhrman, Ilan Newman, Hein Röhrig +1 more

Lecture notes in computer science•Jan 1, 2005•16 citations

Improved quantum algorithm for A-optimal projection

Shi‐Jie Pan, Lin‐Chun Wan, Hailing Liu +4 more

Dimensionality reduction algorithms, which reduce the dimensionality of a given data set whereas preserving the information of the original data set as well as possible, play an important role in machine learning and data mining. Duan et al. proposed a quantum version of the A-optimal projection algorithm (AOP) for dimensionality reduction [Phys. Rev. A 99, 032311 (2019)] and claimed that the algorithm has exponential speedups on the dimensionality of the original feature space $n$ and the dimensionality of the reduced feature space $k$ over the classical algorithm. In this paper, we correct the time complexity of the algorithm of Duan et al. to $O\left[\frac{{\ensuremath{\kappa}}^{4s}\sqrt{{k}^{s}}}{{\ensuremath{\epsilon}}^{s}}{\mathrm{polylog}}^{s}\left(\frac{mn}{\ensuremath{\epsilon}}\right)\right]$, where $\ensuremath{\kappa}$ is the condition number of a matrix that related to the original data set, $s$ is the number of iterations, $m$ is the number of data points, and $\ensuremath{\epsilon}$ is the desired precision of the output state. Since the time complexity has an exponential dependence on $s$, the quantum algorithm can only be beneficial for high-dimensional problems with a small number of iterations $s$. To get a further speedup, we propose an improved quantum AOP algorithm with time complexity $O\left[\frac{s{\ensuremath{\kappa}}^{6}\sqrt{k}}{\ensuremath{\epsilon}}\mathrm{polylog}\left(\frac{nm}{\ensuremath{\epsilon}}\right)+\frac{{s}^{2}{\ensuremath{\kappa}}^{4}}{\ensuremath{\epsilon}}\mathrm{polylog}\left(\frac{\ensuremath{\kappa}k}{\ensuremath{\epsilon}}\right)\right]$ and space complexity $O[{log}_{2}(nk/\ensuremath{\epsilon})+s]$. With space complexity slightly worse, our algorithm achieves, at least, a polynomial speedup compared to the algorithm of Duan et al.. Also, our algorithm shows exponential speedups in $n$ and $m$ compared with the classical algorithm when $\ensuremath{\kappa},\phantom{\rule{0.28em}{0ex}}k$, and $1/\ensuremath{\epsilon}$ are $O[\mathrm{polylog}(nm)]$.

arXiv:2006.05745•Physical Review A•Nov 4, 2020•42 citations

On zeros of exponential polynomials and quantum algorithms

Yoshitaka Sasaki

arXiv:0908.1657•Quantum Information Processing•Oct 21, 2009•4 citations
We develop a quantum-classical hybrid algorithm for function optimization that is particularly useful in the training of neural networks since it makes use of particular aspects of high-dimensional energy landscapes. Due to a recent formulation of semi-supervised learning as an optimization problem, the algorithm can further be used to find the optimal model parameters for deep generative models. In particular, we present a truncated saddle-free Newton's method based on recent insight from optimization, analysis of deep neural networks and random matrix theory. By combining these with the specific quantum subroutines we are able to exhaust quantum computing in order to arrive at a new quantum-classical hybrid algorithm design. Our algorithm is expected to perform at least as well as existing classical algorithms while achieving a polynomial speedup. The speedup is limited by the required classical read-out. Omitting this requirement can in theory lead to an exponential speedup.
We present a quantum algorithm for simulating the classical dynamics of 2 n coupled oscillators (e.g., 2 n masses coupled by springs).Our approach leverages a mapping between the Schrödinger equation and Newton's equation for harmonic potentials such that the amplitudes of the evolved quantum state encode the momenta and displacements of the classical oscillators.When individual masses and spring constants can be efficiently queried, and when the initial state can be efficiently prepared, the complexity of our quantum algorithm is polynomial in n, almost linear in the evolution time, and sublinear in the sparsity.As an example application, we apply our quantum algorithm to efficiently estimate the kinetic energy of an oscillator at any time.We show that any classical algorithm solving this same problem is inefficient and must make 2 ΩðnÞ queries to the oracle, and when the oracles are instantiated by efficient quantum circuits, the problem is bounded-error quantum polynomial time complete.Thus, our approach solves a potentially practical application with an exponential speedup over classical computers.Finally, we show that under similar conditions our approach can efficiently simulate more general classical harmonic systems with 2 n modes.
Dimensionality reduction algorithms, which reduce the dimensionality of a given data set whereas preserving the information of the original data set as well as possible, play an important role in machine learning and data mining. Duan et al. proposed a quantum version of the A-optimal projection algorithm (AOP) for dimensionality reduction [Phys. Rev. A 99, 032311 (2019)] and claimed that the algorithm has exponential speedups on the dimensionality of the original feature space nnn and the dimensionality of the reduced feature space kkk over the classical algorithm. In this paper, we correct the time complexity of the algorithm of Duan et al. to $O\left[\frac{{\ensuremath{\kappa}}^{4s}\sqrt{{k}^{s}}}{{\ensuremath{\epsilon}}^{s}}{\mathrm{polylog}}^{s}\left(\frac{mn}{\ensuremath{\epsilon}}\right)\right]$, where $\ensuremath{\kappa}$ is the condition number of a matrix that related to the original data set, sss is the number of iterations, mmm is the number of data points, and $\ensuremath{\epsilon}$ is the desired precision of the output state. Since the time complexity has an exponential dependence on sss, the quantum algorithm can only be beneficial for high-dimensional problems with a small number of iterations sss. To get a further speedup, we propose an improved quantum AOP algorithm with time complexity $O\left[\frac{s{\ensuremath{\kappa}}^{6}\sqrt{k}}{\ensuremath{\epsilon}}\mathrm{polylog}\left(\frac{nm}{\ensuremath{\epsilon}}\right)+\frac{{s}^{2}{\ensuremath{\kappa}}^{4}}{\ensuremath{\epsilon}}\mathrm{polylog}\left(\frac{\ensuremath{\kappa}k}{\ensuremath{\epsilon}}\right)\right]$ and space complexity $O[{log}_{2}(nk/\ensuremath{\epsilon})+s]$. With space complexity slightly worse, our algorithm achieves, at least, a polynomial speedup compared to the algorithm of Duan et al.. Also, our algorithm shows exponential speedups in nnn and mmm compared with the classical algorithm when $\ensuremath{\kappa},\phantom{\rule{0.28em}{0ex}}k$, and $1/\ensuremath{\epsilon}$ are O[polylog(nm)]O[\mathrm{polylog}(nm)]O[polylog(nm)].