While calculating complexity may seem like pure math, there is a deep connection between computers and the physics that governs their resources – time and memory. Complexity theory, indeed, is not just pure math but the study of math constrained by reality. If you change the rules of reality, you change the boundaries of what is possible. And changing the laws of physics at play in computer hardware, will drastically change what a computer can do!
Now, a groundbreaking new paper from PhD candidate Junqiao (Randy) Lin, shows that even within quantum mechanics, choosing a different mathematical model for quantum entanglement completely alters the boundaries of what is knowable. This fundamental result has earned Lin the prestigious Best Student Paper award at STOC 2026, a premier conference in theoretical computer science. Lin is a researcher at QuSoft, the Dutch research center for quantum software and technology launched by CWI and UvA.
Detecting the truth
To understand the scientific results of the paper we have to look at a concept called interactive proof systems. Imagine you are a journalist who is going to moderate a debate between two brilliant but untrustworthy scientists who claim they have solved an impossible math problem. You don’t have the means to check their calculations yourself, your only chance to know if they are saying the truth is to converse with them during the panel discussion.
In complexity theory, you are the verifier (a computer with limited power), and the scientists are the provers (all-powerful but dishonest systems). By asking them sharp, strategic questions to get them to fact-check each other, you can use their own interactions to catch them in a lie or figure out if their claim is actually true. Even though they are infinitely smarter than you!
This model of verifying truth through conversation dates back to a foundational 1990 result by computer scientists László Babai, Lance Fortnow, and Carsten Lund. They proved a class known as MIP = NEXP. In simple terms, they showed that by cross-examining multiple isolated provers, a humble verifier could suddenly confirm the solutions to incredibly massive, exponential problems; problems far more powerful than ordinary, efficient verification.
Quantum Entanglement enters the picture
For thirty years, researchers assumed these all-powerful provers were kept in completely isolated, classical rooms. But in 2020, a landmark paper shook the scientific world by introducing quantum mechanics into the equation.
If you give the provers shared quantum entanglement – a bizarre physical phenomenon where two particles become deeply linked so that what happens to one instantly affects the other, even across the universe – they can synchronize their answers in ways that are impossible in a classical world. This creates a new complexity class called MIP*.
Two mathematical descriptions of Quantum Entanglement
Because quantum entanglement is so strange, mathematicians and physicists have spent decades trying to write down the exact rules for it. Over time, two different mathematical frameworks emerged to describe these quantum correlations:
- The Tensor Product Model: This assumes the two entangled systems are distinct and physically separated in space. It is the conventional model used to build quantum computers today.
- The Commuting-Operator Model: This is a broader, more general mathematical framework. Instead of worrying about physical separation, it focuses on the order of operations—ensuring that actions performed on one system do not interfere with the other.
The 2020 breakthrough: MIP* = RE, used the first framework (the tensor product model). It proved that when provers use this kind of entanglement, the verifier’s power increases dramatically. Suddenly, a limited computer can verify statements that are “recursively enumerable” (RE). This means the computer can always confirm if a statement is true, even if it might run forever if the statement is false. The ultimate example of this is Alan Turing’s famous Halting Problem—detecting whether a computer program will loop infinitely or eventually stop – which was previously thought to be uncomputable.
This realization didn’t just alter computer science; it triggered a cascade through other fields, disproving major long-standing puzzles like Connes’ embedding theorem in operator algebra and Tsirelson’s problem in quantum mechanics.
Flipping the Quantum description: MIP^co = coRE
This is exactly where Lin’s award-winning paper comes in. Instead of using the standard tensor product framework, Lin investigated what happens to interactive proofs under that second, more general lens: the commuting-operator model MIP^co.
His main result proves something astonishing: MIP^co = coRE
By switching the mathematical framework used to describe quantum entanglement, the entire system’s power completely inverts. Instead of verifying the truth of uncomputable problems (RE), the verifier can now only definitively confirm when a statement is false (coRE). If the statement is actually true, the computer may loop forever.
Lin’s research offers a brand-new formulation for uncomputability, with profound consequences stretching back into operator algebra and quantum mechanics. Ultimately, it delivers a striking conclusion: what we can verify through the math of computation changes drastically depending on which of the two mathematical frameworks we use to model physics.
