We introduce the notion of the relaxation time for noisy quantum maps on the
2d-dimensional torus - a generalization of previously studied dissipation time. We show
that relaxation time is sensitive to the chaotic behavior of the corresponding classical
system if one simultaneously considers the semiclassical limit ($\hbar$ -> 0) together
with the limit of small noise strength ($\ep$ -> 0). Focusing on quantized smooth Anosov
maps, we exhibit a semiclassical regime $\hbar<\ep^{E}$ << 1 (where E>1) in
which classical and quantum relaxation times share the same asymptotics: in this regime, a
quantized Anosov map relaxes to equilibrium fast, as the classical map does. As an
intermediate result, we obtain rigorous estimates of the quantum-classical correspondence
for noisy maps on the torus, up to times logarithmic in $\hbar^{-1}$. On the other hand, we
show that in the ``quantum regime'' $\ep$ << $\hbar$ << 1, quantum and
classical relaxation times behave very differently. In the special case of ergodic toral
symplectomorphisms (generalized ``Arnold's cat'' maps), we obtain the exact asymptotics of
the quantum relaxation time and precise the regime of correspondence between quantum and
classical relaxations.