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
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[polylog(nm)].