Document Open Access Logo

The Power of Block-Encoded Matrix Powers: Improved Regression Techniques via Faster Hamiltonian Simulation

Authors Shantanav Chakraborty, András Gilyén, Stacey Jeffery

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.33.pdf
  • Filesize: 480 kB
  • 14 pages

Document Identifiers

Author Details

Shantanav Chakraborty
  • QuIC, Université libre de Bruxelles, Belgium
András Gilyén
  • QuSoft/CWI, The Netherlands
Stacey Jeffery
  • QuSoft/CWI, The Netherlands

Acknowledgements

The authors are grateful for Iordanis Kerendis, Anupam Prakash and Michael Walter for useful discussions. SC is supported by the Belgian Fonds de la Recherche Scientifique - FNRS under grants no F.4515.16 (QUICTIME) and R.50.05.18.F (QuantAlgo). AG is supported by ERC Consolidator Grant QPROGRESS. SJ is supported by an NWO WISE Grant and NWO Veni Innovational Research Grant under project number 639.021.752.

Cite AsGet BibTex

Shantanav Chakraborty, András Gilyén, and Stacey Jeffery. The Power of Block-Encoded Matrix Powers: Improved Regression Techniques via Faster Hamiltonian Simulation. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 33:1-33:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.33

Abstract

We apply the framework of block-encodings, introduced by Low and Chuang (under the name standard-form), to the study of quantum machine learning algorithms and derive general results that are applicable to a variety of input models, including sparse matrix oracles and matrices stored in a data structure. We develop several tools within the block-encoding framework, such as singular value estimation of a block-encoded matrix, and quantum linear system solvers using block-encodings. The presented results give new techniques for Hamiltonian simulation of non-sparse matrices, which could be relevant for certain quantum chemistry applications, and which in turn imply an exponential improvement in the dependence on precision in quantum linear systems solvers for non-sparse matrices. In addition, we develop a technique of variable-time amplitude estimation, based on Ambainis' variable-time amplitude amplification technique, which we are also able to apply within the framework. As applications, we design the following algorithms: (1) a quantum algorithm for the quantum weighted least squares problem, exhibiting a 6-th power improvement in the dependence on the condition number and an exponential improvement in the dependence on the precision over the previous best algorithm of Kerenidis and Prakash; (2) the first quantum algorithm for the quantum generalized least squares problem; and (3) quantum algorithms for estimating electrical-network quantities, including effective resistance and dissipated power, improving upon previous work.

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum computation theory
Keywords
  • Quantum algorithms
  • Hamiltonian simulation
  • Quantum machine learning

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Dorit Aharonov and Amnon Ta-Schma. Adiabatic quantum state generation and statistical zero-knowledge. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC 2003), pages 20-29, 2003. URL: http://dx.doi.org/10.1145/780542.780546.
  2. Andris Ambainis. Variable time amplitude amplification and quantum algorithms for linear algebra problems. In Symposium on Theoretical Aspects of Computer Science STACS, pages 636-647, 2012. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2012.636.
  3. Srinivasan Arunachalam, Vlad Gheorghiu, Tomas Jochym-O’Connor, Michele Mosca, and Priyaa Varshinee Srinivasan. On the robustness of bucket brigade quantum RAM. New Journal of Physics, 17(12):123010, 2015. URL: http://arxiv.org/abs/1502.03450.
  4. Ryan Babbush, Dominic W Berry, Ian D Kivlichan, Annie Y Wei, Peter J Love, and Alán Aspuru-Guzik. Exponentially more precise quantum simulation of fermions in second quantization. New Journal of Physics, 18(3):033032, 2016. URL: http://arxiv.org/abs/1506.01020.
  5. D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma. Exponential improvement in precision for simulating sparse Hamiltonians. In Symposium on Theory of Computing, STOC 2014, pages 283-292, 2014. URL: http://dx.doi.org/10.1145/2591796.2591854.
  6. Dominic W. Berry, Graeme Ahokas, Richard Cleve, and Barry C. Sanders. Efficient quantum algorithms for simulating sparse Hamiltonians. Communications in Mathematical Physics, 270(2):359-371, 2007. URL: http://dx.doi.org/10.1007/s00220-006-0150-x.
  7. Dominic W. Berry and Andrew M. Childs. Black-box Hamiltonian simulation and unitary implementation. Quantum Information and Computation, 12(1-2):29-62, 2012. URL: http://arxiv.org/abs/0910.4157.
  8. Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. Simulating Hamiltonian Dynamics with a Truncated Taylor Series. Phys. Rev. Lett., 114:090502, 2015. URL: http://dx.doi.org/10.1103/PhysRevLett.114.090502.
  9. Dominic W. Berry, Andrew M. Childs, and Robin Kothari. Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters. In FOCS, pages 792-809, 2015. URL: http://dx.doi.org/10.1109/FOCS.2015.54.
  10. Dominic W. Berry and Leonardo Novo. Corrected quantum walk for optimal Hamiltonian simulation. Quantum Information and Computation, 16(15-16):1295-1317, 2016. URL: http://dx.doi.org/10.26421/QIC16.15-16.
  11. Shantanav Chakraborty, András Gilyén, and Stacey Jeffery. The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation, 2018. URL: http://arxiv.org/abs/1804.01973.
  12. Andrew M. Childs. Quantum information processing in continuous time. PhD thesis, Massachusetts Institute of Technology, 2004. URL: https://dspace.mit.edu/handle/1721.1/16663.
  13. Andrew M. Childs. On the relationship between continuous- and discrete-time quantum walk. Communications in Mathematical Physics, 294(2):581-603, 2010. URL: http://dx.doi.org/10.1007/s00220-009-0930-1.
  14. Andrew M. Childs, Robin Kothari, and Rolando D. Somma. Quantum Algorithm for Systems of Linear Equations with Exponentially Improved Dependence on Precision. SIAM Journal on Computing, 46(6):1920-1950, 2017. URL: http://dx.doi.org/10.1137/16M1087072.
  15. Andrew M. Childs and Nathan Wiebe. Hamiltonian simulation using linear combinations of unitaries. Quantum Information and Computation, 12(11-12):901-924, 2012. URL: http://arxiv.org/abs/1202.5822.
  16. András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st ACM Symposium on Theory of Computing (STOC), 2019. (to appear). URL: http://arxiv.org/abs/1806.01838.
  17. Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Quantum Random Access Memory. Phys. Rev. Lett., 100:160501, April 2008. URL: http://dx.doi.org/10.1103/PhysRevLett.100.160501.
  18. Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Physical review letters, 103(15):150502, 2009. URL: http://dx.doi.org/10.1103/PhysRevLett.103.150502.
  19. Iordanis Kerenidis and Anupam Prakash. Quantum recommendation systems. CoRR, 2016. URL: http://arxiv.org/abs/1603.08675.
  20. Iordanis Kerenidis and Anupam Prakash. Quantum gradient descent for linear systems and least squares, 2017. URL: http://arxiv.org/abs/1704.04992.
  21. Yang Liu and Shengyu Zhang. Fast Quantum Algorithms for Least Squares Regression and Statistic Leverage Scores. Theor. Comput. Sci., 657(PA):38-47, 2017. URL: http://dx.doi.org/10.1016/j.tcs.2016.05.044.
  22. Seth Lloyd. Universal quantum simulators. Science, 273(5278):1073-1078, 1996. URL: http://dx.doi.org/10.1126/science.273.5278.1073.
  23. Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum principal component analysis. Nature Physics, 10(631), 2014. URL: http://dx.doi.org/10.1038/nphys3029.
  24. Guang Hao Low and Isaac L. Chuang. Hamiltonian Simulation by Qubitization, 2016. URL: http://arxiv.org/abs/1610.06546.
  25. Leonardo Novo and Dominic W. Berry. Improved Hamiltonian simulation via a truncated Taylor series and corrections. Quantum Information and Computation, 17(7-8):0623-0635, 2016. URL: http://dx.doi.org/10.26421/QIC17.7-8.
  26. David Poulin, Angie Qarry, Rolando Somma, and Frank Verstraete. Quantum Simulation of Time-Dependent Hamiltonians and the Convenient Illusion of Hilbert Space. Phys. Rev. Lett., 106:170501, April 2011. URL: http://dx.doi.org/10.1103/PhysRevLett.106.170501.
  27. Maria Schuld, Ilya Sinayskiy, and Francesco Petruccione. Prediction by linear regression on a quantum computer. Physical Review A, 94:022342, 2016. URL: http://dx.doi.org/10.1103/PhysRevA.94.022342.
  28. Chunhao Wang and Leonard Wossnig. A quantum algorithm for simulating non-sparse Hamiltonian, 2018. URL: http://arxiv.org/abs/1803.08273.
  29. Guoming Wang. Efficient Quantum Algorithms for Analyzing Large Sparse Electrical Networks. Quantum Information and Computation, 11 and 12:987-1026, 2017. URL: http://dx.doi.org/10.26421/QIC17.11-12.
  30. Guoming Wang. Quantum algorithm for linear regression. Physical Review A, 96:012335, 2017. URL: http://dx.doi.org/10.1103/PhysRevA.96.012335.
  31. Nathan Wiebe, Dominic W. Berry, Peter Høyer, and Barry C. Sanders. Simulating Hamiltonian dynamics on a quantum computer. Journal of Physics A, 44(44):445308, 2011. URL: http://arxiv.org/abs/1011.3489.
  32. Nathan Wiebe, Daniel Braun, and Seth Lloyd. Quantum algorithm for data fitting. Physical review letters, 109(5):050505, 2012. URL: http://dx.doi.org/10.1103/PhysRevLett.109.050505.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact