Efficient quantum algorithms for state measurement and linear algebra applications
Abstract
We present an algorithm for measurement of -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.
References
- 1. , Int. J. Theor. Phys. 21 (1982) 467. Crossref, ISI, Google Scholar
- 2. , Modern Computer Arithmetic (Cambridge University Press, 2010). Crossref, Google Scholar
- 3. , 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. , Phys. Rev. Lett. 114 (2015) 090502. Crossref, ISI, Google Scholar
- 5. , Int. J. Quantum Inform. 16 (2016) 1650027. Google Scholar
- 6. , Science 273 (1996) 1073. Crossref, ISI, Google Scholar
- 7. , 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. , Phys. Rev. Lett. 103 (2009) 150502. Crossref, ISI, Google Scholar
- 9. , Phys. Rev. Lett. 110 (2013) 250504. Crossref, ISI, Google Scholar
- 10. , Ann. Statistics 44 (2016) 682. Crossref, ISI, Google Scholar
- 11. , Quantum Computation and Quantum Information, Sec. 6.2 (Cambridge University Press, Cambridge, 2000). Google Scholar
- 12. , Ann. Math. Statistics 23 (1952) 493. Crossref, ISI, Google Scholar
- 13. , J. Res. National Bureau of Standards 49 (1952) 409. Crossref, ISI, Google Scholar
- 14. , Numerical Recipes: The Art of Scientific Computing, Chap. 2.5, 3rd edn. (Cambridge University Press, 2007). Google Scholar
- 15. , 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. , FnT Theor. Comput. Sci. 9 (2013) 125. Crossref, Google Scholar
- 18. , Mathematical Methods for Physicists: A Comprehensive Guide, Chap. 18.4, 7th edn. (Academic Press, 2011). Google Scholar
- 19. , J. Chem. Phys. 81 (1984) 3967. Crossref, ISI, Google 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! |
