The Proof That Breaks When You Read It Twice

After an hour of squinting, you’ve just cracked that sudoku puzzle. The finished grid is proof. Anyone can scan the rows and columns and confirm you got it right, without redoing a second of your work. That’s all a proof is in this corner of computer science, a certificate that confirms an answer and not the chain of logic you’d find in a math textbook.

Some problems, though, seem to come with a proof you physically can’t write down, and the reason is wild. The only object that can serve as the proof is a quantum state, so tangled that writing it out on paper would take more symbols than there are atoms in the universe (probably). It’s now been more than twenty years that complexity theorists have wondered whether that’s truly unavoidable. Maybe there’s a clever workaround, an ordinary written proof hiding in there that nobody has spotted. Either that or maybe some truths are simply unwritable.

Four researchers finally settled it, in a 100-page paper that took best-paper honors at the 2026 Symposium on Theory of Computing in June. The answer is unwritable. For one very specific problem, no classical proof will ever do the job, and you need the quantum object itself.

Some answers you can hand over but never spell out

Start with what a quantum proof even is. For instance, if you want to show that a material is magnetic. That’s hard to confirm from the outside, unless someone hands you the material’s quantum state, the mathematical description of how its electrons are arranged. Feed that state to a quantum computer and it can check the magnetism claim in a snap. The state is the proof.

The trouble is that quantum states get monstrous, thanks to superposition, where a system holds many possible configurations at once. Even a modest system can pack in more configurations than the universe has atoms (yes, the number of atoms in space is a handy way to express the enormity of something).

It then stands to reason that this is absolutely not something you can transcribe. So for some problems, the natural proof is one of these impossible-to-write objects, and a classical proof would have to sidestep the whole tangled mess of the quantum world to exist at all.

To show that’s impossible, theorists needed one problem that clears two bars. It has to have a quantum proof. And it has to have no classical proof, not even one that a quantum computer does the checking for. That second bar is brutal, because you’re not ruling out a single clever idea. You’re ruling out every possible written proof paired with every possible quantum checking routine, all at once.

The photocopy problem

One property cracked it open, and it’s one you never think about. You can read a proof twice. A written document doesn’t vanish after someone looks at it (outside of spy movies), so a classical proof can be copied and rechecked as many times as you like. That reusability feels too obvious to be a weakness.
In the quantum world it’s a fault line.

When you measure a quantum state, you disturb it, and that disturbance scrambles whatever you’d measure next. A quantum proof is fragile in exactly this way. Look at it wrong and it changes. A classical proof, like, I don’t know, a written recipe for generating the right quantum state, has no such fragility, because anyone can run the recipe again and churn out a fresh copy whenever they want.

Mark Zhandry, a quantum cryptographer now at Stanford, noticed this by accident in 2024. Measurement disturbance sits at the heart of a lot of quantum encryption, and he suspected the same trick could separate quantum proofs from classical ones. Nobody had aimed it at this question before. His plan was a proof by contradiction. Assume a classical proof exists, then show that its comfortable, copy-it-forever reusability leads somewhere impossible.

A forensics puzzle cracked on a marathon run

The problem Zhandry picked has a great name, the spectral forrelation problem, and a simpler way to picture it. Say an object is lit from two angles, throwing two shadows. You’re handed the two shadows and asked whether a single object could really have cast both. It’s a forensics puzzle, as Chinmay Nirkhe of the University of Washington put it. Is there an object consistent with both shadows, or isn’t there?

On its own, that’s hard even for a quantum computer. But hand over the right quantum state and a quantum computer can confirm it fits both shadows in no time. That state is a clean quantum proof. A classical proof would instead be a written procedure for generating such a state, a concise document you could run and then compare against the shadows.

Zhandry showed that if that written procedure existed, you could reuse it to pull off something that should be far too hard, guessing the shape of shadows from only partial information. One step was left. He needed to prove that guessing task was so hard that no classical proof could help with it either. He couldn’t close it alone, so late in 2024 he brought in John Bostanci and Jonas Haferkamp.

Their first finished proof had a fatal flaw in the last step. That near miss only made them meaner about it. Nirkhe, who’d been circling the same problem on his own for years, joined in early 2025 with a tweak that kept the strategy but rewrote nearly every detail. What followed was nine months of overstuffed emails and flights between New York, Washington, California, and Germany. One of the breakthroughs landed when Bostanci was 20 miles into a training run in Central Park. They posted the result in mid-November, ten days after he finished his marathon.

What it truly settles

Officially, the four of them proved that two classes of problems are different, with one thing to take into account. The first class, QMA, covers everything with a quantum proof. The second, QCMA, covers problems whose proofs are classical but get checked by a quantum computer. (The names stand for quantum Merlin-Arthur and quantum-classical Merlin-Arthur, after a thought experiment starring the wizard and the king. Complexity theorists name things the way you’d expect.)

What should be taken into consideration is that this is an oracle separation. It leans on some simplifying assumptions that fence off the full space of possibilities, so it isn’t the last word for every conceivable case. It is, though, the strongest evidence in twenty years that quantum proofs really are more powerful than classical ones.

Anand Natarajan, a quantum information theorist at MIT, called it “a beautiful result” with “a bunch of fresh, new ideas” inside. Soon after the paper went up, an MIT master’s student named Andrew Huang spotted that one piece of the argument could power a second, separate oracle separation, which he and his adviser then proved. Two independent routes to the same conclusion is a good look.

None of this puts a quantum computer on your desk any sooner. The payoff is quieter, and more interesting. It’s a concrete handle on a question that’s nagged physicists for a century, which is why the quantum world refuses to be described in ordinary classical terms. Nirkhe frames computation as the yardstick for measuring that strangeness.

What drives him is the old, stubborn question underneath, the same one that fell out of quantum theory a hundred years ago, and the cryptography these techniques might enable someday is a side benefit. Some things about quantum reality can’t be flattened onto a page, and now there’s a proof of it. You just can’t read that proof twice.