Some problems are too difficult even for quantum computers
Yaroslav Koshta/Getty Images
The researchers identified a “nightmare scenario” calculation involving exotic types of quantum matter that would be impossible to solve, even for a very efficient quantum computer.
Determining the phase of a material can be relatively simple, without the complexity of the quantum states of matter. Take water, for example – it’s straightforward to tell whether it’s in a solid or liquid phase. However, the quantum version of this task may be much more difficult. Thomas Schuster and his colleagues at the California Institute of Technology have now demonstrated that identifying the quantum phases of matter can be difficult even for quantum computers.
They mathematically analyzed a scenario where a quantum computer is presented with a set of measurements about the quantum state of an object and has to identify its phase. Schuster says it’s not always an impossible problem, but his team proved for a substantial fraction of phases of matter — the more exotic relatives of liquid water and ice, such as “topological” phases that contain strange electric currents — a quantum computer could need impossibly long computations. The situation is like the worst version of a lab experiment where an instrument has to be kept for billions or trillions of years to identify the properties of the sample.
This makes a quantum computer practically obsolete for this task. Schuster says these steps are unlikely to appear in actual experiments with materials or quantum computers — they’re more diagnostic where our current understanding of quantum computing lacks more than a practical threat. “They’re like a nightmare scenario that would be very bad if it shows up. It might not show up, but we should understand it better,” he says.
This course of study opens up interesting questions about what computers can do in general, says Bill Pfeifferman at the University of Chicago in Illinois. “This is saying something more broadly about the limits of computation, that despite dramatic speed-ups for certain tasks, there will always be tasks that are too difficult for even efficient quantum computers.”
Mathematically, the new study combines aspects of quantum information science that are used in quantum cryptography with fundamental theories of matter physics, so it could also help advance both.
Moving forward, the team wants to extend their analysis to quantum phases of matter that are more energetic, or excited, which are harder to compute on an even larger scale.
Topics:
