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

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.

What are phases of matter in quantum states?

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.

Impossible tasks

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.

The implications of unsolvability

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.

© 2025 Science X Network