  A quasi-Toeplitz $M$-matrix $A$ is an infinite $M$-matrix that can be written
as the sum of a semi-infinite Toeplitz matrix and a correction matrix. This
paper is concerned with computing the square root of invertible quasi-Toeplitz
$M$-matrices which preserves the quasi-Toeplitz structure. We show that the
Toeplitz part of the square root can be easily computed through
evaluation/interpolation at the $m$ roots of unity. This advantage allows to
propose algorithms solely for the computation of correction part, whence we
propose a fixed-point iteration and a structure-preserving doubling algorithm.
Additionally, we show that the correction part can be approximated by solving a
nonlinear matrix equation with coefficients of finite size followed by
extending the solution to infinity. Numerical experiments showing the
efficiency of the proposed algorithms are performed.
