Post

More than 30 years ago, researchers discovered that hypothetical computers based on the laws of quantum physics would be able to rapidly solve difficult math problems. Ever since then, they’ve sought to pinpoint cases where quantum computers are more powerful than their ordinary “classical” cousins. For nearly as long, a small band of computer scientists has pursued a related question that gets… Source

More than 30 years ago, researchers discovered that hypothetical computers based on the laws of quantum physics would be able to rapidly solve difficult math problems. Ever since then, they’ve sought to pinpoint cases where quantum computers are more powerful than their ordinary “classical” cousins. For nearly as long, a small band of computer scientists has pursued a related question that gets…

Source

For nearly as long, a small band of computer scientists has pursued a related question that gets less attention: Are proofs that exploit quantum physics also more powerful than classical proofs?

In this context, a “proof” is not a series of logical statements that leads to a theorem, as it is in math. Instead, it’s a certificate confirming that a problem has been solved correctly. For example, if you solve a tricky sudoku puzzle, your solution itself is a proof. A computer can easily scan the grid and verify that it’s correct.

Researchers have identified problems where this proof-checking process likely requires a quantum computer. For some of these problems, the proofs themselves are still classical — ordinary written documents. But for other problems, the only known proofs are fundamentally different mathematical objects called quantum states.

Researchers want to understand whether such exotic quantum proofs are necessary. In those cases where a problem appears to require a quantum proof, is it really impossible to come up with an ordinary classical proof? Or is there some clever way to replace the quantum proof with a classical one, and researchers just haven’t discovered it?

For over 20 years, this question has ranked among the biggest open problems in the field of quantum complexity theory, which studies the intrinsic hardness of quantum problems. Now, in a 100-page paper that received a best-paper award at the 2026 Symposium on Theory of Computing in June, four researchers have finally resolved it — or at least, they’ve come as close to a comprehensive answer as anyone expects to get. They identified a special computational problem that truly requires a quantum proof. No classical proof will do the trick.