Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Thank you for visiting nature.com. You are using a browser version with limited support for CSS. To obtain the best experience, we recommend you use a more up to date browser (or turn off compatibility mode in Internet Explorer). In the meantime, to ensure continued support, we are displaying the site without styles and JavaScript.

Advertisement

Nature Physics
  • Letter
  • Published:

Quantum principal component analysis

Nature Physicsvolume 10, pages631–633 (2014)Cite this article

Subjects

Abstract

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.

This is a preview of subscription content,access via your institution

Access options

Access through your institution

Subscription info for Japanese customers

We have a dedicated website for our Japanese customers. Please go tonatureasia.com to subscribe to this journal.

Buy this article

  • Purchase on SpringerLink
  • Instant access to the full article PDF.

￥ 4,980

Prices may be subject to local taxes which are calculated during checkout

Similar content being viewed by others

References

  1. Nielsen, M. A. & Chuang, I. L.Quantum Computation and Quantum Information (Cambridge Univ. Press, 2000).

    MATH  Google Scholar 

  2. Mohseni, M., Rezakhani, A. T. & Lidar, D. A. Quantum-process tomography: Resource analysis of different strategies.Phys. Rev. A77, 032322 (2008).

    Article ADS  Google Scholar 

  3. Gross, D., Liu, Y-K., Flammia, S. T., Becker, S. & Eisert, J. Quantum state tomography via compressed sensing.Phys. Rev. Lett.105, 150401 (2010).

    Article ADS  Google Scholar 

  4. Liu, Y-K. Universal low-rank matrix recovery from Pauli measurements.Adv. Neural Inf. Proc. Sys. (NIPS)24, 1638–1646 (2011).

    Google Scholar 

  5. Flammia, S. T., Gross, D., Liu, Y-K. & Eisert, J. Quantum tomography via compressed sensing: Error bounds, sample complexity and efficient estimators.New J. Phys.14, 095022 (2012).

    Article ADS  Google Scholar 

  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. USA104, 20167–20172 (2007).

    Article ADS MathSciNet  Google Scholar 

  7. Shabani, A. et al. Efficient measurement of quantum dynamics via compressive sensing.Phys. Rev. Lett.106, 100401 (2011).

    Article ADS  Google Scholar 

  8. Shabani, A., Mohseni, M., Lloyd, S., Kosut, R. L. & Rabitz, H. Estimation of many-body quantum hamiltonians via compressive sensing.Phys. Rev. A84, 012107 (2011).

    Article ADS  Google Scholar 

  9. Bishop, C. M.Pattern Recognition and Machine Learning (Springer, 2006).

    MATH  Google Scholar 

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

    MATH  Google Scholar 

  11. Lloyd, S. Universal quantum simulators.Science273, 1073–1078 (1996).

    Article ADS MathSciNet  Google Scholar 

  12. Aharonov, D. & Ta-Shma, A.Proc. 35th Annu. ACM Symp. on Theory of Computing 20–29 (ACM, 2003).

    Google Scholar 

  13. Berry, D. W., Ahokas, G., Cleve, R. & Sanders, B. C. Efficient quantum algorithms for simulating sparse hamiltonians.Commun. Math. Phys.270, 359–371 (2007).

    Article ADS MathSciNet  Google Scholar 

  14. Wiebe, N., Berry, D. W., Hoyer, P. & Sanders, B. C. Simulating quantum dynamics on a quantum computer.J. Phys. A43, 065203 (2010).

    Article ADS MathSciNet  Google Scholar 

  15. Harrow, A. W., Hassidim, A. & Lloyd, S. Quantum algorithm for linear systems of equations.Phys. Rev. Lett.103, 150502 (2009).

    Article ADS MathSciNet  Google Scholar 

  16. Araújo, M., Feix, A., Costa, F. & Brukner, Č. Quantum circuits cannot control unknown operations. Preprint athttp://arxiv.org/abs/1309.7976 (2013).

  17. Nakayama, S., Soeda, A. & Murao, M. Universal implementation of projective measurement of energy. Preprint athttp://arxiv.org/abs/1310.3047 (2013).

  18. Giovannetti, V., Lloyd, S. & Maccone, L. Quantum random access memory.Phys. Rev. Lett.100, 160501 (2008).

    Article ADS MathSciNet  Google Scholar 

  19. Giovannetti, V., Lloyd, S. & Maccone, L. Architectures for a quantum random access memory.Phys. Rev. A78, 052310 (2008).

    Article ADS  Google Scholar 

  20. De Martini, F. et al. Experimental quantum private queries with linear optics.Phys. Rev. A80, 010302(R) (2009).

    Article ADS  Google Scholar 

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

  22. Choi, M-D. Completely positive linear maps on complex matrices.Lin. Alg. Appl.10, 285–290 (1975).

    Article MathSciNet  Google Scholar 

  23. Bar-Yossef, Z.Proc. 35th Annu. ACM Symp. on Theory of Computing 335–344 (ACM, 2003).

    Google Scholar 

  24. Keyl, M. & Werner, R. F. Estimating the spectrum of a density operator.Phys. Rev. A64, 052311 (2001).

    Article ADS MathSciNet  Google Scholar 

  25. Bacon, D., Chuang, I. L. & Harrow, A. W. Efficient quantum circuits for Schur and Clebsch–Gordan transforms.Phys. Rev. Lett.97, 170502 (2006).

    Article ADS MathSciNet  Google Scholar 

  26. Keyl, M. Quantum state estimation and large deviations.Rev. Math. Phys.18, 19–60 (2006).

    Article MathSciNet  Google Scholar 

  27. Helstrom, C. W.Quantum Detection and Estimation Theory (Academic, 1976).

    MATH  Google Scholar 

  28. Rebentrost, P., Mohseni, M. & Lloyd, S. Quantum support vector machine for big data classification. Preprint athttp://arxiv.org/abs/1307.0471 (2013).

Download references

Acknowledgements

This work was supported by DARPA, Google-NASA Quantum Artificial Intelligence Laboratory, AFOSR under a MURI program, and J. Epstein. The authors thank A. Childs and R. Kothari for helpful discussions.

Author information

Authors and Affiliations

  1. Department of Mechanical Engineering, Massachusetts Institute of Technology, 02139 Cambridge, Massachusetts, USA

    Seth Lloyd

  2. Research Laboratory for Electronics, Massachusetts Institute of Technology, 02139 Cambridge, Massachusetts, USA

    Seth Lloyd & Patrick Rebentrost

  3. Google Research, 90291 Venice, California, USA

    Masoud Mohseni

Authors
  1. Seth Lloyd
  2. Masoud Mohseni
  3. Patrick Rebentrost

Contributions

S.L., M.M. and P.R. contributed to the theoretical research described in the paper and the writing of the manuscript.

Corresponding author

Correspondence toSeth Lloyd.

Ethics declarations

Competing interests

The authors declare no competing financial interests.

Rights and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Lloyd, S., Mohseni, M. & Rebentrost, P. Quantum principal component analysis.Nature Phys10, 631–633 (2014). https://doi.org/10.1038/nphys3029

Download citation

This article is cited by

Access through your institution
Buy or subscribe

Associated content

Show, don't tell

  • Yi-Kai Liu
Nature PhysicsNews & Views

Advertisement

Search

Advanced search

Quick links

Nature Briefing

Sign up for theNature Briefing newsletter — what matters in science, free to your inbox daily.

Get the most important science stories of the day, free in your inbox.Sign up for Nature Briefing
[8]ページ先頭
©2009-2025 Movatter.jp