# The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation

arXiv: https://arxiv.org/abs/1804.01973 · HTML: https://mlsanity.com/paper/1804.01973/

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Apr 2018.

## Built on by (most cited first, 30 of 30)

- [A Survey on Quantum Reinforcement Learning](https://mlsanity.com/paper/2211.03464/) (2022)
- [Quantum Deep Hedging](https://mlsanity.com/paper/2303.16585/) (2023)
- [Quantum Reinforcement Learning via Policy Iteration](https://mlsanity.com/paper/2203.01889/) (2022)
- [A Primer on Quantum Machine Learning](https://mlsanity.com/paper/2511.15969/) (2025)
- [Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraints](https://mlsanity.com/paper/2110.13086/) (2021)
- [Quantum Transformer: Accelerating model inference via quantum linear algebra](https://mlsanity.com/paper/2402.16714/) (2024)
- [Quantum Machine Learning for Finance](https://mlsanity.com/paper/2109.04298/) (2021)
- [Revisiting Quantum Algorithms for Linear Regressions: Quadratic Speedups without Data-Dependent Parameters](https://mlsanity.com/paper/2311.14823/) (2023)
- [Do you know what q-means?](https://mlsanity.com/paper/2308.09701/) (2023)
- [Towards efficient quantum algorithms for diffusion probabilistic models](https://mlsanity.com/paper/2502.14252/) (2025)
- [Quantum Ridgelet Transform: Winning Lottery Ticket of Neural Networks with Quantum Computation](https://mlsanity.com/paper/2301.11936/) (2023)
- [Des-q: a quantum algorithm to provably speedup retraining of decision trees](https://mlsanity.com/paper/2309.09976/) (2023)
- [Quantum algorithms for SVD-based data representation and analysis](https://mlsanity.com/paper/2104.08987/) (2021)
- [Exponential Quantum Communication Advantage in Distributed Inference and Learning](https://mlsanity.com/paper/2310.07136/) (2023)
- [Spacetime-Efficient Low-Depth Quantum State Preparation with Applications](https://mlsanity.com/paper/2303.02131/) (2023)
- [Quantum Algorithms for the Pathwise Lasso](https://mlsanity.com/paper/2312.14141/) (2023)
- [Multivariate trace estimation using quantum state space linear algebra](https://mlsanity.com/paper/2405.01098/) (2024)
- [Learning low-degree quantum objects](https://mlsanity.com/paper/2405.10933/) (2024)
- [An Introduction to Quantum Computing for Statisticians and Data Scientists](https://mlsanity.com/paper/2112.06587/) (2021)
- [Efficient Quantum Algorithms for Quantum Optimal Control](https://mlsanity.com/paper/2304.02613/) (2023)
- [Quantum Speedup for Spectral Approximation of Kronecker Products](https://mlsanity.com/paper/2402.07027/) (2024)
- [Quantum enhanced rare event discovery and sampling](https://mlsanity.com/paper/2606.06316/) (2026)
- [Differentiable Quantum Computing for Large-scale Linear Control](https://mlsanity.com/paper/2411.01391/) (2024)
- [An Exponential Separation Between Quantum and Quantum-Inspired Classical Algorithms for Linear Systems](https://mlsanity.com/paper/2411.02087/) (2024)
- [Quantum Algorithm for Sparse Online Learning with Truncated Gradient Descent](https://mlsanity.com/paper/2411.03925/) (2024)
- [Trainable Quantum Neural Network for Multiclass Image Classification with the Power of Pre-trained Tree Tensor Networks](https://mlsanity.com/paper/2504.14995/) (2025)
- [Quantum Algorithms for Projection-Free Sparse Convex Optimization](https://mlsanity.com/paper/2507.08543/) (2025)
- [Quantum Sparse Recovery and Quantum Orthogonal Matching Pursuit](https://mlsanity.com/paper/2510.06925/) (2025)
- [On Encoding Matrices using Quantum Circuits](https://mlsanity.com/paper/2510.20030/) (2025)
- [Stacking the Deck: Tunable Trainability in Stacked LCUs](https://mlsanity.com/paper/2607.24686/) (2026)

## Abstract (arXiv)

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.