US team finds problems that even quantum computers can't crack

Researchers at Caltech, led by Thomas Schuster, have identified intrinsic limits in quantum computing’s ability to efficiently solve certain complex problems, specifically in determining the phases of matter from unknown quantum states. While quantum computers leverage qubits to process vast possibilities simultaneously, some quantum phase recognition tasks remain beyond their reach. The study highlights that as the correlation length (ξ)—which measures how far quantum system properties influence each other—increases, the computational time required to identify phases grows exponentially. When ξ grows faster than the logarithm of the system size, the problem becomes super-polynomially hard, making it practically unsolvable within reasonable timeframes, even by quantum machines. This finding underscores fundamental constraints in probing and understanding complex quantum phases, such as topological order and symmetry-protected topological phases, which are crucial for both theoretical physics and advancing quantum technologies. The researchers also point out that certain quantum states have well-defined phases that no efficient quantum experiment can reliably identify, revealing inherent limits in measurement and observation.