Quantum Computing Faces Theoretical Limit in Identifying Exotic Matter Phases
Researchers have identified a class of calculations related to complex quantum materials that would be impossible to solve, even with the most powerful quantum computers, potentially outlining the boundaries of what quantum computation can achieve.
The team, led by Thomas Schuster at the California Institute of Technology, mathematically demonstrated that determining the phase of certain exotic quantum states of matter – those beyond simple solids or liquids, like “topological” phases with unusual electrical properties – could require a quantum computer to run calculations for an impossibly long time. This scenario resembles a lab experiment demanding instrument operation for billions or trillions of years. Understanding the phases of matter is crucial for developing new materials with tailored properties.
“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,” said Schuster. While these specific phases are unlikely to be found in practical experiments, the research highlights gaps in our understanding of quantum computation and its limitations. The study also connects quantum information science, used in areas like quantum cryptography, with fundamental physics, potentially advancing both fields.
Bill Fefferman at the University of Chicago noted the findings raise broader questions about the limits of computation, suggesting that even with quantum speed-ups, some tasks will remain fundamentally intractable. The team plans to extend their analysis to more energetic, or “excited,” quantum phases, which are already known to be computationally challenging.
Researchers will continue to explore these theoretical boundaries to refine our understanding of quantum computing’s capabilities and limitations.
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:
