CoChat
Sign Up
Cited by 1,385Quantum Computing Algorithms and ArchitectureQuantum Information and CryptographyQuantum many-body systems

Quantum principal component analysis

Open access
Lloyd, Seth, Mohseni, Masoud, Rebentrost, Patrick·2014·Nature Physics
DOI 10.1038/nphys3029
Open this paper in CoChat — free accountOpen PDF

Abstract

Characterizing an unknown quantum state typically relies on analysing the outcome of a large set of measurements. Certain quantum-processing tasks are now shown to be realizable using only approximate knowledge of the state, which can be gathered with exponentially fewer resources. The usual way to reveal properties of an unknown quantum state, given many copies of a system in that state, is to perform measurements of different observables and to analyse the results statistically1,2. For non-sparse but low-rank quantum states, revealing eigenvectors and corresponding eigenvalues in classical form scales super-linearly with the system dimension3,4,5,6. Here we show that multiple copies of a quantum system with density matrix ρ can be used to construct the unitary transformation e−iρt. As a result, one can perform quantum principal component analysis of an unknown low-rank density matrix, revealing in quantum form the eigenvectors corresponding to the large eigenvalues in time exponentially faster than any existing algorithm. We discuss applications to data analysis, process tomography and state discrimination.

AI snapshot

Written from the paper’s full text.

TL;DR

The paper proposes using many copies of a quantum state’s density matrix to simulate the unitary evolution generated by that matrix, enabling quantum principal component analysis. It shows that dominant eigenvectors and eigenvalues of low-rank states can be exposed in time logarithmic in the system dimension, with applications to tomography, data analysis, and state discrimination.

Key findings

  • Repeated infinitesimal swap operations on ρ⊗σ can approximate the unitary e^{-iρt}; the simulation error scales as ε = O(t²/n), and n = O(t²ε^{-1}) copies suffice under the stated norm bound.
  • Quantum PCA constructs eigenvectors and eigenvalues of an unknown low-rank density matrix in time O(R log d), using n = O(1/ε³) copies for phase estimation to accuracy ε; the abstract describes this as exponentially faster than existing algorithms.
  • For a covariance matrix Σ = AA† with quantum access to the columns of A, e^{-itΣ/trΣ} can be implemented in O(n log d) time, extending efficient exponentiation to non-sparse low-rank matrices; existing Suzuki-Trotter methods require O(d log d) for non-sparse Hamiltonians.
  • Applications include process tomography via the Choi-Jamiolkowski state, state discrimination, and cluster assignment; qPCA is compared with compressed sensing, which reconstructs the full density matrix in O(Rd log d), while qPCA associates eigenvectors and eigenvalues in O(R log d).

Methods

  • Theoretical quantum-algorithm paper with no empirical dataset or experiment reported.
  • Uses multiple copies of ρ, the swap operator, partial traces, and Suzuki-Trotter simulation to implement e^{-iρt}; a conditional swap enables conditional applications for quantum phase estimation.
  • Analyzes sample complexity, runtime, and applications, including data analysis with quantum access to vectors and norms via quantum random access memory.

Limitations

  • The paper states that qPCA reveals only a fraction of the full information needed to describe a system, and that it works best when the density matrix is low-rank or dominated by a few large eigenvalues; if all eigenvalues are O(1/d), resolving them requires time O(d).
  • The paper notes accuracy depends on the low-rank approximation or projection error, and the method requires many copies of the state.
  • Evident from the text: the data-analysis application assumes quantum access to data columns and norms, with quantum random access memory requiring O(d) hardware resources and switches; the algorithm outputs eigenvectors in quantum form, and obtaining a classical full density matrix description would take O(Rd log d). No experimental demonstration is presented.

Model-written summary. Check it against the paper before relying on it.

Integrity signals

Registry

Crossref · 10.1038/nphys3029

Cites

33 of 33 references verified0 citation errors · 0 not checkable

Statistics

Nothing to recompute.

Claims the paper makes

0 of 22 cited sources checked · 0 supported · 0 flagged

  • Findingreasoning

    With n=O(t^2 ε^{-1}) copies of Σ/trΣ, the operator e^{-itΣ/trΣ} can be implemented to precision ε in O(n log d) time.

    “Using n = O(t 2 -1 ) copies of Σ/trΣ allows us to implement e -itΣ/trΣ to accuracy in time O(n log d).”
    Quote in the paperSubstantial claim
    • The authors state this as an assumption: Quantum access is available to the columns of A and to their norms.
    • The authors state this as an assumption: The data vectors can be generated in quantum parallel by an oracle.
    • The authors state this as an assumption: A quantum computer or quantum random access memory is available that maps |i>|0>|0> to |i>|a_i>|a_i>.
  • Findingreasoning

    For an unknown low-rank density matrix ρ, qPCA produces its eigenvectors and eigenvalues in O(R log d) time.

    “The primary difference is that qPCA constructs eigenvectors and associates them with the corresponding eigenvalues in time O(R log d)”
    • Also stated in: § Abstract · plain
      “qPCA efficiently reveals the eigenvectors and eigenvalues of the unknown density matrix ρ and allows one to probe their properties.”
    Quote in the paperSubstantial claim
  • Findingreasoning

    A conditional version of the operation is obtained by substituting a controlled SWAP for the ordinary SWAP in the derivation.

    “Here, in contrast, the conditional operation can be performed simply by replacing the SWAP operator with a conditional SWAP in the derivation above.”
    Quote in the paperSubstantial claim
  • Findingreasoning

    A set of copies of a quantum state with density matrix ρ enables implementation of the unitary e^{-iρt}.

    “Here we show that multiple copies of a quantum system with density matrix ρ can be used to construct the unitary transformation e -iρt .”
    • Also stated in: § Abstract · plain
      “we show that multiple copies of the state ρ can be used to implement the unitary operator e -iρt”
    Quote in the paperSubstantial claim
  • Findingnone given

    If the matrix has low rank, projecting onto the subspace of large eigenvalues is exact.

    “When the matrix is of low rank, the projection is exact.”
    Quote in the paperSubstantial claim
  • May combine two claims. 14
  • The quote only partly states this claim. 1
  • Classified as probably not a substantial claim. 2

  • May combine two claims.

    Findingnone given

    qPCA is beneficial when ρ has small rank R or can be approximated at rank R; in that case only the top R eigenvalues appear as nonzero in the decomposition.

    “As above, qPCA is useful if ρ has small rank R or admits a rank R approximation.In this case, only the largest R eigenvalues will register as non-zero in the eigenvector/eigenvalue decomposition (2).”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingcitation

    Density matrix exponentiation works best when ρ has some large eigenvalues; when every eigenvalue is O(1/d), resolving them needs time t=O(d).

    “Note that density matrix exponentiation is most effective when some of the eigenvalues of ρ are large.If all of the eigenvalues are of size O(1/d) then we require time t = O(d) to resolve the eigenvalues 15 .”
    Quote in the paperSubstantial claim0 of 1 sources checked
    • cites [15] Harrow, A. W., Hassidim, A. & Lloyd, S. Quantum algorithm for linear systems of equations. Phys. Rev. Lett. 103, 150502 (2009). source

      Not checked in the free run.

  • May combine two claims.

    Findingnone given

    With mn copies of ρ, one gets m instances of the decomposition, and the i-th eigenvalue r_i occurs about r_i m times.

    “Using mn copies of ρ we obtain m copies of the decomposition (2), where the ith eigenvalue r i appears ≈ r i m times.”
    Quote in the paperSubstantial claim

  • The quote only partly states this claim.

    Findingreasoning

    Repeated infinitesimal swap operations on ρ⊗σ allow construction of e^{-iρt} to accuracy ε, requiring n=O(t^2 ε^{-1}) steps.

    “Repeated application of (1) with n copies of ρ allows one to construct e -iρn t σ e iρn t .”
    • Also stated in: § Abstract · plain
      “to simulate e -iρt to accuracy requires n = O(t 2 -foot_0 |ρ -σ | 2 ) ≤ O(t 2 -1 ) steps”
    • Also stated in: § Abstract · plain
      “Thus, simply performing repeated infinitesimal swap operations on ρ ⊗ σ allows us to construct the unitary operator e -iρt .”
    Quote in the paperSubstantial claim0 of 1 sources checked
    • cites [11][12][13][14]

      Not checked in the free run.

  • May combine two claims.

    Findingcitation

    Feeding the conditional operation into quantum phase estimation gives eigenvector and eigenvalue estimates to precision ε, with copy count scaling as O(1/ε^3).

    “Inserting this conditional operation in the quantum phase algorithm and using the improved phaseestimation techniques of ref. 15 yields the eigenvectors and eigenvalues to accuracy by applying the quantum phase algorithm for time t = O( -1 ), and so requires n = O(1/ 3 ) copies of the state ρ.”
    Quote in the paperSubstantial claim0 of 1 sources checked
    • cites [15] Harrow, A. W., Hassidim, A. & Lloyd, S. Quantum algorithm for linear systems of equations. Phys. Rev. Lett. 103, 150502 (2009). source

      Not checked in the free run.

  • May combine two claims.

    Findingcitation

    Properties of the i-th eigenstate can be read by measuring the expectation of a chosen Hermitian M in that state; when M is sparse or efficiently simulable, the measurement takes O(log d) time.

    “The features of the ith eigenstate can then be determined by performing a quantum measurement to obtain the expectation value χ i |M|χ i of the eigenvector with eigenvalue r i for desired Hermitian M. As long as M is sparse [11][12][13][14] or efficiently simulable by the methods given in this paper, this measurement can itself be performed in time O(log d).”
    Quote in the paperSubstantial claim0 of 1 sources checked
    • cites [11][12][13][14]

      Not checked in the free run.

  • Classified as probably not a substantial claim.

    Premisecitation

    Compressed sensing employs only single-qubit state preparation and measurement.

    “Only single-qubit preparations and measurements are employed.”
    Quote in the paperSubstantial claim0 of 1 sources checked
    • cites [3][4][5]7,8

      Not checked in the free run.

  • May combine two claims.

    Interpretationcitation

    qPCA can build the eigenvectors for the dominant eigenvalues of the Choi-Jamiolkowski state, and the resulting spectral decomposition captures many key channel properties.

    “qPCA can then be used to construct the eigenvectors corresponding to the dominant eigenvalues of this state: the resulting spectral decomposition in turn encapsulates many of the most important properties of the channel 22 .”
    Quote in the paperSubstantial claim0 of 1 sources checked
    • cites [22] Choi, M-D. Completely positive linear maps on complex matrices. Lin. Alg. Appl. 10, 285–290 (1975). source

      Not checked in the free run.

  • May combine two claims.

    Interpretationreasoning

    qPCA could tomograph the eigenvectors in O(Rd log d) time; that classical description can then reproduce the full density matrix in O(Rd log d) time, matching quantum compressed sensing but using multi-qubit infinitesimal swaps.

    “qPCA could also be used to perform state tomography on the eigenvectors, revealing their components in time O(Rd log d).This classical description of the eigenvalues and eigenvectors can then be used to reproduce the full density matrix in time O(Rd log d), the same as in quantum compressed sensing but relying on the multi-qubit infinitesimal swap operation.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Interpretationreasoning

    qPCA efficiently uncovers the eigenvectors and eigenvalues of an unknown ρ and permits their properties to be examined.

    “qPCA efficiently reveals the eigenvectors and eigenvalues of the unknown density matrix ρ and allows one to probe their properties.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Interpretationreasoning

    qPCA outputs, in quantum form, the eigenvectors tied to the large eigenvalues, achieving an exponential speed-up over all prior algorithms.

    “As a result, one can perform quantum principal component analysis of an unknown low-rank density matrix, revealing in quantum form the eigenvectors corresponding to the large eigenvalues in time exponentially faster than any existing algorithm.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Premisecitation

    Compressed sensing must first reconstruct the density matrix and then diagonalize it to obtain eigenvectors and eigenvalues, which randomized low-rank algorithms do in time greater than O(d^2 log R + dR^2).

    “In contrast, to construct the eigenvectors and eigenvalues using compressed sensing one must first reconstruct the density matrix and then diagonalize it, which takes time >O(d 2 log R + dR 2 ) by randomized algorithms for low-rank matrices 6 .”
    Quote in the paperSubstantial claim0 of 1 sources checked
    • cites [6] Liberty, E., Woolfe, F., Martinsson, P-G., Rokhlin, V. & Tygert, M. Randomized algorithms for the low-rank approximation of matrices. Proc. Natl Acad. Sci. USA 104, 20167–20172 (2007). source

      Not checked in the free run.

  • Classified as probably not a substantial claim.

    Interpretationnone given

    Identifying the largest eigenvalues and their eigenvectors may aid representation and analysis of large high-dimensional data sets.

    “The ability to identify the largest eigenvalues of a matrix together with the corresponding eigenvectors is potentially useful for the representation and analysis of large amounts of high-dimensional data.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Interpretationreasoning

    When |χ comes from one of the two sets, the procedure amounts to minimum-error state discrimination but runs exponentially faster.

    “If |χ is selected from one of the two sets, this procedure is simply minimum error state discrimination 1 , but exponentially faster.”
    Quote in the paperSubstantial claim0 of 1 sources checked
    • cites [1] Nielsen, M. A. & Chuang, I. L. Quantum Computation and Quantum Information (Cambridge Univ. Press, 2000).

      Not checked in the free run.

  • May combine two claims.

    Interpretationreasoning

    The absolute value of the measured eigenvalue gauges confidence in the set assignment: larger magnitudes mean greater confidence, and magnitude 1 means certainty.

    “As a bonus, the magnitude of the measured eigenvalue is a measure of the confidence of the set assignment measurement: larger magnitude eigenvalues correspond to higher confidence in the assignment, and magnitude 1 corresponds to certainty”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Interpretationcitation

    For an arbitrary vector |χ, the method serves as a tool for supervised learning and cluster assignment.

    “If |χ is some other vector, then the method provides a method for supervised learning and cluster assignment 9,10,21,28 :”
    Quote in the paperSubstantial claim0 of 4 sources checked
    • cites [9] Bishop, C. M. Pattern Recognition and Machine Learning (Springer, 2006).

      Not checked in the free run.

    • cites [10] Murphy, K. P. Machine Learning: A Probabilistic Perspective (MIT Press, 2012).

      Not checked in the free run.

    • cites [21] Lloyd, S., Mohseni, M. & Rebentrost, P. Quantum algorithms for supervised and unsupervised machine learning. Preprint at http://arxiv.org/abs/1307.0411 (2013).

      Not checked in the free run.

    • cites [28] Rebentrost, P., Mohseni, M. & Lloyd, S. Quantum support vector machine for big data classification. Preprint at http://arxiv.org/abs/1307.0471 (2013). source

      Not checked in the free run.

  • May combine two claims.

    Premisecitation

    Group-representation methods obtain the spectrum in O(poly(log d)) time but need O(d^2) time to reconstruct eigenvectors.

    “These methods reveal the spectrum [24][25][26] in time O(poly(log d)) but take time O(d 2 ) to reconstruct the eigenvectors 26 .”
    Quote in the paperSubstantial claim0 of 1 sources checked
    • cites [24][25][26]

      Not checked in the free run.

