Scientists Discover a Problem Too Complex for Even Quantum Computers to Solve

Here’s what you’ll learn when you read this story:

• Quantum computers can outperform even the best classical supercomputers thanks to quantum entanglement and superposition, but even they can’t solve some problems.
• A new preprint study shows how quantum computers can’t solve a “nightmare” problem of determining quantum phases of matter.
• This limitation of quantum computers might point to a limit on physical observation itself.

Quantum computing is often portrayed as the “superman” of the information age. Powered by entangled qubits in superposition, these high-tech machines can perform many calculations at once, drastically improving computing time when compared to classic supercomputers. Just last week, for instance, Google announced that the company’s quantum computer could run algorithms some 13,000 times faster than its classical counterpart.

But even Superman has his kryptonite—and the same can be said for quantum computers.

Usually, these weaknesses play out on the engineering side of things. For one, quantum computers are extremely susceptible to decoherence and require robust error-correction to even be usable. This is the chief reason why today’s quantum computers can barely inch past the 1,000-qubit mark, and current estimates suggest that a 20 million-qubit quantum computer would be needed to break classical cryptography.

But a new study, recently uploaded to the preprint server arXiv, explores the computational limits of these machines—possibly probing the very limit of physical observation itself. In other words, there are some problems that even quantum computers can’t solve, and it could be that these questions are fundamentally unsolvable.

Although not all examples of determining a quantum phase are considered impossible, New Scientist reports that some questions would require quantum computers to operate for impossibly long times—potentially billions of trillions of years.