We prove that given the ability to make entangled measurements on at most $k$
replicas of an $n$-qubit state $rho$ simultaneously, there is a property of
$rho$ which requires at least order $2^n / k^2$ measurements to learn.
However, the same property only requires one measurement to learn if we can
make an entangled measurement over a number of replicas polynomial in $k, n$.
Because the above holds for each positive integer $k$, we obtain a hierarchy of
tasks necessitating progressively more replicas to be performed efficiently. We
introduce a powerful proof technique to establish our results, and also use
this to provide new bounds for testing the mixedness of a quantum state.