⚛️ Even quantum computers cannot solve this computational problem

Quantum computers promise to revolutionize our ability to solve problems thanks to their unique properties. However, a team of researchers has just discovered a computable task that appears impossible to solve within a reasonable timeframe even for these machines.

Quantum bits, or qubits, exploit particular physical phenomena like superposition and entanglement to simultaneously process many possibilities. This ability allows them to perform calculations exponentially faster than classical computers for certain applications.


However, Thomas Schuster from the California Institute of Technology and his team have identified a specific problem that even quantum computers struggle to solve within a reasonable time.

The problem in question

In the quantum world, matter can exist in different states called phases, which manifest at extremely low temperatures close to absolute zero. These phases are governed by the laws of quantum mechanics and exhibit surprising properties, such as topological phases where matter organizes according to particular geometric patterns.

The researchers explain that quantum mechanics has revealed entirely new phases of matter, whose identification and characterization are of fundamental interest to physics and information sciences.

The study demonstrates that the computation time required to recognize these phases increases exponentially with the correlation length, a measure that describes the distance over which the properties of a quantum system remain linked. A problem that seems designed to be solved by a quantum computer.

Yet when this length exceeds certain values, the computation time becomes so significant that the task becomes practically impossible to solve, even for the most powerful quantum computers. This difficulty applies to a broad class of quantum phases.

These results show that certain fundamental properties of the Universe could possess intrinsic limits in the computational domain.

The researchers emphasize that their work should be considered as a worst-case study: there exist quantum states whose phase is perfectly defined, but impossible to recognize efficiently by experimental means, both conventional and quantum. This discovery opens new perspectives on the very nature of physical observation and its potential limitations.