  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.
