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

Laser Physics Letters

Quantum canonical correlation analysis algorithm

Chuandong Song, Jian Li, Yanyan Hou, Qinghui Liu, Zhuo Wang

Published Aug 22, 2023• 3 citations
Publisher

Abstract

Abstract Canonical correlation analysis (CCA) is a fundamental technique used to analyze data correlation in various fields, including video and medical data analysis. In this paper, we propose a quantum canonical correlation analysis (QCCA) algorithm. First, we introduce a combined density matrix representation method that transforms CCA into generalized eigenvalue decomposition. Moreover, to address the challenge of performing generalized eigenvalue decomposition in high-dimensional scenarios, we propose a quantum method for extracting the canonical principal axes. In this method, two sets of variables are transformed into a reduced density matrix, so that the product of variable matrices can be accelerated by phase estimation and controlled rotation. Complexity analysis shows that the QCCA algorithm achieves exponential acceleration in variable dimensions n, p and variable size m compared to classical algorithms. The QCCA algorithm serves as a foundation for the subsequent development of quantum algorithms for classification, regression, and other machine learning tasks.

DOI
10.1088/1612-202x/acee63

Related papers

Quantum-inspired canonical correlation analysis for exponentially large dimensional data

Naoko Koide‐Majima, Kei Majima

Canonical correlation analysis (CCA) serves to identify statistical dependencies between pairs of multivariate data. However, its application to high-dimensional data is limited due to considerable computational complexity. As an alternative to the conventional CCA approach that requires polynomial computational time, we propose an algorithm that approximates CCA using quantum-inspired computations with computational time proportional to the logarithm of the input dimensionality. The computational efficiency and performance of the proposed quantum-inspired CCA (qiCCA) algorithm are experimentally evaluated on synthetic and real datasets. Furthermore, the fast computation provided by qiCCA allows directly applying CCA even after nonlinearly mapping raw input data into high-dimensional spaces. The conducted experiments demonstrate that, as a result of mapping raw input data into the high-dimensional spaces with the use of second-order monomials, qiCCA extracts more correlations compared with the linear CCA and achieves comparable performance with state-of-the-art nonlinear variants of CCA on several datasets. These results confirm the appropriateness of the proposed qiCCA and the high potential of quantum-inspired computations in analyzing high-dimensional data.

arXiv:1907.03236•Neural Networks•Dec 9, 2020•8 citations

Near-optimal quantum kernel principal component analysis

Youle Wang

Abstract Kernel principal component analysis (kernel PCA) is a nonlinear dimensionality reduction technique that employs kernel functions to map data into a high-dimensional feature space, thereby extending the applicability of linear PCA to nonlinear data and facilitating the extraction of informative principal components. However, kernel PCA necessitates the manipulation of large-scale matrices, leading to high computational complexity and posing challenges for efficient implementation in big data environments. Quantum computing has recently been integrated with kernel methods in machine learning, enabling effective analysis of input data within intractable feature spaces. Although existing quantum kernel PCA proposals promise exponential speedups, they impose stringent requirements on quantum hardware that are challenging to fulfill. In this work, we propose a quantum algorithm for kernel PCA by establishing a connection between quantum kernel methods and block encoding, thereby diagonalizing the centralized kernel matrix on a quantum computer. The query complexity is logarithmic with respect to the size of the data vector, D , and linear with respect to the size of the dataset. An exponential speedup could be achieved when the dataset consists of a few high-dimensional vectors, wherein the dataset size is polynomial in log ⁡ ( D ) , with D being significantly large. In contrast to existing work, our algorithm enhances the efficiency of quantum kernel PCA and reduces the requirements for quantum hardware. Furthermore, we have also demonstrated that the algorithm based on block encoding matches the lower bound of query complexity, indicating that our algorithm is nearly optimal. Our research has laid down new pathways for developing quantum machine learning algorithms aimed at addressing tangible real-world problems and demonstrating quantum advantages within machine learning.

Quantum Science and Technology•Nov 12, 2024•6 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

Quantum algorithm for the covariance matrix preparation and its application

Tong Ning, Y. L. Yang

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.

Europhysics Letters (EPL)•Jun 20, 2023•0 citations

Quantum algorithm for low-rank matrix regression with feature extraction

Kaitian Gao, Youlong Yang, Zhenye Du

Low-rank matrix regression is a pivotal technique in image processing and pattern recognition that can directly handle data with intrinsic matrix structures. However, classical algorithms for this task suffer from a computational bottleneck, where the complexity escalates cubically with the matrix dimension, incurring prohibitive costs for high-dimensional datasets. In this study, we propose a quantum algorithm for low-rank matrix regression with feature extraction, leveraging the Harrow–Hassidim–Lloyd algorithm for regression matrix estimation and a modified quantum singular-value thresholding algorithm for iterative variable updates. Theoretical analysis demonstrates that our algorithm reduces the time complexity dependence on the matrix dimension from cubic to logarithmic, achieving an exponential speedup over classical counterparts when the problem is well conditioned and the precision requirements are moderate. Furthermore, we introduce an algorithmic variant utilizing the quantum memory model to bypass the reliance on quantum random access memory. Additionally, we propose a hybrid strategy leveraging quantum sketching techniques to effectively eliminate the runtime dependence on the condition number. Subsequently, we performed small-scale quantum experiments to validate the feasibility of our proposed quantum algorithm.

