We prove that recognizing the phase of matter of an unknown quantum state is quantum computationally hard. More specifically, we show that the quantum computational time of any phase recognition algorithm must grow exponentially in the range of correlations ξ of the unknown state. This exponential growth renders the problem practically infeasible for even moderate correlation ranges, and leads to super-polynomial quantum computational time in the system size n whenever ξ = ω(log n). Our results ...