17 of 17

  • The authors state this as an assumption.

    Quantum access is available to the columns of A and to their norms.

    “Assume that we have quantum access to the columns |a i of A and to their norms |a i |.”

  • The authors state this as an assumption.

    The data vectors can be generated in quantum parallel by an oracle.

    “suppose that the density matrix corresponds to the covariance matrix of a set of data vectors a i ∈ C d that can be generated in quantum parallel using an oracle.”

  • The authors state this as an assumption.

    A quantum computer or quantum random access memory is available that maps |i>|0>|0> to |i>|a_i>|a_i>.

    “That is, we have a quantum computer or quantum random access memory [18][19][20] that takes |i |0 |0 → |i |a i ||a i | .”
3 of 3

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Sufficiently powerful quantum computers can in principle provide computational speedups for key machine learning algorithms and subroutines such as data fitting, principal component analysis, Bayesian inference, Monte Carlo methods, support vector machines, Boltzmann machines, and recommendation systems.

    “Sufficiently powerful quantum computers can in principle provide computational speedups for key machine learning algorithms and subroutines such as data fitting [4], principal component analysis [5], Bayesian inference [6,7], Monte Carlo methods [8], support vector machines [9,10], Boltzmann machines [11,12], and recommendation systems [13].”

    From Continuous-variable quantum neural networks (2019) · cites this paper as [5]

  • An alternative approach for nonlinear differential equations based on a set of basis functions rather than a finite grid was proposed in Ref [144].

    “An alternative approach has been proposed for nonlinear differential equations that is based on using a set of basis functions rather than a finite grid [144].”

    From Variational quantum algorithms (2021) · cites this paper as [144]

    The Abstract passages describe quantum principal component analysis and density-matrix exponentiation, while the Discussion describes applications to data analysis. Searches for nonlinear differential equations, basis functions, and finite grids found no passage in our copy addressing the attributed approach. (LLM, conf=0.75)

    Experimental — accuracy not yet measured

  • By more sophisticated Trotter-Suzuki decompositions, the approximation error can be made to depend on progressively higher orders in τ.

    “First, by more sophisticated Trotter-Suzuki decompositions 261 , the approximation error can be made to depend on progressively-higher orders in τ 196,260,261 .”

    From Quantum Chemistry in the Age of Quantum Computing (2019) · cites this paper as [260]

  • Quantum realizations of principal components analysis and support vector machine have been derived.

    “The first advantage has been leveraged in deriving the quantum realization of the principal components analysis algorithm [221] and of a support vector machine.[222]”

    From Quantum Computing for Molecular Biology** (2023) · cites this paper as [221]

  • The quantum PCA algorithm builds the covariance matrix of the data in the quantum computer, and uses quantum phase estimation to compute the eigenvectors in logarithmic time.

    “In essence, this algorithm builds the covariance matrix of the data in the quantum computer, and uses a subroutine known as quantum phase estimation [15] to compute the eigenvectors in logarithmic time.”

    From The prospects of quantum computing in computational molecular biology (2021) · cites this paper as [86]

