A problem that takes quantum computers an unfathomable amount of time to solve

October 31, 2025 report by Krystal Kasal, Phys.org edited by Stephanie Baum, reviewed by Robert Egan This article has been reviewed according to Science X's editorial process and policies. Editors have highlighted the following attributes while ensuring the content's credibility: fact-checked preprint trusted source proofread It's a well-known fact that quantum calculations are difficult, but one would think that quantum computers would facilitate the process. In most cases, this is true.Quantum bits, or qubits, use quantum phenomena, like superposition and entanglement, to process many possibilities simultaneously. This allows for exponentially faster computing for complex problems. However, Thomas Schuster, of California Institute of Technology, and his research team have given quantum computers a problem that even they can't solve in a reasonable amount of time—recognizing phases of matter of unknown quantum states.The team's research can be found in a paper published on the arXiv preprint server.In the everyday world, distinguishing between a liquid phase and a gas phase, for example, is fairly simple, but unsurprisingly, things get much more complicated in the quantum world. Quantum phases of matter occur at absolute zero temperature and quantum mechanics dictate their properties and behavior, which are driven by quantum fluctuations. Quantum phases can be categorized by their properties, such as topological phases and non-equilibrium phases."Quantum mechanics has unveiled entirely new phases of matter, including topological order and symmetry-protected topological phases. The ability to identify and characterize these diverse phases of matter is of fundamental interest across physics and information science and crucial for advancing quantum technologies," say the study authors.Some of these phases, like topological order, are known to be hard to recognize computationally. The correlation length (range), defined as a measure of the distance over which the properties of a quantum many-body system are correlated, appears to increase this recognition difficulty as it increases. The study demonstrates that computational time grows exponentially with the correlation range, represented as ξ, and becomes a super-polynomial in system size n when ξ = ω(log n). This results in unfathomable computation times, making the calculations essentially impossible to solve.To determine how a quantum computer would fare at the task, the team came up with a mathematical scenario where a quantum computer is presented with information about a quantum state of an object and must identify the phase. They found that recognizing the phase of matter is quantum computationally hard for a wide class of phases, including symmetry-breaking and symmetry-protected topological (SPT) phases. They found that this extends even to classical phases, and to both pure and mixed states."At a conceptual level, our results should be viewed as a worst-case statement: There exist classical and quantum states whose phase of matter is precisely defined, yet is impossible to recognize in any efficient quantum experiment," the study authors write.Earlier this year, Schuster and colleagues published a paper about randomness and quantum computers. In the paper, they hinted at a deeper meaning in their research, stating, "Our results show that several fundamental physical properties—evolution time, phases of matter, and causal structure— are probably hard to learn through conventional quantum experiments. This raises profound questions about the nature of physical observation itself."This study seems to lean toward an understanding that some properties of the universe have limits that may prevent us from ever fully understanding them. Still, scientists will keep trying. Future work that might build upon this study might involve exploring which physical properties make phase recognition easy in practice, despite worst-case hardness, or investigating whether phase recognition is feasible for ground states of constant-local Hamiltonians. Written for you by our author Krystal Kasal, edited by Stephanie Baum, and fact-checked and reviewed by Robert Egan—this article is the result of careful human work. We rely on readers like you to keep independent science journalism alive. If this reporting matters to you, please consider a donation (especially monthly). You'll get an ad-free account as a thank-you. More information: Thomas Schuster et al, Hardness of recognizing phases of matter, arXiv (2025). DOI: 10.48550/arxiv.2510.08503 Journal information: arXiv © 2025 Science X Network Nov 1, 20250Nov 1, 20250Nov 1, 20250Oct 31, 20253Oct 31, 202502 hours ago22 hours ago22 hours agoNov 1, 2025Nov 1, 2025Nov 1, 2025Nov 1, 2025Nov 1, 2025Nov 1, 2025Nov 1, 2025Sep 10, 2025Aug 12, 2025Jul 4, 2025Aug 22, 2025Aug 11, 2020Dec 13, 2023Oct 31, 2025Oct 31, 2025Oct 30, 2025Oct 30, 2025Oct 30, 2025Oct 30, 2025