  Entanglement is at the heart of most quantum information tasks, and therefore
considerable effort has been made to find methods of deciding the entanglement
content of a given bipartite quantum state. Here, we prove a fundamental
limitation to deciding if an unknown state is entangled or not: we show that
any quantum measurement which can answer this question necessarily gives enough
information to identify the state completely. Therefore, only prior information
regarding the state can make entanglement detection less expensive than full
state tomography in terms of the demanded quantum resources. We also extend our
treatment to other classes of correlated states by considering the problem of
deciding if a state is NPT, discordant, or fully classically correlated.
Remarkably, only the question related to quantum discord can be answered
without resorting to full state tomography.
