World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

Efficient quantum algorithms for state measurement and linear algebra applications

    We present an algorithm for measurement of k-local operators in a quantum state, which scales logarithmically both in the system size and the output accuracy. The key ingredients of the algorithm are a digital representation of the quantum state, and a decomposition of the measurement operator in a basis of operators with known discrete spectra. We then show how this algorithm can be combined with (a) Hamiltonian evolution to make quantum simulations efficient, (b) the Newton–Raphson method based solution of matrix inverse to efficiently solve linear simultaneous equations, and (c) Chebyshev expansion of matrix exponentials to efficiently evaluate thermal expectation values. The general strategy may be useful in solving many other linear algebra problems efficiently.


    • 1. R. P. Feynman, Int. J. Theor. Phys. 21 (1982) 467. Crossref, ISIGoogle Scholar
    • 2. R. P. Brent and P. Zimmermann, Modern Computer Arithmetic (Cambridge University Press, 2010). CrossrefGoogle Scholar
    • 3. D. W. Berry, A. M. Childs, R. Cleve, R. Kothari and R. D. Somma, Exponential improvement in precision for simulating sparse Hamiltonians, in Proc. 46th Annual ACM Symp. on Theory of Computing, STOC’14, New York, NY, 31 May–3 June (ACM, New York, 2014), pp. 283–292. Google Scholar
    • 4. D. W. Berry, A. M. Childs, R. Cleve, R. Kothari and R. D. Somma, Phys. Rev. Lett. 114 (2015) 090502. Crossref, ISIGoogle Scholar
    • 5. A. Patel and A. Priyadarsini, Int. J. Quantum Inform. 16 (2016) 1650027. Google Scholar
    • 6. S. Lloyd, Science 273 (1996) 1073. Crossref, ISIGoogle Scholar
    • 7. D. Aharonov and A. Ta-Shma, Adiabatic quantum state generation and statistical zero knowledge, in Proc. 35th Annual ACM Symp. on Theory of Computing, STOC’03, San Diego, CA, 9–11 June (ACM, New York, 2003), pp. 20–29. Google Scholar
    • 8. A. W. Harrow, A. Hassidim and S. Lloyd, Phys. Rev. Lett. 103 (2009) 150502. Crossref, ISIGoogle Scholar
    • 9. B. D. Clader, B. C. Jacobs and C. R. Sprouse, Phys. Rev. Lett. 110 (2013) 250504. Crossref, ISIGoogle Scholar
    • 10. T. Cai, D. Kim, Y. Wang, M. Yuan and H. H. Zhou, Ann. Statistics 44 (2016) 682. Crossref, ISIGoogle Scholar
    • 11. M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, Sec. 6.2 (Cambridge University Press, Cambridge, 2000). Google Scholar
    • 12. H. Chernoff, Ann. Math. Statistics 23 (1952) 493. Crossref, ISIGoogle Scholar
    • 13. M. R. Hestenes and E. Stiefel, J. Res. National Bureau of Standards 49 (1952) 409. Crossref, ISIGoogle Scholar
    • 14. W. H. Press, S. A. Teukolsky, W. T. Vetterling and B. P. Flannery, Numerical Recipes: The Art of Scientific Computing, Chap. 2.5, 3rd edn. (Cambridge University Press, 2007). Google Scholar
    • 15. V. Pan and J. Reif, Efficient parallel solution of linear systems, in Proc. 17th Annual ACM Symp. on Theory of Computing, STOC’85, Providence, RI, 6–8 May (ACM, New York, 1985), pp. 143–152. Google Scholar
    • 16. S. Sachdeva and N. K. Vishnoi, Matrix inversion is as easy as exponentiation, arXiv:1305.0526. Google Scholar
    • 17. S. Sachdeva and N. K. Vishnoi, FnT Theor. Comput. Sci. 9 (2013) 125. CrossrefGoogle Scholar
    • 18. G. B. Arfken, H. J. Weber and F. E. Harris, Mathematical Methods for Physicists: A Comprehensive Guide, Chap. 18.4, 7th edn. (Academic Press, 2011). Google Scholar
    • 19. H. Tal-Ezer and R. Kosloff, J. Chem. Phys. 81 (1984) 3967. Crossref, ISIGoogle Scholar
    • 20. M. AbramowitzI. A. Stegun (eds.), Handbook of Mathematical Functions: With Formulas, Graphs and Mathematical Tables, Chap. 9.12 (Dover Publications, 1965). Google Scholar
    Remember to check out the Most Cited Articles!

    Check out Annual Physics Catalogue 2019 and recommend us to your library!