Journal of Applied Physics•Jan 5, 2026•0 citations

Quantum algorithm for the nonlinear dimensionality reduction with arbitrary kernel

Yaochong Li, Ri‐Gui Zhou, Ruiqing Xu +2 more

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.

Quantum Science and Technology•Oct 5, 2020•36 citations
Abstract Canonical correlation analysis (CCA) is a fundamental technique used to analyze data correlation in various fields, including video and medical data analysis. In this paper, we propose a quantum canonical correlation analysis (QCCA) algorithm. First, we introduce a combined density matrix representation method that transforms CCA into generalized eigenvalue decomposition. Moreover, to address the challenge of performing generalized eigenvalue decomposition in high-dimensional scenarios, we propose a quantum method for extracting the canonical principal axes. In this method, two sets of variables are transformed into a reduced density matrix, so that the product of variable matrices can be accelerated by phase estimation and controlled rotation. Complexity analysis shows that the QCCA algorithm achieves exponential acceleration in variable dimensions n, p and variable size m compared to classical algorithms. The QCCA algorithm serves as a foundation for the subsequent development of quantum algorithms for classification, regression, and other machine learning tasks.
Canonical correlation analysis (CCA) serves to identify statistical dependencies between pairs of multivariate data. However, its application to high-dimensional data is limited due to considerable computational complexity. As an alternative to the conventional CCA approach that requires polynomial computational time, we propose an algorithm that approximates CCA using quantum-inspired computations with computational time proportional to the logarithm of the input dimensionality. The computational efficiency and performance of the proposed quantum-inspired CCA (qiCCA) algorithm are experimentally evaluated on synthetic and real datasets. Furthermore, the fast computation provided by qiCCA allows directly applying CCA even after nonlinearly mapping raw input data into high-dimensional spaces. The conducted experiments demonstrate that, as a result of mapping raw input data into the high-dimensional spaces with the use of second-order monomials, qiCCA extracts more correlations compared with the linear CCA and achieves comparable performance with state-of-the-art nonlinear variants of CCA on several datasets. These results confirm the appropriateness of the proposed qiCCA and the high potential of quantum-inspired computations in analyzing high-dimensional data.
Abstract Kernel principal component analysis (kernel PCA) is a nonlinear dimensionality reduction technique that employs kernel functions to map data into a high-dimensional feature space, thereby extending the applicability of linear PCA to nonlinear data and facilitating the extraction of informative principal components. However, kernel PCA necessitates the manipulation of large-scale matrices, leading to high computational complexity and posing challenges for efficient implementation in big data environments. Quantum computing has recently been integrated with kernel methods in machine learning, enabling effective analysis of input data within intractable feature spaces. Although existing quantum kernel PCA proposals promise exponential speedups, they impose stringent requirements on quantum hardware that are challenging to fulfill. In this work, we propose a quantum algorithm for kernel PCA by establishing a connection between quantum kernel methods and block encoding, thereby diagonalizing the centralized kernel matrix on a quantum computer. The query complexity is logarithmic with respect to the size of the data vector, D , and linear with respect to the size of the dataset. An exponential speedup could be achieved when the dataset consists of a few high-dimensional vectors, wherein the dataset size is polynomial in log ⁡ ( D ) , with D being significantly large. In contrast to existing work, our algorithm enhances the efficiency of quantum kernel PCA and reduces the requirements for quantum hardware. Furthermore, we have also demonstrated that the algorithm based on block encoding matches the lower bound of query complexity, indicating that our algorithm is nearly optimal. Our research has laid down new pathways for developing quantum machine learning algorithms aimed at addressing tangible real-world problems and demonstrating quantum advantages within machine learning.
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.
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.
Low-rank matrix regression is a pivotal technique in image processing and pattern recognition that can directly handle data with intrinsic matrix structures. However, classical algorithms for this task suffer from a computational bottleneck, where the complexity escalates cubically with the matrix dimension, incurring prohibitive costs for high-dimensional datasets. In this study, we propose a quantum algorithm for low-rank matrix regression with feature extraction, leveraging the Harrow–Hassidim–Lloyd algorithm for regression matrix estimation and a modified quantum singular-value thresholding algorithm for iterative variable updates. Theoretical analysis demonstrates that our algorithm reduces the time complexity dependence on the matrix dimension from cubic to logarithmic, achieving an exponential speedup over classical counterparts when the problem is well conditioned and the precision requirements are moderate. Furthermore, we introduce an algorithmic variant utilizing the quantum memory model to bypass the reliance on quantum random access memory. Additionally, we propose a hybrid strategy leveraging quantum sketching techniques to effectively eliminate the runtime dependence on the condition number. Subsequently, we performed small-scale quantum experiments to validate the feasibility of our proposed quantum algorithm.
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.