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

arXiv:1903.03999

An Improved Algorithm for Quantum Principal Component Analysis

Changpeng Shao

Published Mar 10, 2019• 1 citation
arXivHTMLPDF

Abstract

Principal component analysis is an important dimension reduction technique in machine learning. In [S. Lloyd, M. Mohseni and P. Rebentrost, Nature Physics 10, 631-633, (2014)], a quantum algorithm to implement principal component analysis on quantum computer was obtained by computing the Hamiltonian simulation of unknown density operators. The complexity is $O((\log d)t^2/ε)$, where $d$ is the dimension, $t$ is the evolution time and $ε$ is the precision. We improve this result into $O((\log d)t^{1+\frac{1}{k}}/ε^{\frac{1}{k}})$ for arbitrary constant integer $k\geq 1$. As a result, we show that the Hamiltonian simulation of low-rank dense Hermitian matrices can be implemented in the same time.

DOI
10.48550/arxiv.1903.03999

Related papers

Quantum Principal Component Analysis Only Achieves an Exponential Speedup Because of Its State Preparation Assumptions

Ewin Tang

A central roadblock to analyzing quantum algorithms on quantum states is the lack of a comparable input model for classical algorithms. Inspired by recent work of the author [E. Tang, STOC 2019.], we introduce such a model, where we assume we can efficiently perform ℓ^{2}-norm samples of input data, a natural analog to quantum algorithms that assume efficient state preparation of classical data. Though this model produces less practical algorithms than the (stronger) standard model of classical computation, it captures versions of many of the features and nuances of quantum linear algebra algorithms. With this model, we describe classical analogs to Lloyd, Mohseni, and Rebentrost's quantum algorithms for principal component analysis [S. Lloyd, M. Mohseni, and P. Rebentrost, Nat. Phys. 10, 631 (2014).NPAHAX1745-247310.1038/nphys3029] and nearest-centroid clustering [S. Lloyd, M. Mohseni, and P. Rebentrost, Quantum algorithms for supervised and unsupervised machine learning]. Since they are only polynomially slower, these algorithms suggest that the exponential speedups of their quantum counterparts are simply an artifact of state preparation assumptions.

arXiv:1811.00414•Physical Review Letters•Aug 4, 2021•141 citations

Hardware-efficient quantum principal component analysis for medical image recognition

Zidong Lin, Hongfeng Liu, Kai Tang +10 more

Principal component analysis (PCA) is a widely used tool in machine learning algorithms, but it can be computationally expensive. In 2014, Lloyd, Mohseni & Rebentrost proposed a quantum PCA (qPCA) algorithm [Nat. Phys. 10, 631 (2014)] that has not yet been experimentally demonstrated due to challenges in preparing multiple quantum state copies and implementing quantum phase estimations. In this study, we presented a hardware-efficient approach for qPCA, utilizing an iterative approach that effectively resets the relevant qubits in a nuclear magnetic resonance (NMR) quantum processor. Additionally, we introduced a quantum scattering circuit that efficiently determines the eigenvalues and eigenvectors (principal components). As an important application of PCA, we focused on classifying thoracic CT images from COVID-19 patients and achieved high accuracy in image classification using the qPCA circuit implemented on the NMR system. Our experiment highlights the potential of near-term quantum devices to accelerate qPCA, opening up new avenues for practical applications of quantum machine learning algorithms.

Frontiers of Physics•Apr 8, 2024•10 citations

Experimental Quantum Principal Component Analysis via Parametrized Quantum Circuits

Tao Xin, Liangyu Che, Xi Cheng +5 more

Principal component analysis (PCA) is a widely applied but rather time-consuming tool in machine learning techniques. In 2014, Lloyd, Mohseni, and Rebentrost proposed a quantum PCA (qPCA) algorithm [Lloyd, Mohseni, and Rebentrost, Nat. Phys. 10, 631 (2014)NPAHAX1745-247310.1038/nphys3029] that still lacks experimental demonstration due to the experimental challenges in preparing multiple quantum state copies and implementing quantum phase estimations. Here, we propose a new qPCA algorithm using the hybrid classical-quantum control, where parameterized quantum circuits are optimized with simple measurement observables, which significantly reduces the experimental complexity. As one important PCA application, we implement a human face recognition process using the images from the Yale Face Dataset. By training our quantum processor, the eigenface information in the training dataset is encoded into the parameterized quantum circuit, and the quantum processor learns to recognize new face images from the test dataset with high fidelities. Our work paves a new avenue toward the study of qPCA applications in theory and experiment.

Physical Review Letters•Mar 18, 2021•60 citations

Resonant quantum principal component analysis

Zhaokai Li, Zihua Chai, Yuhang Guo +6 more

