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

Europhysics Letters (EPL)

Quantum algorithm for the covariance matrix preparation and its application

Tong Ning, Y. L. Yang

Published Jun 20, 2023• 0 citations
Publisher

Abstract

Abstract Performing the eigendecomposition of the covariance matrix of the dataset is of great significance in the field of machine learning. However, classical operations will become time-consuming when involving large data sets. In this paper, in order to address this problem, we design an efficient quantum algorithm to prepare the covariance matrix state by means of quantum amplitude estimation. After that, we research on its application in principal component analysis and Mahalanobis distance calculation. Specifically, we obtain the transformation matrix for quantum principal component analysis based on the singular value estimation algorithm and the amplitude amplification algorithm. Furthermore, we invoke the quantum matrix inversion algorithm to calculate the Mahalanobis distance. The final complexity analysis shows that our proposed algorithms can achieve speedup compared to their classical counterparts under certain conditions.

DOI
10.1209/0295-5075/acdff5

Related papers

Covariance matrix preparation for quantum principal component analysis

Max Hunter Gordon, M. Cerezo, Łukasz Cincio +1 more

Principal component analysis (PCA) is a dimensionality reduction method in data analysis that involves diagonalizing the covariance matrix of the dataset. Recently, quantum algorithms have been formulated for PCA based on diagonalizing a density matrix. These algorithms assume that the covariance matrix can be encoded in a density matrix, but a concrete protocol for this encoding has been lacking. Our work aims to address this gap. Assuming amplitude encoding of the data, with the data given by the ensemble $\{p_i,| ψ_i \rangle\}$, then one can easily prepare the ensemble average density matrix $\overlineρ = \sum_i p_i |ψ_i\rangle \langle ψ_i |$. We first show that $\overlineρ$ is precisely the covariance matrix whenever the dataset is centered. For quantum datasets, we exploit global phase symmetry to argue that there always exists a centered dataset consistent with $\overlineρ$, and hence $\overlineρ$ can always be interpreted as a covariance matrix. This provides a simple means for preparing the covariance matrix for arbitrary quantum datasets or centered classical datasets. For uncentered classical datasets, our method is so-called "PCA without centering", which we interpret as PCA on a symmetrized dataset. We argue that this closely corresponds to standard PCA, and we derive equations and inequalities that bound the deviation of the spectrum obtained with our method from that of standard PCA. We numerically illustrate our method for the MNIST handwritten digit dataset. We also argue that PCA on quantum datasets is natural and meaningful, and we numerically implement our method for molecular ground-state datasets.

arXiv:2204.03495•Apr 7, 2022•2 citations

Quantum principal component analysis based on the dynamic selection of eigenstates

Barkha Soni, Nilay Khare

Abstract Quantum principal component analysis is a dimensionality reduction method to select the significant features of a dataset. A classical method finds the solution in polynomial time, but when the dimension of feature space scales exponentially, it is inefficient to compute the matrix exponentiation of the covariance matrix. The quantum method uses density matrix exponentiation to find principal components with exponential speedup. We enhance the existing algorithm that applies amplitude amplification using range-based static selection of eigenstates on the output of phase estimation. So, we propose an equivalent quantum method with the same complexity using a dynamic selection of eigenstates. Our algorithm can efficiently find phases of equally likely eigenvalues based on the similarity scores. It obtains principal components associated with highly probable larger eigenvalues. We analyze these methods on various factors to justify the resulting complexity of a proposed method as effective in quantum counterparts.

Europhysics Letters (EPL)•Feb 17, 2022•4 citations

Covariance Matrix Preparation for Quantum Principal Component Analysis

Max Hunter Gordon, Marco Cerezo, Łukasz Cincio +1 more

