  Matrices with the displacement structures of circulant, Toeplitz, and Hankel
types as well as matrices with structures generalizing these types are
omnipresent in computations of sciences and engineering. In this paper, we
present efficient and memory-reduced quantum algorithms for solving linear
systems with such structures by devising a new approach to implement the
block-encodings of these structured matrices. More specifically, by decomposing
$n\times n$ dense matrices into linear combinations of displacement matrices,
we first deduce the parameterized representations of the matrices with
displacement structures so that they can be treated similarly. With such
representations, we then construct $\epsilon$-approximate block-encodings of
these structured matrices in two different data access models, i.e., the
black-box model and the QRAM data structure model. It is shown the quantum
linear system solvers based on the proposed block-encodings provide a quadratic
speedup with respect to the dimension over classical algorithms in the
black-box model and an exponential speedup in the QRAM data structure model. In
particular, these linear system solvers subsume known results with significant
improvements and also motivate new instances where there was no specialized
quantum algorithm before. As an application, one of the quantum linear system
solvers is applied to the linear prediction of time series, which justifies the
claimed quantum speedup is achievable for problems of practical interest.
