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.
“They’re like a nightmare scenario that would be very bad if it appears,” Schuster tells New Scientist. “It probably doesn’t appear, but we should understand it better.”
To read more, click here.