Challenging Calculations: Quantum Computers May Struggle with ‘Nightmare’ Problems

Researchers have uncovered a “nightmare scenario” computation tied to a rare form of quantum material that remains unsolvable, even with the most advanced quantum computers.

In contrast to the simpler task of determining the phase of standard matter, such as identifying whether water is in a solid or liquid state, the quantum equivalent can prove exceedingly challenging. Thomas Schuster and his team at the California Institute of Technology have demonstrated that identifying the quantum phase of matter can be notably difficult, even for quantum machines.

They mathematically examined a scenario in which a quantum computer receives a set of measurements regarding the quantum state of an object and must determine its phase. Schuster mentioned that this is not necessarily an impossible task, but his team has shown that a considerable number of quantum phases of matter—such as the complex interactions between liquid water and ice, including unusual “topological” phases that exhibit strange electrical currents—might necessitate quantum computers to perform computations over extremely protracted periods. This situation mirrors a worst-case scenario in laboratory settings, where instruments may need to operate for billions or even trillions of years to discern the characteristics of a sample.

This doesn’t imply that quantum computers are rendered obsolete for this analysis. As Schuster noted, these phases are unlikely to manifest in actual experiments involving materials or quantum systems, serving more as an indicator of our current limitations in understanding quantum computers than posing an immediate practical concern. “They’re like nightmare scenarios. It would be quite unfortunate if such a case arose. It probably won’t happen, but we need to improve our comprehension,” he stated.

Bill Fefferman from the University of Chicago raised intriguing questions regarding the overall capabilities of computers. “This might illuminate the broader limits of computation: while substantial speed improvements have been realized for specific tasks, there will inevitably be challenges that remain too daunting, even for efficient quantum computers,” he asserted.

Mathematically, he explained, this new research merges concepts from quantum information science employed in quantum cryptography with foundational principles from materials physics, potentially aiding progress in both domains.

Looking ahead, the researchers aspire to broaden their analysis to encompass more energetic or excited quantum phases of matter, which are recognized as challenging for wider calculations.