2025/10/09 by Thomas Schuster, Schuster, Thomas, Dominik Kufel +5 · 3 citations
Computer Science · Physics and Astronomy · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Information Theory (cs.IT) #Mathematical Physics (math-ph) #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #Quantum many-body systems #Strongly Correlated Electrons (cond-mat.str-el)
paper · pdf · doi:10.48550/arxiv.2510.08503
openalex publication_date 2025/10/09 · openalex created_date 2025/10/11 · openalex updated_date 2026/07/28
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 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 ξ; the complexity of phase recognition for Hamiltonians with constant locality remains an important open question.