  The superconformal index of the $\mathcal{N}=4$ $SU(N)$ supersymmetric
Yang-Mills theory counts the 1/16-BPS states in this theory, and has been used
via the AdS/CFT correspondence to count black hole microstates of 1/16-BPS
black holes. On one hand, this index may be related to the Euclidean partition
function of the theory on $S^3\times S^1$ with complex chemical potentials,
which maps by the AdS/CFT correspondence to a sum over Euclidean gravity
solutions. On the other hand, the index may be expressed as a sum over
solutions to Bethe Ansatz Equations (BAEs). We show that the known solutions to
the BAEs that have a good large $N$ limit, for the case of equal chemical
potentials for the two angular momenta, have a one-to-one mapping to (complex)
Euclidean black hole solutions on the gravity side. This mapping captures both
the leading contribution from the classical gravity action (of order $N^2$), as
well as non-perturbative corrections in $1/N$, which on the gravity side are
related to wrapped D3-branes. Some of the BA solutions map to orbifolds of the
standard Euclidean black hole solutions (that obey exactly the same boundary
conditions as the other solutions). A priori there are many more gravitational
solutions than Bethe Ansatz solutions, but we show that by considering the
non-perturbative effects, the extra solutions are ruled out, leading to a
precise match between the solutions on both sides.
