  In the field of sampling algorithms, MCMC (Markov Chain Monte Carlo) methods
are widely used when direct sampling is not possible. However, multimodality of
target distributions often leads to slow convergence and mixing. One common
solution is parallel tempering. Though highly effective in practice,
theoretical guarantees on its performance are limited. In this paper, we
present a new lower bound for parallel tempering on the spectral gap that has a
polynomial dependence on all parameters except $\log L$, where $(L + 1)$ is the
number of levels. This improves the best existing bound which depends
exponentially on the number of modes. Moreover, we complement our result with a
hypothetical upper bound on spectral gap that has an exponential dependence on
$\log L$, which shows that, in some sense, our bound is tight.
