As a general framework, matrix exponential dimensionality reduction (MEDR) deals with the small-sample-size problem that appears in linear dimensionality-reduction (DR) algorithms. High complexity is the bottleneck in this type of DR algorithm because one has to solve a large-scale matrix exponential generalized eigenproblem. To address it, here we design a general quantum algorithm framework for MEDR based on the block-encoding technique. This framework is configurable, that is, by selecting suitable methods to design the block encodings of the data matrices, a series of efficient quantum algorithms can be derived from this framework. Specifically, by constructing the block encodings of the data matrix exponentials, we solve the generalized eigenproblem and then obtain the digital-encoded quantum state corresponding to the compressed low-dimensional data set, which can be directly utilized as the input state for other quantum machine learning tasks to overcome the curse of dimensionality. As applications, we apply this framework to four linear DR algorithms and design their quantum algorithms, which all achieve a polynomial speedup in the dimension of the sample over their classical counterparts.
As a general framework, matrix exponential dimensionality reduction (MEDR) deals with the small-sample-size problem that appears in linear dimensionality-reduction (DR) algorithms. High complexity is the bottleneck in this type of DR algorithm because one has to solve a large-scale matrix exponential generalized eigenproblem. To address it, here we design a general quantum algorithm framework for MEDR based on the block-encoding technique. This framework is configurable, that is, by selecting suitable methods to design the block encodings of the data matrices, a series of efficient quantum algorithms can be derived from this framework. Specifically, by constructing the block encodings of the data matrix exponentials, we solve the generalized eigenproblem and then obtain the digital-encoded quantum state corresponding to the compressed low-dimensional data set, which can be directly utilized as the input state for other quantum machine learning tasks to overcome the curse of dimensionality. As applications, we apply this framework to four linear DR algorithms and design their quantum algorithms, which all achieve a polynomial speedup in the dimension of the sample over their classical counterparts.
As a general framework, Matrix Exponential Dimensionality Reduction (MEDR) deals with the small-sample-size problem that appears in linear Dimensionality Reduction (DR) algorithms. High complexity is the bottleneck in this type of DR algorithm because one has to solve a large-scale matrix exponential eigenproblem. To address it, here we design a general quantum algorithm framework for MEDR based on the block-encoding technique. This framework is configurable, that is, by selecting suitable methods to design the block-encodings of the data matrices, a series of new efficient quantum algorithms can be derived from this framework. Specifically, by constructing the block-encodings of the data matrix exponentials, we solve the eigenproblem and then obtain the digital-encoded quantum state corresponding to the compressed low-dimensional dataset, which can be directly utilized as input state for other quantum machine learning tasks to overcome the curse of dimensionality. As applications, we apply this framework to four linear DR algorithms and design their quantum algorithms, which all achieve a polynomial speedup in the dimension of the sample over their classical counterparts.
Abstract Dimensionality reduction (DR) techniques play an extremely critical role in the data mining and pattern recognition field. However, most DR approaches involve large-scale matrix computations, which cause too high running complexity to implement in the big data scenario efficiently. The recent developments in quantum information processing provide a novel path to alleviate this problem, where a potential quantum acceleration can be obtained comparing with the classical counterpart. Nevertheless, existing proposals for quantum DR methods faced the common dilemma of the nonlinear generalization owing to the intrinsic linear limitation of quantum computation. In this paper, an architecture to simulate the arbitrary nonlinear kernels on a universal quantum computer is illustrated and further propose the quantum kernel principal component analysis (QKPCA) algorithm. The key idea is employing the truncated Taylor expansion to approximate the arbitrary nonlinear kernel within the fixed error and then constructing the corresponding Hamiltonian simulation for the quantum phase estimation algorithm. It is demonstrated theoretically that the QKPCA is qualified for the nonlinear DR task while the exponential speedup is also maintained. In addition, this research has the potential ability to develop other quantum DR approaches and existing linear quantum machine learning models.
Abstract Data classification is a fundamental problem in machine learning. We study quantum speedup of the supervised data classification algorithms (quadratic, linear and naïve Bayes classifiers) based on Bayes’ theory. The main technique we use to achieve quantum speedup is block-encoding. However, to apply this technique effectively, we propose a general method to construct the block-encoding. As an application, we show that all the three classifiers achieve exponential speedup at the number of samples over their classical counterparts. As for the dimension of the space, quantum quadratic and linear classifiers achieve varying degrees of polynomial speedup, while quantum naïve Bayes’ classifier achieves an exponential speedup. The only assumption we make is the qRAM to prepare quantum states of the input data.
The era of big data has made traditional machine learning algorithms struggle with high-dimensional, nonlinear datasets due to high computational resource consumption, long training times, and limited generalization. Quantum computing, with its exponential parallelism from qubit superposition and entanglement, offers new hope for machine learning. Local Sensitive Discriminant Analysis (LSDA) algorithm is a widely used dimensionality reduction technique in machine learning. However, it is time-consuming when handling large-scale high-dimensional data. This paper proposed a quantum version of LSDA algorithm, which transforms the generalized eigenvalue problem in LSDA into a Hermitian eigenvalue problem, solved using quantum phase estimation and block-encoding techniques. Two post-processing strategies are provided to obtain low-dimensional data for quantum or classical machine learning tasks. The quantum LSDA algorithm obtains polynomial speedups compared to the classical LSDA in terms of the number of data points and dimensionality, showing the potential of quantum technique to boost machine learning efficiency.
We apply the framework of block-encodings, introduced by Low and Chuang (under the name standard-form), to the study of quantum machine learning algorithms and derive general results that are applicable to a variety of input models, including sparse matrix oracles and matrices stored in a data structure. We develop several tools within the block-encoding framework, such as singular value estimation of a block-encoded matrix, and quantum linear system solvers using block-encodings. The presented results give new techniques for Hamiltonian simulation of non-sparse matrices, which could be relevant for certain quantum chemistry applications, and which in turn imply an exponential improvement in the dependence on precision in quantum linear systems solvers for non-sparse matrices. In addition, we develop a technique of variable-time amplitude estimation, based on Ambainis' variable-time amplitude amplification technique, which we are also able to apply within the framework. As applications, we design the following algorithms: (1) a quantum algorithm for the quantum weighted least squares problem, exhibiting a 6-th power improvement in the dependence on the condition number and an exponential improvement in the dependence on the precision over the previous best algorithm of Kerenidis and Prakash; (2) the first quantum algorithm for the quantum generalized least squares problem; and (3) quantum algorithms for estimating electrical-network quantities, including effective resistance and dissipated power, improving upon previous work.
Implementing polynomial functions of Hermitian matrices on quantum hardware is a foundational task in quantum computing, critical for accurate Hamiltonian simulation, quantum linear system solving, high-fidelity state preparation, machine learning kernels, and other advanced quantum algorithms. Existing state-of-the-art techniques, including Qubitization, Quantum Singular Value Transformation (QSVT), and Quantum Signal Processing (QSP), rely heavily on block-encoding the Hermitian matrix. These methods are often constrained by the complexity of preparing the block-encoded state, the overhead associated with the required ancillary qubits, or the challenging problem of angle synthesis for the polynomial's phase factors, which limits the achievable circuit depth and overall efficiency. In this work, we propose a novel and resource-efficient approach to implement arbitrary polynomials of a Hermitian matrix by leveraging the Generalized Quantum Signal Processing (GQSP) framework. Our method circumvents the need for block-encoding and avoids the compounding post-selection overheads characteristic of LCU-based constructions, achieving a stable, degree-independent success probability. We derive closed-form expressions for symmetric polynomial expansions and demonstrate how linear combinations of GQSP circuits can realize the desired transformation. This approach reduces resource overhead and opens new pathways for quantum algorithm design for functions of Hermitian matrices, particularly in settings where the Hermitian operator arises naturally from symmetric combinations of unitaries.