Quantum strategies achieve perfect play for unsolvable linear equations mod n
Linear equations mod $n$ are pseudo-telepathic
Computational ComplexityLogic in Computer Science
Summary
Some systems of linear equations modulo a number n have no solutions, but the authors show that quantum players can still always win a certain game based on these unsolvable systems. They prove this by combining previous mathematical results with quantum theory about how certain transformations cannot exist. This means that there are problems that are impossible to solve classically but can be perfectly solved if players use quantum resources, a phenomenon called pseudo-telepathy. The work also fully describes which types of constraint systems have these quantum advantages in finite dimensions.
What this means in practice
- •For quantum protocol designers: Identify constraint systems where quantum strategies guarantee success despite classical unsolvability, enabling new quantum communication protocols.
- •For quantum game developers: Create games that exploit quantum pseudo-telepathy effects using unsatisfiable linear equations mod n for engaging quantum advantage demonstrations.
A theory result. No direct application yet.
Authors
Lorenzo Ciardo
Abstract
We prove that the quantum monad in dimension $2n$ admits no natural transformation to the polymorphism clone of linear equations modulo $n$. Consequently, for every $n\geq 2$, there exists an unsatisfiable system of linear equations over $\mathbb{Z}_n$ whose constraint system game admits a perfect finite-dimensional quantum strategy. As a corollary, we completely characterise pseudo-telepathic constraint languages in finite dimension. The proof combines a result of Harding, Jager, and Smith on group-valued measures on subspaces of Hilbert spaces with the polymorphism-minion characterisation of quantum pseudo-telepathy.