Projected Entangled Pair States (PEPS) constitute an important family of Tensor Networks, since they approximate well ground states and thermal states of quantum many body systems. PEPS come together with a parent Hamiltonian. In this talk I will focus on the problem of estimating its spectral gap, i.e. the difference between the two smallest eigenvalues. I will introduce the problem and motivate it from several perspectives. Then I will show some new results, and an application to bound the convergence time of quantum Gibbs-sampling algorithms motivated by the study of self-correcting quantum memories.