Some problems are too hard for even quantum computers
Yaroslav Kushta/Getty Images
Researchers have identified a “nightmare scenario” calculation related to exotic types of quantum matter that would be impossible to solve, even for a very efficient quantum computer.
Without the complexity of quantum states of matter, determining the phase of a material can be relatively simple. Take water, for example – it is straightforward to tell whether it is in a solid or liquid phase. The quantum version of this task, however, can be a lot more daunting. Thomas Schuster at the California Institute of Technology and his colleagues have now proven identifying quantum phases of matter can get too difficult even for quantum computers.
They mathematically analysed a scenario where a quantum computer is presented with a set of measurements about a quantum state of an object and has to identify its phase. Schuster says this is not always an impossible problem, but his team proved for a substantial portion of quantum phases of matter – the more exotic relatives of liquid water and ice, such as “topological” phases that feature odd electric currents – a quantum computer may need to calculate for an impossibly long time. The situation is like the worst version of a lab experiment where identifying the properties of a sample would require keeping an instrument on for billions or trillions of years.
This doesn’t 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 are more of a diagnostic for where our understanding of quantum computation is currently lacking than an imminent practical threat. “They’re like a nightmare scenario that would be very bad if it appears. It probably doesn’t appear, but we should understand it better,” he says.
Bill Fefferman at the University of Chicago in Illinois says this course of study opens intriguing questions about what computers can do in general. “This may be saying something about the limits of computation more broadly, that despite attaining dramatic speed-ups for certain specific tasks, there will always be tasks that are still too hard even for efficient quantum computers,” he says.
Mathematically, the new study connects facets 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 quantum phases of matter that are more energetic, or excited, which are known to be hard to compute even more broadly.
Topics:
