  In 2D chiral p-wave superconductors, the zero-energy Majorana fermion
excitations trapped at vortex cores follow non-Abelian statistics which can be
potentially exploited to build a topological quantum computer. The Majorana
states are protected from the thermal effects by the mini-gap,
$\Delta^2/\epsilon_F$ ($\Delta$:bulk gap, $\epsilon_F$: Fermi energy), which is
the excitation gap to the higher-energy, non-topological, bound states in the
vortex cores. Robustness to thermal effects is guaranteed only when $T \ll
\Delta^2/\epsilon_F \sim 0.1$ mK, which is a very severe experimental
constraint. Here we show that when s-wave superconductivity is
proximity-induced on the surface of a topological insulator or a
spin-orbit-coupled semiconductor, as has been recently suggested, the mini-gaps
of the resultant non-Abelian states can be orders of magnitude larger than in a
chiral p-wave superconductor. Specifically, for interfaces with high barrier
transparencies, the mini-gap can be as high as $\sim \Delta \gg
\Delta^2/\epsilon_F $, where $\Delta$ is the bulk gap of the s-wave
superconductor responsible for the proximity effect.
