Papers With

← All papers
First page of Maximally entangled states are not complete for pseudo-telepathy

Maximally entangled states are not complete for pseudo-telepathy

Olivier Lalonde

quant-ph Aug 5, 2026 · v1
formalization quantum ai-agents
Read PDF arXiv abstract Code
TL;DR
The nonexistence proof of a perfect maximally entangled strategy, based on a rational NPA-hierarchy certificate, is formalized in Lean 4 with AI (Codex) assistance.
Abstract
One of the longstanding open problems in quantum nonlocality is to determine if maximally entangled states are complete for bipartite pseudo-telepathic games: namely, if every nonlocal game which admits a perfect entangled strategy admits such a strategy which uses a maximally entangled state. We exhibit a counterexample to this in the form of a bipartite nonlocal game with input sets of size 4 and 3 and output sets both of size 6. This game is part of a new class of nonlocal games, which we call inner product games, which could be of independent interest.
Problem

A long-standing open question is whether every bipartite pseudo-telepathic nonlocal game that admits a perfect entangled strategy also admits one using a maximally entangled state.

Approach

The author introduces inner product games, defined by unitaries and a positive semidefinite matrix S, and shows each has a perfect entangled strategy. A computer search over unitaries with entries in {-1,0,1} found a game with inputs 4 and 3, outputs 6 and 6, and S=diag(1,1,2,2,2,2). A modified tracial NPA hierarchy produced a rational infeasibility certificate, and the nonexistence proof was formalized in Lean as noPerfectMaximallyEntangledStrategy.

Results

The game has a perfect strategy using a non-maximally entangled state of local dimension 6, but no perfect maximally entangled strategy in any dimension. This shows maximally entangled states are not complete for pseudo-telepathy.