Principal component analysis (PCA) is a dimensionality reduction method in data analysis that involves diagonalizing the covariance matrix of the dataset. Recently, quantum algorithms have been formulated for PCA based on diagonalizing a density matrix. These algorithms assume that the covariance matrix can be encoded in a density matrix, but a concrete protocol for this encoding has been lacking. Our work aims to address this gap. Assuming amplitude encoding of the data, with the data given by the ensemble {pi, |ψi$\rangle$}, then one can easily prepare the ensemble average density matrix $\overline{ρ}$ =Σipi|ψi$\rangle$$\langle$ψi|. We first show that $\overline{ρ}$ is precisely the covariance matrix whenever the dataset is centered. For quantum datasets, we exploit global phase symmetry to argue that there always exists a centered dataset consistent with $\overline{ρ}$ , and hence $\overline{ρ}$ can always be interpreted as a covariance matrix. This provides a simple means for preparing the covariance matrix for arbitrary quantum datasets or centered classical datasets. For uncentered classical datasets, our method is so-called “PCA without centering,” which we interpret as PCA on a symmetrized dataset. We argue that this closely corresponds to standard PCA, and we derive equations and inequalities that bound the deviation of the spectrum obtained with our method from that of standard PCA. We numerically illustrate our method for the Modified National Institute of Standards and Technology (MNIST) handwritten digit dataset. We also argue that PCA on quantum datasets is natural and meaningful, and we numerically implement our method for molecular ground-state datasets.

PRX Quantum•Sep 7, 2022•28 citations

A QUANTUM APPROXIMATION ALGORITHM FOR COVARIANCE OF RANDOM VARIABLES

Michal Koren, OR PERETZ

Quantum computing is a promising emerging field in computational science, attracting significant international research interest. Data representation is crucial to the success of machine learning models, and covariance analysis to determine relationships between pairs of random variables is an essential step in exploratory data analysis. Here we introduce a novel quantum algorithm for covariance approximation and its circuit implementation for discrete-value vectors. The algorithm leverages vital components of quantum computing, including amplitude encoding, the Grover diffusion algorithm for amplitude amplification and the quantum Fourier transform. As a core innovation, we utilize two quantum states and their properties of superposition product states to estimate the covariance between input vectors. Evaluating the quantum algorithm’s performance over five discrete-value distributions, we found high levels of agreement between the classical and quantum computations, with maximum average errors averaging 0.153. Furthermore, the analysis revealed additional applications of the Grover diffusion operator to solve problems.

Quantum Journal of Engineering Science and Technology•Sep 30, 2024•0 citations

Quantum phase estimation based algorithms for machine learning

Oumayma Ouedrhiri, Oumayma Banouar, Salah El Hadaj +1 more

Quantum computing is certainly one of the greatest advances in the computer science field. Thanks to the parallelism and entanglement properties, it has proved to offer several advantages compared to the classical algorithms especially in the great reduction of the processing time. Quantum phase estimation (QPE) is one of the most important algorithms for quantum computing. It is known as the eigenvalue finding module for unitary operators. The Fourier transform is the key to this procedure. It has been researched and used to solve many problems such as the order finding problem, and the factoring problem. It was also applied for quantum sampling algorithms and the calculation of the eigenvalues of unitary matrices. In this paper, we study three important quantum algorithms for machine learning that use the QPE algorithm as a subroutine: the quantum principal components analysis (PCA) for data visualization, the Harrow-Hassidim-Lloyd (HHL) algorithm for solving linear systems, and the quantum singular value thresholding (SVT) for matrix completion in recommender systems. We also discuss the advantages and limits of such algorithms compared to their classical versions. Then we discuss potential ways of amelioration of such algorithms, and end with a proposed approach for further improvement.

International Informatics and Software Engineering Conference (IISEC)•Dec 16, 2021•3 citations

Advancement of Quantum Methods in Principal Component Analysis

Barkha Soni, Nilay Khare

Quantum principal component analysis (QPCA) is analogous to the classical method with additive speedup. This is based on the unsupervised dimensionality reduction mechanism that transforms exponentially high dimensional data points into low dimensional space by retaining significant features with the largest variance. To our knowledge, quantum computations are highly exponential and supports implicit parallelism. Therefore, quantum method for finding principal components are proved to achieve exponential speedup over existing classical solution. An advantage of quantum superposition is utilized for the Eigen decomposition of density matrix which is identical to covariance, however, a way through which its computation happen, is truly an interesting factor. This paper presents basic methodological framework to design QPCA algorithm. Our framework includes the methods for quantum data encoding, quantum memory processing, and the requisite quantum circuit implementations to realize QPCA algorithms. In addition, we categorized existing QPCA methods in view of recent advances. We then proposed the possible advancements that can benefit to design quantum based efficient algorithms for principal component analysis. At the last, suggested concepts are compared with existing methods based on complexities and other factors to justify our proposal as significant in perspective to future directions.

