Hardness of recognizing phases of matter

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 $\xi$ 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 $\xi = \omega(\log n)$. Our results apply to a substantial portion of all known phases of matter, including symmetry-breaking phases and symmetry-protected topological phases for any discrete on-site symmetry group in any spatial dimension. To establish this hardness, we extend the study of pseudorandom unitaries (PRUs) to quantum systems with symmetries. We prove that symmetric PRUs exist under standard cryptographic conjectures, and can be constructed in extremely low circuit depths. We also establish hardness for systems with translation invariance and purely classical phases of matter. A key technical limitation is that the locality of the parent Hamiltonians of the states we consider is linear in $\xi$; the complexity of phase recognition for Hamiltonians with constant locality remains an important open question.