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.
Given a copy of that quantum state, a quantum computer can easily check it to verify that the material is magnetic.
That means the material’s quantum state can serve as a quantum proof for this problem.
Quantum versions of many classic math problems also come with analogous quantum proofs.
In 2024, he began to suspect that a feature of quantum physics at the heart of many cryptographic schemes could also help distinguish quantum proofs from classical ones.
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 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.
“It’s a beautiful result,” said Anand Natarajan, a quantum information theorist at the Massachusetts Institute of Technology. “There’s a bunch of fresh, new ideas that come out of it.”
Show, Don’t Tell
Suppose you want to prove that a material has a particular property — say, that it’s magnetic. This is a hard problem unless you have access to the material’s quantum state: a mathematical object specifying the configuration of its electrons. Given a copy of that quantum state, a quantum computer can easily check it to verify that the material is magnetic. That means the material’s quantum state can serve as a quantum proof for this problem. Quantum versions of many classic math problems also come with analogous quantum proofs.
The trouble is that quantum states can be extraordinarily complicated, due to a phenomenon called superposition, in which many different configurations of a system can coexist in a single state. Even in a relatively simple system, the number of possible configurations that contribute to a quantum superposition can exceed the number of atoms in the universe, making it impossible to write down a classical description of the system’s quantum state.
Outside of spy movies, documents rarely self-destruct after they’re read — and fortunately for mathematicians, proofs are no exception.
For some problems, the natural proof might be one of these impossible-to-describe quantum states. A classical proof, if it existed, would have to bypass the intrinsic complexity of the quantum world completely. Researchers don’t think that’s possible.
To confirm this intuition, complexity theorists need to find a specific problem that checks two boxes: First, it must have a quantum proof. Second, it must not have a classical proof. That second step is the hard part, and it’s made harder still by the fact that problems with classical proofs might still use quantum computers for their proof-checking procedures (or algorithms). To succeed, researchers must rule out every potential combination of classical proof and quantum proof-checking algorithm.
It’s notoriously hard to prove sweeping statements that apply to all algorithms. Short of a revolution in complexity theory, a comprehensive result is out of the question. Instead, researchers have sought compelling evidence that quantum proofs are categorically different from classical ones. In 2006, they made partial progress, but they couldn’t achieve their ultimate goal: a particularly coveted form of evidence that avoids making unusual assumptions.
“That just seemed like a much, much harder problem,” said Scott Aaronson, a complexity theorist at the University of Texas, Austin, who co-authored the 2006 paper with the mathematician Greg Kuperberg.
In 2025, four researchers finally succeeded.
Quantum Forensics
The story of the new result began with Mark Zhandry, a researcher in the field of quantum cryptography, the study of how to harness quantum effects to protect sensitive information. In 2024, he began to suspect that a feature of quantum physics at the heart of many cryptographic schemes could also help distinguish quantum proofs from classical ones.
“It was sort of by accident that I started thinking about it,” said Zhandry, who’s now at Stanford University.
