⚛️ quantum physics

Maximally entangled states are not complete for pseudo-telepathy

The paper resolves a longstanding open problem in quantum nonlocality by presenting a counterexample—a specific bipartite nonlocal game within a new class called "inner product games"—that demonstrates maximally entangled states are not complete for pseudo-telepathy, as there exist games with perfect entangled strategies that cannot be won using only maximally entangled states.

Original authors: Olivier Lalonde

Published 2026-08-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Olivier Lalonde

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a universe where two friends, Alice and Bob, are separated by a vast distance, perhaps even on opposite sides of the galaxy. They can't talk to each other, send text messages, or use telepathy in the sci-fi sense. Yet, they are playing a game where they must coordinate their answers perfectly to win. In the classical world, if they can't communicate, there are limits to how well they can coordinate; they are bound by the rules of logic and probability. But in the quantum world, things get weird. If Alice and Bob share a special "quantum link" called entanglement, they can sometimes coordinate their answers in ways that seem impossible, as if they are reading each other's minds. This spooky phenomenon is called quantum pseudo-telepathy.

The big question scientists have been asking for a long time is: How strong does this quantum link need to be? Specifically, do Alice and Bob need the "strongest possible" link, known as a maximally entangled state, to win these impossible games? It's a bit like asking if you need a Ferrari to win a race, or if a really good bicycle will do. For many years, every example of these mind-bending games that scientists found could be won using that "Ferrari" level of entanglement. This led to a hopeful guess: maybe the strongest link is all you ever need. But is that true for every possible game?

A new paper by Olivier Lalonde from the University of Waterloo says: No, not always.

Lalonde has discovered a specific game where the "Ferrari" (the maximally entangled state) actually fails to win, even though a different, slightly "wobblier" quantum link can win perfectly. It's a counterexample that shatters the idea that the strongest connection is always the best tool for the job.

The Game of "Inner Product"

To understand the discovery, we have to look at the game itself. Lalonde invented a new type of game called an "inner product game." Imagine Alice and Bob are each handed a secret code (an input number). Based on their code, they have to pick a specific vector (a direction in space) from a list of options. They win if the two vectors they pick are not perpendicular to each other—think of it like two arrows that aren't pointing at a perfect 90-degree angle to one another.

The rules are tricky. The game is designed so that if Alice and Bob try to use classical logic (just guessing or following a pre-agreed plan), they will lose. But if they share a quantum link, they can win every single time.

Lalonde created a specific version of this game with the following stats:

Inputs: Alice gets one of 4 possible questions; Bob gets one of 3.
Outputs: They must each choose one of 6 possible answers.
The Winning State: To win perfectly, they need to share a quantum state where the "local dimension" is 6.

The Ferrari vs. The Custom Bike

Here is the twist. In this specific game, the "perfect" quantum strategy requires a very specific, custom-built entangled state. It looks like this:
$|\Phi\rangle = \frac{1}{\sqrt{18}} (|1\rangle|1\rangle + |2\rangle|2\rangle + 2|3\rangle|3\rangle + 2|4\rangle|4\rangle + 2|5\rangle|5\rangle + 2|6\rangle|6\rangle)$

Notice the numbers? Some parts of the link are weighted by 1, and others are weighted by 2. This is a non-maximally entangled state. It's not perfectly balanced; it's lopsided.

Now, here is the punchline: A maximally entangled state cannot win this game.

A maximally entangled state is like a perfectly balanced scale where every option has an equal weight (all 1s). Lalonde proved mathematically that if Alice and Bob try to use this perfectly balanced "Ferrari" to play this specific game, they will inevitably fail. They simply cannot coordinate their answers perfectly using that type of link. They must use the lopsided, custom-built link described above.

How Did They Prove It?

You might wonder, "How can you be sure a perfect strategy doesn't exist?" You can't just play the game a million times; you need a mathematical proof.

Lalonde used a powerful tool called the tracial NPA hierarchy. Think of this as a super-sophisticated logic machine that checks every possible way Alice and Bob could try to coordinate their answers. It's like checking every possible move in a chess game to see if a checkmate is possible.

The proof was heavy-duty. It involved a computer solving a massive puzzle with 207,202 variables and 208,702 constraints. It took 7 minutes on a laptop to solve. The computer didn't just guess; it produced a "rational certificate of infeasibility," which is a mathematical receipt proving that no solution exists. To be extra sure, the entire proof was double-checked by a computer program called Lean, a proof assistant that verifies math step-by-step.

The result is solid: There is no perfect strategy using a maximally entangled state for this game.

Why This Matters

This discovery is a big deal because it settles a long-standing debate. For years, scientists wondered if the "strongest" quantum link was the only one that mattered for these mind-bending games. This paper shows that nature is more subtle than that. Sometimes, the "perfect" tool isn't the right tool; you need a specific, slightly imperfect one to get the job done.

