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.
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.
The methodology involves several key steps:
- 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.
- 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.
- 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.
- 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