CoChat
Sign Up
Cited by 127Quantum Computing Algorithms and ArchitectureQuantum many-body systemsQuantum Information and Cryptography

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

Open access
Chakraborty, Shantanav, Gilyén, András, Jeffery, Stacey·2019·Schloss Dagstuhl – Leibniz-Zentrum für Informatik
DOI 10.4230/lipics.icalp.2019.33
Open this paper in CoChat — free accountOpen PDF

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.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.4230/lipics.icalp.2019.33

Cites

4 of 4 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

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?

  • For an N x N linear system, classical algorithmic complexity scales polynomially in N, whereas the HHL quantum algorithm has complexity scaling logarithmically in N, with some scaling improvements proposed.

    “The classical algorithmic complexity for this task scales polynomially in the dimension N , whereas the now-famous Harrow-Hassidim-Lloyd (HHL) quantum algorithm [3] has a complexity that scales logarithmically in N , with some scaling improvements having been proposed [134-137].”

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

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 44

  1. [AA03] Scott Aaronson and Andris Ambainis. Quantum search of spatial regions. In FOCS , pages 200-209, 2003, arXiv: quant-ph/0303041 . · arXiv
  2. [AGGW17] Joran van Apeldoorn, András Gilyén, Sander Gribling, and Ronald de Wolf. Quantum SDP-solvers: Better upper and lower bounds. In FOCS , pages 403-414, 2017, arXiv: 1705.01843 . · arXiv
  3. [AGJO + 15] 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, arXiv: 1502.03450 . · arXiv
  4. [Amb12] 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, arXiv: 1010.4458 . · arXiv
  5. [ATS03] 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, arXiv: quant-ph/0301023 . · arXiv
  6. [BACS07] 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, arXiv: quant-ph/0508139 . · arXiv
  7. [BBK + 16] 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, arXiv: 1506.01020 . · arXiv
  8. [BC12] Dominic W. Berry and Andrew M. Childs. Black-box hamiltonian simulation and unitary implementation. Quantum Information and Computation , 12(1-2):29-62, 2012, arXiv: 0910.4157 . · arXiv
  9. [BCC + 14] 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, arXiv: 1312.1414 . · arXiv
  10. [BCJ + 13] Aleksandrs Belovs, Andrew M Childs, Stacey Jeffery, Robin Kothari, and Frédéric Magniez. Time-efficient quantum walks for 3-distinctness. In International Colloquium on Automata, Languages, and Programming , pages 105-122. Springer, 2013, arXiv: 1302.7316 . · arXiv
  11. [BCK15] Dominic W. Berry, Andrew M. Childs, and Robin Kothari. Hamiltonian simulation with nearly optimal dependence on all parameters. In FOCS , pages 792-809, 2015, arXiv: 1501.01715 . · arXiv
  12. [Bel97] R. Bellman. Introduction to Matrix Analysis . Society for Industrial and Applied Mathematics, second edition, 1997.
  13. [Bel13] Aleksandrs Belovs. Quantum walks and electric networks. 2013, arXiv: 1302.3143 . · arXiv
  14. [BN16] Dominic W. Berry and Leonardo Novo. Corrected quantum walk for optimal hamiltonian simulation. Quantum Information and Computation , 16(15-16):1295-1317, 2016, arXiv: 1606.03443 . · arXiv
  15. [Bol13] Béla Bollobás. Modern graph theory . Springer Science & Business Media, 2013.
  16. [CEMM98] Richard Cleve, Artur Ekert, Chiara Macchiavello, and Michele Mosca. Quantum algorithms revisited. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences , 454(1969):339-354, 1998, arXiv: quant-ph/9708016 . · arXiv
  17. [CGJ18] Shantanav Chakraborty, András Gilyén, and Stacey Jeffery. The power of blockencoded matrix powers: improved regression techniques via faster hamiltonian simulation, 2018. arXiv:1804.01973v1 . · arXiv
  18. [Chi04] Andrew M. Childs. Quantum information processing in continuous time . PhD thesis, Massachusetts Institute of Technology, 2004.
  19. [CKM + 11] Paul Christiano, Jonathan A Kelner, Aleksander Madry, Daniel A Spielman, and Shang-Hua Teng. Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs. In Proceedings of the forty-third annual ACM symposium on Theory of computing , pages 273-282. ACM, 2011, arXiv: 1010.2921 . · arXiv
  20. [CKS17] Andrew M. Childs, Robin Kothari, and Rolando D. Somma. Quantum algorithm for systems of linear equations with exponentially improved dependence on precision. 2017, arXiv: 1511.02306 . · arXiv
  21. [CW12] Andrew M. Childs and Nathan Wiebe. Hamiltonian simulation using linear combinations of unitaries. Quantum Information and Computation , 12(11-12):901-924, 2012, arXiv: 1202.5822 . · arXiv
  22. [GLM08] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Quantum random access memory. Phys. Rev. Lett. , 100:160501, Apr 2008, arXiv: 0708.1879 . · arXiv
  23. [GR02] Lov Grover and Terry Rudolph. Creating superpositions that correspond to efficiently integrable probability distributions. 2002, arXiv: quant-ph/0208112 . · arXiv
  24. [GSLW18] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. 2018, arXiv: 1806.01838 . · arXiv
  25. [HHL09] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Physical review letters , 103(15):150502, 2009, arXiv: 0811.3171 . · arXiv
  26. [IJ16] Tsuyoshi Ito and Stacey Jeffery. Approximate span programs. In Proceedings of the 43rd International Colloquium on Automata, Languages and Programming (ICALP 2016) , 2016, arXiv: 1507.00432 . · arXiv
  27. [KP16] Iordanis Kerenidis and Anupam Prakash. Quantum recommendation systems. 2016, arXiv: 1603.08675 . · arXiv
  28. [KP17] Iordanis Kerenidis and Anupam Prakash. Quantum gradient descent for linear systems and least squares. 2017, arXiv: 1704.04992 . · arXiv
  29. [LC16] Guang Hao Low and Isaac L. Chuang. Hamiltonian simulation by qubitization. 2016, arXiv: 1610.06546 . · arXiv
  30. [LC17] Guang Hao Low and Isaac L. Chuang. Hamiltonian simulation by uniform spectral amplification. 2017, arXiv: 1707.05391 . · arXiv
  31. [LRS13] Yin Tat Lee, Satish Rao, and Nikhil Srivastava. A new approach to computing maximum flows using electrical flows. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing , pages 755-764. ACM, 2013.
  32. [MLM17] Dominic J Moylett, Noah Linden, and Ashley Montanaro. Quantum speedup of the traveling-salesman problem for bounded-degree graphs. Physical Review A , 95(3):032323, 2017, arXiv: 1612.06203 . · arXiv
  33. [Mon15] Ashley Montanaro. Quantum walk speedup of backtracking algorithms. 2015, arXiv: 1509.02374 . · arXiv
  34. [NB16] Leonardo Novo and Dominic W. Berry. Improved hamiltonian simulation via a truncated Taylor series and corrections. Quantum Information and Computation , 17(78):0623-0635, 2016, arXiv: 1611.10033 . · arXiv
  35. [PQSV11] 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, Apr 2011, arXiv: 1102.1360 . · arXiv
  36. [SS11] Daniel A Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. SIAM Journal on Computing , 40(6):1913-1926, 2011, arXiv: 0803.0929 . · arXiv
  37. [SSP16] Maria Schuld, Ilya Sinayskiy, and Francesco Petruccione. Prediction by linear regression on a quantum computer. Physical Review A , 94:022342, 2016, arXiv: 1601.07823 . · arXiv
  38. [TS13] Amnon Ta-Shma. Inverting well conditioned matrices in quantum logspace. In Proceedings of the Forty-fifth Annual ACM Symposium on Theory of Computing , pages 881-890, 2013.
  39. [Wan17a] Guoming Wang. Efficient quantum algorithms for analyzing large sparse electrical networks. Quantum Information and Computation , 11 and 12:987-1026, 2017, arXiv: 1311.1851 . · arXiv
  40. [Wan17b] Guoming Wang. Quantum algorithm for linear regression. Physical Review A , 96:012335, 2017, arXiv: 1402.0660 . · arXiv
  41. [WBHS11] 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, arXiv: 1011.3489 . · arXiv
  42. [WBL12] Nathan Wiebe, Daniel Braun, and Seth Lloyd. Quantum algorithm for data fitting. Physical review letters , 109(5):050505, 2012, arXiv: 1204.5242 . · arXiv
  43. [WW18] Chunhao Wang and Leonard Wossnig. A quantum algorithm for simulating nonsparse hamiltonian, 2018, arXiv: 1803.08273 . · arXiv
  44. [WZP18] Leonard Wossnig, Zhikuan Zhao, and Anupam Prakash. Quantum linear system algorithm for dense matrices. Physical review letters , 120(5):050502, 2018, arXiv: 1704.06174 . · arXiv

