Parallel Repetition for Entangled and Non-signaling Provers

This direction is split into other directions: general entangled game repetition. Its last version stays readable and citable here.

Version 1 of 115 papers36 conceptsfrozen 2026-10-04

In computational complexity and quantum information, we often want to turn a "slightly hard" problem into an "extremely hard" one. The standard way to do this is through parallel repetition: instead of asking a prover to win a game once, you ask them to win $n$ independent instances of the game simultaneously.

Intuitively, if a prover has a 50% chance of winning one game, their chance of winning two should be 25%, and their chance of winning $n$ games should decay exponentially. However, when provers share quantum entanglement or follow "non-signaling" strategies, this intuition often fails. They can use their shared resources to correlate their answers across the different instances, effectively "hedging" their bets to maintain a high success rate.

The Challenge of Correlated Strategies

The core difficulty in proving a parallel repetition theorem lies in the fact that the $n$ games are not truly independent once the provers are involved. Even if the verifier picks questions for each game independently, the provers do not have to answer them independently.

In the quantum world, provers can use entanglement to link their strategies. Oded Regev demonstrated that "strong" parallel repetition—where the winning probability decays at the exact rate suggested by the single-game value—fails for both entangled and non-signaling provers. This means provers can perform significantly better than a naive "independent" strategy would suggest.

A striking example of this is quantum hedging, explored by Srinivasan Arunachalam. In certain two-round interactions, a quantum player can correlate their moves across parallel games to perfectly eliminate the risk of losing every single game, even if they have no way to guarantee a win in any individual round.

The Analytical Breakthrough: Projection Games

To make progress, researchers often focus on projection games. In these games, the answer of the first prover and the question pair uniquely determine what the second prover's answer must be for them to win.

David Steurer and Irit Dinur introduced an analytical framework that moved away from traditional combinatorial counting toward linear algebra and operator theory. By defining a "relaxed" value for a game—one that is perfectly multiplicative—they showed that the success probability in projection games does indeed decay exponentially.

This was extended to the quantum setting by Thomas Vidick, Steurer, and Dinur. They proved that for entangled projection games, shared entanglement cannot overcome the inherent difficulty of winning many rounds at once. The "entangled value" of the game still vanishes as you add more repetitions, providing a foundation for hardness amplification in quantum complexity.

Beyond Entanglement: Non-signaling Limits

Non-signaling strategies represent the absolute limit of what physics allows: correlations that do not allow faster-than-light communication. These are even more powerful than quantum entanglement.

Surprisingly, parallel repetition theorems still hold here. Shun Watanabe developed a proof using information theory and a "change of measure" technique. This approach shows that the probability of winning a large fraction of rounds decays exponentially, regardless of how large the provers' "alphabet" (the complexity of their possible answers) is. This suggests that the bottleneck for provers isn't the complexity of their communication, but the fundamental lack of signaling between them.

Scaling to Multiple Provers

While the two-prover case is increasingly well-understood, the frontier of the field is the multi-prover scenario. Tsuyoshi Ito and colleagues have shown that moving from two to three provers creates a massive jump in computational complexity, making the games NP-hard to solve.

However, as the number of players grows, some quantum advantages actually start to disappear. In the "Hypercube Game" studied by Runyao Duan and others, the gap between quantum and classical strategies vanishes exponentially as more participants are added. This highlights a recurring theme: while entanglement allows for powerful local coordination, it struggles to maintain that edge against the combinatorial explosion of constraints in large-scale, multi-party games.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_parallel_repetition_for_entangled_and_no_72f49535,
  title = {Parallel Repetition for Entangled and Non-signaling Provers},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/parallel-repetition-for-entangled-and-non-signaling-provers/rdr_72f4953554134bb0a04f352d4f950503},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_parallel_repetition_for_entangled_and_no_72f49535_v1,
  title = {Parallel Repetition for Entangled and Non-signaling Provers},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/parallel-repetition-for-entangled-and-non-signaling-provers/rdr_72f4953554134bb0a04f352d4f950503/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}