Search

Discriminative Canonical Correlation Analysis (DCCA) is a powerful supervised feature extraction technique for two sets of multivariate data, which has wide applications in pattern recognition. DCCA consists of two parts: (i) mean-centering that subtracts the sample mean from the sample; (ii) solving the generalized eigenvalue problem. The cost of DCCA is expensive when dealing with a large number of high-dimensional samples. To solve this problem, here we propose a quantum DCCA algorithm. Specifically, we devise an efficient method to compute the mean of all samples, then use block-Hamiltonian simulation and quantum phase estimation to solve the generalized eigenvalue problem. Our algorithm achieves a polynomial speedup in the dimension of samples under certain conditions over its classical counterpart.

International audience; Matrices with the displacement structures of circulant, Toeplitz, and Hankel types as well as matrices with structures generalizing these types are omnipresent in computations of sciences and engineering. In this paper we present efficient and memory-reduced quantum algorithms for solving linear systems with such structures by devising an approach to implement the block-encodings of these structured matrices. More specifically, by decomposing n×n dense matrices into linear combinations of displacement matrices, we first deduce the parametrized representations of the matrices with displacement structures so that they can be treated similarly. With such representations, we then construct ε-approximate block-encodings of these structured matrices in two different data access models, i.e., the black-box model and the quantum random access memory (QRAM) data structure model. It is shown the quantum linear system solvers based on the proposed block-encodings provide a quadratic speedup with respect to the dimension over classical algorithms in the black-box model and an exponential speedup in the QRAM data structure model. In particular, these linear system solvers subsume known results with significant improvements and also can motivate new instances where there was no specialized quantum algorithm before. As an application, one of the quantum linear system solvers is applied to the linear prediction of time series, which justifies the claimed quantum speedup is achievable for problems of practical interest.

International audience; The Poisson equation has wide applications in many areas of science and engineering. Although there are some quantum algorithms that can efficiently solve the Poisson equation, they generally require a fault-tolerant quantum computer, which is beyond the current technology. We propose a variational quantum algorithm (VQA) to solve the Poisson equation, which can be executed on noisy intermediate-scale quantum devices. In detail, we first adopt the finite-difference method to transform the Poisson equation into a linear system. Then, according to the special structure of the linear system, we find an explicit tensor product decomposition, with only (2log2n+1) items, of its coefficient matrix under a specific set of simple operators, where n is the dimension of the coefficient matrix. This implies that the proposed VQA needs fewer quantum measurements, which dramatically reduces the required quantum resources. Additionally, we design observables to efficiently evaluate the expectation values of the simple operators on a quantum computer. Numerical experiments demonstrate that our algorithm can solve the Poisson equation.

Dimensionality reduction (DR) algorithms, which reduce the dimensionality of a given data set while preserving the information of the original data set as well as possible, play an important role in machine learning and data mining. Duan \emph{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 Duan \emph{et al}.'s algorithm to $O(\frac{\kappa^{4s}\sqrt{k^s}} {\epsilon^{s}}\mathrm{polylog}^s (\frac{mn}{\epsilon}))$, where $\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 $\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(\frac{s \kappa^6 \sqrt{k}}{\epsilon}\mathrm{polylog}(\frac{nm}{\epsilon}) + \frac{s^2 \kappa^4}{\epsilon}\mathrm{polylog}(\frac{\kappa k}{\epsilon}))$ and space complexity $O(\log_2(nk/\epsilon)+s)$. With space complexity slightly worse, our algorithm achieves at least a polynomial speedup compared to Duan \emph{et al}.'s algorithm. Also, our algorithm shows exponential speedups in $n$ and $m$ compared with the classical algorithm when both $\kappa$, $k$ and $1/\epsilon$ are $O(\mathrm{polylog}(nm))$., Comment: 11 pages, 2 figures