  In recent years, the entanglement spectra of quantum states have been
identified to be highly valuable for improving our understanding on many
problems in quantum physics, such as classification of topological phases,
symmetry-breaking phases, and eigenstate thermalization, etc. However, it
remains a major challenge to fully characterize the entanglement spectrum of a
given quantum state. An outstanding problem is whether the difficulty is
intrinsically technical or fundamental? Here using the tools in computational
complexity, we perform a rigorous analysis to pin down the counting complexity
of entanglement spectra of (i) states generated by polynomial-time quantum
circuits, (ii) ground states of gapped 5-local Hamiltonians, and (iii)
projected entangled-pair states (PEPS). We prove that despite the state
complexity, the problems of counting the number of sizable elements in the
entanglement spectra all belong to the class $\mathsf{\# P}$-complete, which is
as hard as calculating the partition functions of Ising models. Our result
suggests that the absence of an efficient method for solving the problem is
fundamental in nature, from the point of view of computational complexity
theory.
