Some problems are too difficult even for quantum computers
Yaroslav Kushta/Getty Images
Researchers have identified a “nightmare scenario” calculation involving exotic types of quantum matter that is impossible to solve even for a very efficient quantum computer.
Without taking into account the complexity of quantum states of matter, determining the phase of a material can be relatively simple. Take water for example: it is easy to determine whether it is in a solid or liquid phase. However, the quantum version of this problem may be much more difficult. Thomas Schuster from the California Institute of Technology and his colleagues have shown that identifying the quantum phases of matter may be too difficult even for quantum computers.
They mathematically analyzed a scenario in which a quantum computer is given a set of measurements of an object's quantum state and must identify its phase. Schuster says it's not always an impossible task, but his team has demonstrated a significant portion of quantum phases of matter – more exotic relatives of liquid water and icesuch as “topological” phases in which odd electrical currents flow—a quantum computer may have to perform calculations for incredibly long periods of time. The situation is similar to the worst version of a laboratory experiment, where determining the properties of a sample would require keeping the instrument on for billions or trillions of years.
This does not make quantum computers virtually obsolete for this task. Schuster says these phases are unlikely to show up in actual experiments with materials or quantum computers—they are more diagnostic of what is currently missing in our understanding of quantum computing than an immediate practical threat. “They're like a nightmare scenario that would be very bad if it showed up. It probably won't, but we need to understand it better,” he says.
Bill Fefferman at the University of Chicago in Illinois says the course opens intriguing questions about what computers can do. “Perhaps this says something about the limitations of computing more broadly: despite significant speedups on some specific problems, there will always be problems that are still too complex even for efficient quantum computers,” he says.
From a mathematical perspective, the new research connects aspects of quantum information science that are used in quantum cryptography with ideas fundamental to the physics of matter, so it could also help advance both, he says.
Going forward, the team wants to expand their analysis to more energetic, or excited, quantum phases of matter, which are notoriously difficult to calculate more broadly.
Topics:
