Hardness of recognizing phases of matter

Thomas Schuster, Dominik S. Kufel, Norman Y. Yao, Hsin-Yuan HuangarXiv 2025 · DOI · arXiv

Abstract

This paper establishes that identifying the phase of matter of an unknown quantum state is a computationally hard problem. By leveraging the concept of Symmetric Pseudorandom Unitaries (PRUs), the authors demonstrate that the time required to recognize a phase grows exponentially with the state's correlation range $\xi$. This "exponential wall" suggests that for many complex systems, identifying physical phases is practically impossible for efficient algorithms, even when the states are generated by low-depth circuits. The results have significant implications for both quantum information theory and experimental condensed matter physics.

Introduction

In condensed matter physics, phases of matter—such as magnets, superconductors, or topological insulators—serve as the primary framework for organizing our understanding of complex many-body systems. A fundamental task for researchers is phase recognition: determining which phase a given quantum state belongs to. While various tools exist, such as measuring order parameters or entanglement signatures, their efficiency typically degrades as the correlation range ($\xi$) of the state increases.

The challenge of phase recognition and the indistinguishability of scrambled states.

This research addresses whether this "exponential wall" is a temporary algorithmic hurdle or a fundamental limit of computational complexity. The authors prove that the latter is true, showing that distinguishing between phases is a "hard" problem in the worst-case scenario. This hardness is rooted in the ability of low-depth quantum circuits to scramble identifying signatures into complex, many-body correlations that no efficient experiment can detect.

Methods

The researchers establish this hardness by bridging quantum many-body physics with cryptography, primarily through the construction of Symmetric Pseudorandom Unitaries (PRUs). A PRU is a quantum circuit that is mathematically indistinguishable from a completely random transformation to any observer with limited computational resources.

Technical construction of symmetric PRUs and their assembly into shallow circuits.

The methodology involves several key steps:

  1. Symmetric PRU Construction: The authors extended the PRU concept to systems with discrete on-site or translation symmetries, showing that these operators can be represented as block-diagonal matrices in the appropriate basis.
  2. The Gluing Lemma: A new mathematical lemma was proven, demonstrating that small symmetric PRUs can be "glued" together into a large, system-wide PRU using shallow circuits.
  3. State Scrambling: To prove hardness, the authors take a "fixed point" state (a clear example of a phase) and apply a low-depth symmetric PRU. This process preserves the phase but hides its signatures (like magnetization) across $O(\xi)$-body operators.
  4. LWE Conjecture: The proof's security foundation relies on the "Learning With Errors" (LWE) conjecture, a staple of post-quantum cryptography.

Key Results

The study yields several groundbreaking results regarding the complexity of phase recognition:

  • Exponential Hardness: Theorem 1 proves that distinguishing any quantum phase (e.g., symmetry-breaking, SPT, or topological) from a trivial phase requires computational time that scales exponentially with the correlation range $\xi$.
  • Super-polynomial Complexity: If the correlation range grows even slightly with system size ($\xi = \omega(\log n)$), the recognition time becomes super-polynomial, effectively exceeding the capabilities of any efficient quantum computer.
  • Plausibility of Hard States: The authors demonstrated that these hard-to-recognize states can be created using extremely shallow circuits, suggesting they could plausibly exist in nature or be engineered in near-term quantum devices.
  • Robustness and Extensions: The hardness results were successfully extended to mixed states (accounting for noise or temperature) and translation-invariant systems. Additionally, the authors showed that recognizing classical phases of matter is also computationally hard when correlations are long-ranged.

Discussion and Future Work

While this work provides a rigorous "worst-case" lower bound, it opens several new avenues for research. One technical limitation is that the parent Hamiltonians for these states have a locality that grows with $\xi$, whereas most natural Hamiltonians are 2-local. Whether phase recognition remains hard for states governed by strictly constant-local Hamiltonians is an open question.

Furthermore, the current results apply to discrete symmetries. Extending this to continuous symmetries (like $U(1)$) remains challenging due to the difficulty of shuffling charges with low-depth circuits. Finally, the authors note that while phase recognition is hard in the worst case, it is often easy in practice. Identifying the specific properties of "natural" states—such as spectral gaps—that make them easier to identify than the scrambled states constructed here is a primary goal for future investigation.

Summary updated

BibTeX
@misc{schuster2025hardness,
  author = {Thomas Schuster and Dominik S. Kufel and Norman Y. Yao and Hsin-Yuan Huang},
  title = {{Hardness of recognizing phases of matter}},
  year = {2025},
  eprint = {2510.08503},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2510.08503},
}
Figure