International Conference on Computing, Communication and Networking Technologies (ICCCNT)•Jul 6, 2021•3 citations
Abstract Performing the eigendecomposition of the covariance matrix of the dataset is of great significance in the field of machine learning. However, classical operations will become time-consuming when involving large data sets. In this paper, in order to address this problem, we design an efficient quantum algorithm to prepare the covariance matrix state by means of quantum amplitude estimation. After that, we research on its application in principal component analysis and Mahalanobis distance calculation. Specifically, we obtain the transformation matrix for quantum principal component analysis based on the singular value estimation algorithm and the amplitude amplification algorithm. Furthermore, we invoke the quantum matrix inversion algorithm to calculate the Mahalanobis distance. The final complexity analysis shows that our proposed algorithms can achieve speedup compared to their classical counterparts under certain conditions.
Principal component analysis (PCA) is a dimensionality reduction method in data analysis that involves diagonalizing the covariance matrix of the dataset. Recently, quantum algorithms have been formulated for PCA based on diagonalizing a density matrix. These algorithms assume that the covariance matrix can be encoded in a density matrix, but a concrete protocol for this encoding has been lacking. Our work aims to address this gap. Assuming amplitude encoding of the data, with the data given by the ensemble {pi,∣ψi⟩}\{p_i,| ψ_i \rangle\}{pi​,∣ψi​⟩}, then one can easily prepare the ensemble average density matrix ρ‾=∑ipi∣ψi⟩⟨ψi∣\overlineρ = \sum_i p_i |ψ_i\rangle \langle ψ_i |ρ​=∑i​pi​∣ψi​⟩⟨ψi​∣. We first show that ρ‾\overlineρρ​ is precisely the covariance matrix whenever the dataset is centered. For quantum datasets, we exploit global phase symmetry to argue that there always exists a centered dataset consistent with ρ‾\overlineρρ​, and hence ρ‾\overlineρρ​ can always be interpreted as a covariance matrix. This provides a simple means for preparing the covariance matrix for arbitrary quantum datasets or centered classical datasets. For uncentered classical datasets, our method is so-called "PCA without centering", which we interpret as PCA on a symmetrized dataset. We argue that this closely corresponds to standard PCA, and we derive equations and inequalities that bound the deviation of the spectrum obtained with our method from that of standard PCA. We numerically illustrate our method for the MNIST handwritten digit dataset. We also argue that PCA on quantum datasets is natural and meaningful, and we numerically implement our method for molecular ground-state datasets.
Abstract Quantum principal component analysis is a dimensionality reduction method to select the significant features of a dataset. A classical method finds the solution in polynomial time, but when the dimension of feature space scales exponentially, it is inefficient to compute the matrix exponentiation of the covariance matrix. The quantum method uses density matrix exponentiation to find principal components with exponential speedup. We enhance the existing algorithm that applies amplitude amplification using range-based static selection of eigenstates on the output of phase estimation. So, we propose an equivalent quantum method with the same complexity using a dynamic selection of eigenstates. Our algorithm can efficiently find phases of equally likely eigenvalues based on the similarity scores. It obtains principal components associated with highly probable larger eigenvalues. We analyze these methods on various factors to justify the resulting complexity of a proposed method as effective in quantum counterparts.
Principal component analysis (PCA) is a dimensionality reduction method in data analysis that involves diagonalizing the covariance matrix of the dataset. Recently, quantum algorithms have been formulated for PCA based on diagonalizing a density matrix. These algorithms assume that the covariance matrix can be encoded in a density matrix, but a concrete protocol for this encoding has been lacking. Our work aims to address this gap. Assuming amplitude encoding of the data, with the data given by the ensemble {pi, |ψi⟩\rangle⟩}, then one can easily prepare the ensemble average density matrix ρ‾\overline{ρ}ρ​ =Σipi|ψi⟩\rangle⟩⟨\langle⟨ψi|. We first show that ρ‾\overline{ρ}ρ​ is precisely the covariance matrix whenever the dataset is centered. For quantum datasets, we exploit global phase symmetry to argue that there always exists a centered dataset consistent with ρ‾\overline{ρ}ρ​ , and hence ρ‾\overline{ρ}ρ​ can always be interpreted as a covariance matrix. This provides a simple means for preparing the covariance matrix for arbitrary quantum datasets or centered classical datasets. For uncentered classical datasets, our method is so-called “PCA without centering,” which we interpret as PCA on a symmetrized dataset. We argue that this closely corresponds to standard PCA, and we derive equations and inequalities that bound the deviation of the spectrum obtained with our method from that of standard PCA. We numerically illustrate our method for the Modified National Institute of Standards and Technology (MNIST) handwritten digit dataset. We also argue that PCA on quantum datasets is natural and meaningful, and we numerically implement our method for molecular ground-state datasets.
Quantum computing is a promising emerging field in computational science, attracting significant international research interest. Data representation is crucial to the success of machine learning models, and covariance analysis to determine relationships between pairs of random variables is an essential step in exploratory data analysis. Here we introduce a novel quantum algorithm for covariance approximation and its circuit implementation for discrete-value vectors. The algorithm leverages vital components of quantum computing, including amplitude encoding, the Grover diffusion algorithm for amplitude amplification and the quantum Fourier transform. As a core innovation, we utilize two quantum states and their properties of superposition product states to estimate the covariance between input vectors. Evaluating the quantum algorithm’s performance over five discrete-value distributions, we found high levels of agreement between the classical and quantum computations, with maximum average errors averaging 0.153. Furthermore, the analysis revealed additional applications of the Grover diffusion operator to solve problems.
Quantum computing is certainly one of the greatest advances in the computer science field. Thanks to the parallelism and entanglement properties, it has proved to offer several advantages compared to the classical algorithms especially in the great reduction of the processing time. Quantum phase estimation (QPE) is one of the most important algorithms for quantum computing. It is known as the eigenvalue finding module for unitary operators. The Fourier transform is the key to this procedure. It has been researched and used to solve many problems such as the order finding problem, and the factoring problem. It was also applied for quantum sampling algorithms and the calculation of the eigenvalues of unitary matrices. In this paper, we study three important quantum algorithms for machine learning that use the QPE algorithm as a subroutine: the quantum principal components analysis (PCA) for data visualization, the Harrow-Hassidim-Lloyd (HHL) algorithm for solving linear systems, and the quantum singular value thresholding (SVT) for matrix completion in recommender systems. We also discuss the advantages and limits of such algorithms compared to their classical versions. Then we discuss potential ways of amelioration of such algorithms, and end with a proposed approach for further improvement.
Quantum principal component analysis (QPCA) is analogous to the classical method with additive speedup. This is based on the unsupervised dimensionality reduction mechanism that transforms exponentially high dimensional data points into low dimensional space by retaining significant features with the largest variance. To our knowledge, quantum computations are highly exponential and supports implicit parallelism. Therefore, quantum method for finding principal components are proved to achieve exponential speedup over existing classical solution. An advantage of quantum superposition is utilized for the Eigen decomposition of density matrix which is identical to covariance, however, a way through which its computation happen, is truly an interesting factor. This paper presents basic methodological framework to design QPCA algorithm. Our framework includes the methods for quantum data encoding, quantum memory processing, and the requisite quantum circuit implementations to realize QPCA algorithms. In addition, we categorized existing QPCA methods in view of recent advances. We then proposed the possible advancements that can benefit to design quantum based efficient algorithms for principal component analysis. At the last, suggested concepts are compared with existing methods based on complexities and other factors to justify our proposal as significant in perspective to future directions.