‘Nightmare’ computation may be too difficult even for quantum computers

Researchers have identified a “nightmare scenario” calculation related to exotic types of quantum matter that would be impossible to solve even for a highly efficient quantum computer.

Without the complexity of the quantum states of matter, it can be relatively simple to determine the phase of a material. Take water for example – it is straightforward to tell whether it is in solid or liquid phase. However, the quantum version of this task can be much more daunting. Thomas Schuster at the California Institute of Technology and his colleagues have now proven that identifying quantum phases of matter can be too difficult even for quantum computers.

They mathematically analyzed a scenario where a quantum computer is presented with a set of measurements about a quantum state of an object and must identify its phase. Schuster says this isn’t always an impossible problem, but his team proved for a significant fraction of quantum phases of matter—the more exotic relatives of liquid water and ice, such as “topological” phases that have unequal electrical currents—a quantum computer might have to compute for an impossibly long time. The situation is like the worst version of a laboratory experiment, where identifying the properties of a sample would require keeping an instrument on for billions or trillions of years.

This does not make quantum computers practically obsolete for this task. Schuster says these phases are unlikely to show up in actual experiments with materials or quantum computers—they’re more a diagnosis of where our understanding of quantum computing is currently lacking than an imminent practical threat. “They’re like a nightmare scenario that would be very bad if it shows up. It probably won’t show up, but we should understand it better,” he says.

Bill Fefferman of the University of Chicago in Illinois says this course of study opens up exciting questions about what computers can do in general. “This perhaps says something about the limits of computation more broadly, that despite achieving dramatic speedups for certain specific tasks, there will always be tasks that are still too difficult even for efficient quantum computers,” he says.

Mathematically, the new study connects facets of quantum information science used in quantum cryptography with ideas fundamental to the physics of matter, so it may also help advance both, he says.

Going forward, the team wants to extend their analysis to quantum phases of matter that are more energetic, or excited, which are known to be difficult to calculate even more broadly.