Cites

Flagged first, then by citations

Research works printed but not linked: 2

  1. Aharonov, D. & Ta-Shma, A. Proc. 35th Annu. ACM Symp. on Theory of Computing 20–29 (ACM, 2003).
  2. Bar-Yossef, Z. Proc. 35th Annu. ACM Symp. on Theory of Computing 335–344 (ACM, 2003).

Cited by

Sorted by citations

Related

Authors
Lloyd, S., Mohseni, M., & Rebentrost, P.
Affiliations
  • Massachusetts Institute of Technology (US)
  • Google (United States) (US)
Corresponding author
Lloyd, Seth
ORCID
Venue
Nature Physics
Publisher
Springer Science and Business Media LLC
Published
2014-07-27
Volume
10
Issue
9
Pages
631-633
ISSN
  • 1745-2473 (ISSN-L)
  • 1745-2481
DOI
10.1038/nphys3029
OpenAlex
W1988369744
Semantic Scholar
faddf7f2fcac43032645bd7f562ef21ddddb71fb
Cited by
1,385
References
33
Citations by year
2026: 131 · 2025: 195 · 2024: 165 · 2023: 173 · 2022: 142 · 2021: 180 · 2020: 130 · 2019: 109 · 2018: 64 · 2017: 40 · 2016: 33 · 2015: 13 · 2014: 10
FWCI
31.61
Type
journal article
Language
en
Open access
Licence
Locations
  • Nature Physics (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • DSpace@MIT (Massachusetts Institute of Technology) (submittedVersion, cc-by-nc-sa)
  • arXiv (Cornell University)
Funders
  • National Aeronautics and Space Administration
  • Defense Advanced Research Projects Agency
  • Multidisciplinary University Research Initiative
  • Air Force Office of Scientific Research
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
Keywords
quantum principal component analysis, quantum state tomography, process tomography, state discrimination, exponential speedup, quantum state evolution

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Claims read by deepseek-v4.1-flash under definition version 3 (extract-v3) on 2026-10-07.

Classified by jev-1.13-20260917 (gold-guideline-v0.2) on 2026-10-07.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review