  Toeplitz and Hankel matrices have been a subject of intense interest in a
wide range of science and engineering related applications. In this paper, we
show that quantum circuits can efficiently implement sparse or Fourier-sparse
Toeplitz and Hankel matrices. This provides an essential ingredient for solving
many physical problems with Toeplitz or Hankel symmetry in the quantum setting
with deterministic queries.