It also opens up new questions. Is this game a "self-test"? That means, if someone claims they can win this game, does it prove they are holding that specific, lopsided quantum state? The numbers suggest yes, but proving that analytically (without a computer) is a challenge for the future.

In short, we now know that in the quantum world, having the "best" entanglement isn't always enough. Sometimes, you need the right kind of entanglement, even if it's not the strongest.

Technical Summary: "Maximally entangled states are not complete for pseudo-telepathy"

Problem Statement
The paper addresses a longstanding open problem in quantum nonlocality regarding the sufficiency of maximally entangled states for pseudo-telepathic games. A nonlocal game is termed pseudo-telepathic if it admits a perfect entangled strategy (winning with probability 1) but no perfect classical strategy. While it is known that for many specific families of bipartite pseudo-telepathic games, maximally entangled states suffice to achieve perfect strategies, it remained an open question whether this holds universally. Specifically, the problem asks: Does every nonlocal game admitting a perfect entangled strategy also admit a perfect strategy utilizing a maximally entangled state? Previous work established that maximally entangled states are not necessary (as some games can be won with non-maximally entangled states), but the question of whether they are always sufficient remained unresolved.

Methodology
The author introduces a new class of nonlocal games termed inner product games to construct a counterexample.

Game Definition: An inner product game is defined by collections of unitary operators $\{U_x\}$ and $\{V_y\}$ of order $m$ , and a positive semidefinite matrix $S$ . Alice and Bob receive inputs $x$ and $y$ and must output $a$ and $b$ such that $\langle a| U_x^\dagger S V_y |b\rangle \neq 0$ .
Existence of Entangled Strategy: The paper proves (Proposition 3.1) that any inner product game admits a perfect entangled strategy using a specific entangled state $|\psi\rangle = (S \otimes I)|\Omega\rangle$ , where $|\Omega\rangle$ is the standard maximally entangled state. This strategy does not necessarily use a maximally entangled state if $S$ is not proportional to the identity.
Counterexample Construction ( $G_{4,3,6,6}$ ): Using a computer-assisted heuristic search, the author constructed a specific instance, $G_{4,3,6,6}$ $G_{4, 3, 6, 6}$ , with input sets of size 4 and 3, and output sets of size 6. The construction involved:
- Setting the local dimension $m=6$ .
- Selecting a diagonal matrix $S = \text{diag}(1, 1, 2, 2, 2, 2)$ .
- Enumerating unitaries with components in $\{-1, 0, 1\}$ to find a configuration that is classically infeasible.
- Applying a pruning algorithm to minimize the input set sizes.
Proof of Non-Existence of Maximally Entangled Strategy: To prove that no perfect strategy using a maximally entangled state exists for $G_{4,3,6,6}$ $G_{4, 3, 6, 6}$ , the author employed a variant of the tracial NPA hierarchy (a sum-of-squares hierarchy).
- The problem was formulated as finding a tracial state on a specific $*$ -algebra generated by measurement operators.
- A strengthened version of the $n=4$ level of the hierarchy was used to test for the existence of such a state.
- The resulting semidefinite program (involving ~207k variables and ~208k constraints) was solved numerically to demonstrate infeasibility.
- The proof was formalized in the Lean proof assistant using a rational certificate of infeasibility extracted from the solver.

Key Results
The paper establishes Theorem 1.1, which states:

There exists a bipartite game $G_{4,3,6,6}$ with input sizes 4 and 3, and output sizes 6 and 6.
This game possesses a perfect entangled strategy using an entangled state of local dimension 6 (specifically, a non-maximally entangled state derived from the matrix $S$ ).
Crucially, this game admits no perfect entangled strategy involving a maximally entangled state.

Significance and Claims
The paper claims to settle the open problem in the negative, demonstrating that maximally entangled states are not complete for pseudo-telepathy. The significance of the work lies in:

Resolution of an Open Problem: It provides the first counterexample showing that the class of games solvable with maximally entangled states is strictly smaller than the class of games solvable with general entangled states.
New Game Class: The introduction of "inner product games" offers a new framework for studying nonlocality, which may be of independent interest.
Methodological Contribution: The work demonstrates the utility of combining heuristic computer search with formal verification (via Lean) and numerical hierarchies (tracial NPA) to resolve deep questions in quantum information theory.

Limitations and Future Directions (as noted by the author)
The author notes that the counterexample was "manufactured" via computer search rather than arising from a natural physical system, and the proof of its properties relies heavily on numerical semidefinite programming rather than analytic insight. The paper suggests that finding a "natural" counterexample with an analytic proof remains an open challenge. Additionally, the author notes that numerical simulations suggest $G_{4,3,6,6}$ is a self-test for the specific non-maximally entangled state used, a property that remains to be proven formally. The work also hints at potential implications for the relationship between the entangled chromatic number and the quantum chromatic number in zero-error information theory.

The Game of "Inner Product"

The Ferrari vs. The Custom Bike

How Did They Prove It?

Why This Matters

Technical Summary: "Maximally entangled states are not complete for pseudo-telepathy"

More like this