‘Nightmare’ calculation may be too tricky for even quantum computers

Researchers have uncovered a “nightmare scenario” involving calculations of exotic types of quantum matter that would be unsolvable, even for the most advanced quantum computers.

In contrast to the straightforward nature of identifying the phases of conventional materials like water, the challenge becomes significantly more intricate with their quantum counterparts. A group led by Thomas Schuster at the California Institute of Technology has demonstrated that classifying quantum phases of matter can reach a point of undue complexity, even for quantum computers.

In their mathematical exploration, Schuster and his team examined a case where a quantum computer must deduce the phase of a quantum state based on a series of measurements. According to Schuster, while not all scenarios pose insurmountable challenges, they established that for many exotic quantum phases—akin to unique forms of water and ice, like “topological” phases that behave unpredictably—computational time required may become astronomically long. This situation is reminiscent of an extreme laboratory experiment where the assessment of sample properties would necessitate billions or trillions of years.

This discovery does not render quantum computers ineffective for this analysis. Schuster emphasizes that these rare quantum phases are unlikely to manifest in real-world experiments and serve more as indicators of gaps in our current understanding of quantum computation rather than immediate practical concerns. “They represent a worst-case scenario that could be problematic if encountered, though it likely wouldn’t happen. Yet, it is crucial to comprehend it better,” he notes.

According to Bill Fefferman from the University of Chicago, this research raises compelling questions about the fundamental limits of computation. “This might suggest that, despite achieving significant efficiency gains on specific tasks, there are always problems that remain too challenging even for proficient quantum computers,” he remarks.

The new findings, through their mathematical connections, link aspects of quantum information science relevant to quantum cryptography and principles foundational to the physics of matter, potentially fostering advancements in both fields, he adds.

Looking ahead, the research group aims to extend their study to include more energized and excited quantum phases, known for their inherent computational challenges.