Cited by

Sorted by citations

Authors
Chakraborty, S., Gilyén, A., & Jeffery, S.
Affiliations
  • Université Libre de Bruxelles (BE)
  • Centrum Wiskunde & Informatica (NL)
ORCID
Venue
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Publisher
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Published
2019
ISSN
2331-8422 (ISSN-L)
DOI
10.4230/lipics.icalp.2019.33
OpenAlex
W2795534239
Cited by
127
References
4
Citations by year
2026: 3 · 2025: 18 · 2024: 23 · 2023: 24 · 2022: 22 · 2021: 11 · 2020: 17 · 2019: 9
Type
posted content
Language
en
Open access
Licence
creativecommons.org/licenses/by/3.0/legalcode
Locations
  • arXiv (Cornell University) (submittedVersion)
  • Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands (submittedVersion)
  • DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) (submittedVersion, cc-by)
  • Data Archiving and Networked Services (DANS) (submittedVersion, other-oa)
  • CWI's Institutional Repository (Centrum Wiskunde & Informatica) (submittedVersion, other-oa)
  • UvA-DARE (University of Amsterdam) (submittedVersion, cc-by)
  • Dépôt institutionnel de l'Université libre de Bruxelles (Université Libre de Bruxelles) (submittedVersion, other-oa)
  • arXiv (Cornell University)
  • Leibniz international proceedings in informatics (cc-by)
Funders
  • Fonds De La Recherche Scientifique - FNRS (F.4515.16)
  • Nederlandse Organisatie voor Wetenschappelijk Onderzoek
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
Keywords
block encoding, Hamiltonian simulation, quantum linear system solvers, quantum machine learning, singular value estimation, effective resistance, power dissipation, electrical networks, quantum chemistry, regression algorithms

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.

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