Principal component analysis (PCA) has been widely adopted to reduce the dimension of data while preserving the information. The quantum version of PCA (qPCA) can be used to analyze an unknown low-rank density matrix by rapidly revealing the principal components of it, i.e., the eigenvectors of the density matrix with the largest eigenvalues. However, because of the substantial resource requirement, its experimental implementation remains challenging. Here, we develop a resonant analysis algorithm with minimal resource for ancillary qubits, in which only one frequency-scanning probe qubit is required to extract the principal components. In the experiment, we demonstrate the distillation of the first principal component of a 4 × 4 density matrix, with an efficiency of 86.0% and a fidelity of 0.90. This work shows the speedup ability of quantum algorithm in dimension reduction of data and thus could be used as part of quantum artificial intelligence algorithms in the future.

arXiv:2104.02476•Science Advances•Aug 18, 2021•47 citations

A Low-Complexity Quantum Principal Component Analysis Algorithm

Chen He, Jiazhen Li, Weiqi Liu +2 more

In this article, we propose a low-complexity quantum principal component analysis (qPCA) algorithm. Similar to the state-of-the-art qPCA, it achieves dimension reduction by extracting principal components of the data matrix, rather than all components of the data matrix, to quantum registers, so that the samples of measurement required can be reduced considerably. Both our qPCA and Lin’s qPCA are based on quantum singular-value thresholding (QSVT). The key of Lin’s qPCA is to combine QSVT, and modified QSVT is to obtain the superposition of the principal components. The key of our algorithm, however, is to modify QSVT by replacing the rotation-controlled operation of QSVT with the controlled-notoperation to obtain the superposition of the principal components. As a result, this small trick makes the circuit much simpler. Particularly, the proposed qPCA requires three phase estimations, while the state-of-the-art qPCA requires five phase estimations. Since the runtime of qPCA mainly comes from phase estimations, the proposed qPCA achieves a runtime of roughly 3/5 of that of the state of the art. We simulate the proposed qPCA on the IBM quantum computing platform, and the simulation result verifies that the proposed qPCA yields the expected quantum state.

arXiv:2010.00831•IEEE Transactions on Quantum Engineering•Jan 1, 2022•27 citations

Resource-efficient quantum principal component analysis

Youle Wang, Yu H. Luo

Abstract Principal component analysis (PCA) is an important dimensionality reduction method in machine learning and data analysis. Recently, the quantum version of PCA has been established to diagonalize quantum states. Although these quantum algorithms promise quantum advantages, they require substantial resources beyond the reach of state-of-the-art quantum technologies. This work aims to reduce resource requirements and improve the efficiency of quantum PCA. Assuming that the quantum state is accessed through a purified quantum query model and a sampling model, we propose quantum algorithms that use minimal resource requirements for ancillary qubits to reveal properties of eigenvectors and eigenvalues of a state. In particular, we show that estimating eigenvalue λ with error ε and success probability larger than λ ( 1 − η ) requests a query complexity O ~ ( ϵ − 1 ) and a sample complexity O ~ ( ϵ − 2 η − 1 ) , respectively. To our knowledge, our result is the first quantum speedup that achieves asymptotic linear scaling in 1 / ϵ for quantum PCA. As applications, we discuss estimating the minimum relative entropy of entanglement of bipartite pure-states and performing quantum state discrimination tasks. We show that quantum speedups are maintained when the pure state has a low Schmidt number and states of discrimination have a low rank. This study opens up a new quantum PCA method for high-dimensional quantum data analysis and discusses its application in quantum information processing tasks.

Quantum Science and Technology•May 2, 2024•11 citations
Principal component analysis is an important dimension reduction technique in machine learning. In [S. Lloyd, M. Mohseni and P. Rebentrost, Nature Physics 10, 631-633, (2014)], a quantum algorithm to implement principal component analysis on quantum computer was obtained by computing the Hamiltonian simulation of unknown density operators. The complexity is O((log⁡d)t2/ε)O((\log d)t^2/ε)O((logd)t2/ε), where ddd is the dimension, ttt is the evolution time and εεε is the precision. We improve this result into O((log⁡d)t1+1k/ε1k)O((\log d)t^{1+\frac{1}{k}}/ε^{\frac{1}{k}})O((logd)t1+k1​/εk1​) for arbitrary constant integer k≥1k\geq 1k≥1. As a result, we show that the Hamiltonian simulation of low-rank dense Hermitian matrices can be implemented in the same time.
A central roadblock to analyzing quantum algorithms on quantum states is the lack of a comparable input model for classical algorithms. Inspired by recent work of the author [E. Tang, STOC 2019.], we introduce such a model, where we assume we can efficiently perform ℓ^{2}-norm samples of input data, a natural analog to quantum algorithms that assume efficient state preparation of classical data. Though this model produces less practical algorithms than the (stronger) standard model of classical computation, it captures versions of many of the features and nuances of quantum linear algebra algorithms. With this model, we describe classical analogs to Lloyd, Mohseni, and Rebentrost's quantum algorithms for principal component analysis [S. Lloyd, M. Mohseni, and P. Rebentrost, Nat. Phys. 10, 631 (2014).NPAHAX1745-247310.1038/nphys3029] and nearest-centroid clustering [S. Lloyd, M. Mohseni, and P. Rebentrost, Quantum algorithms for supervised and unsupervised machine learning]. Since they are only polynomially slower, these algorithms suggest that the exponential speedups of their quantum counterparts are simply an artifact of state preparation assumptions.
Principal component analysis (PCA) is a widely used tool in machine learning algorithms, but it can be computationally expensive. In 2014, Lloyd, Mohseni & Rebentrost proposed a quantum PCA (qPCA) algorithm [Nat. Phys. 10, 631 (2014)] that has not yet been experimentally demonstrated due to challenges in preparing multiple quantum state copies and implementing quantum phase estimations. In this study, we presented a hardware-efficient approach for qPCA, utilizing an iterative approach that effectively resets the relevant qubits in a nuclear magnetic resonance (NMR) quantum processor. Additionally, we introduced a quantum scattering circuit that efficiently determines the eigenvalues and eigenvectors (principal components). As an important application of PCA, we focused on classifying thoracic CT images from COVID-19 patients and achieved high accuracy in image classification using the qPCA circuit implemented on the NMR system. Our experiment highlights the potential of near-term quantum devices to accelerate qPCA, opening up new avenues for practical applications of quantum machine learning algorithms.
Principal component analysis (PCA) is a widely applied but rather time-consuming tool in machine learning techniques. In 2014, Lloyd, Mohseni, and Rebentrost proposed a quantum PCA (qPCA) algorithm [Lloyd, Mohseni, and Rebentrost, Nat. Phys. 10, 631 (2014)NPAHAX1745-247310.1038/nphys3029] that still lacks experimental demonstration due to the experimental challenges in preparing multiple quantum state copies and implementing quantum phase estimations. Here, we propose a new qPCA algorithm using the hybrid classical-quantum control, where parameterized quantum circuits are optimized with simple measurement observables, which significantly reduces the experimental complexity. As one important PCA application, we implement a human face recognition process using the images from the Yale Face Dataset. By training our quantum processor, the eigenface information in the training dataset is encoded into the parameterized quantum circuit, and the quantum processor learns to recognize new face images from the test dataset with high fidelities. Our work paves a new avenue toward the study of qPCA applications in theory and experiment.
Principal component analysis (PCA) has been widely adopted to reduce the dimension of data while preserving the information. The quantum version of PCA (qPCA) can be used to analyze an unknown low-rank density matrix by rapidly revealing the principal components of it, i.e., the eigenvectors of the density matrix with the largest eigenvalues. However, because of the substantial resource requirement, its experimental implementation remains challenging. Here, we develop a resonant analysis algorithm with minimal resource for ancillary qubits, in which only one frequency-scanning probe qubit is required to extract the principal components. In the experiment, we demonstrate the distillation of the first principal component of a 4 × 4 density matrix, with an efficiency of 86.0% and a fidelity of 0.90. This work shows the speedup ability of quantum algorithm in dimension reduction of data and thus could be used as part of quantum artificial intelligence algorithms in the future.
In this article, we propose a low-complexity quantum principal component analysis (qPCA) algorithm. Similar to the state-of-the-art qPCA, it achieves dimension reduction by extracting principal components of the data matrix, rather than all components of the data matrix, to quantum registers, so that the samples of measurement required can be reduced considerably. Both our qPCA and Lin’s qPCA are based on quantum singular-value thresholding (QSVT). The key of Lin’s qPCA is to combine QSVT, and modified QSVT is to obtain the superposition of the principal components. The key of our algorithm, however, is to modify QSVT by replacing the rotation-controlled operation of QSVT with the controlled-notoperation to obtain the superposition of the principal components. As a result, this small trick makes the circuit much simpler. Particularly, the proposed qPCA requires three phase estimations, while the state-of-the-art qPCA requires five phase estimations. Since the runtime of qPCA mainly comes from phase estimations, the proposed qPCA achieves a runtime of roughly 3/5 of that of the state of the art. We simulate the proposed qPCA on the IBM quantum computing platform, and the simulation result verifies that the proposed qPCA yields the expected quantum state.
Abstract Principal component analysis (PCA) is an important dimensionality reduction method in machine learning and data analysis. Recently, the quantum version of PCA has been established to diagonalize quantum states. Although these quantum algorithms promise quantum advantages, they require substantial resources beyond the reach of state-of-the-art quantum technologies. This work aims to reduce resource requirements and improve the efficiency of quantum PCA. Assuming that the quantum state is accessed through a purified quantum query model and a sampling model, we propose quantum algorithms that use minimal resource requirements for ancillary qubits to reveal properties of eigenvectors and eigenvalues of a state. In particular, we show that estimating eigenvalue λ with error ε and success probability larger than λ ( 1 − η ) requests a query complexity O ~ ( ϵ − 1 ) and a sample complexity O ~ ( ϵ − 2 η − 1 ) , respectively. To our knowledge, our result is the first quantum speedup that achieves asymptotic linear scaling in 1 / ϵ for quantum PCA. As applications, we discuss estimating the minimum relative entropy of entanglement of bipartite pure-states and performing quantum state discrimination tasks. We show that quantum speedups are maintained when the pure state has a low Schmidt number and states of discrimination have a low rank. This study opens up a new quantum PCA method for high-dimensional quantum data analysis and discusses its application in quantum information processing tasks.