In classical computational complexity, parallel repetition is the foundational mechanism for hardness amplification. If a verifier wants to ensure that two non-communicating provers cannot cheat in a game, the verifier can make them play $k$ independent instances of the game simultaneously. If the maximum winning probability of a single game is $v < 1$, a natural intuition suggests that the probability of winning all $k$ rounds should decay exponentially as $v^k$.
However, when provers share quantum entanglement or utilize non-signaling strategies, this classical intuition completely breaks down. Entanglement allows provers to violate local realism, introducing non-local correlations that can be leveraged across supposedly independent game instances. Understanding how, when, and why parallel repetition succeeds or fails in the presence of quantum and non-signaling resources is a central problem in quantum information theory and computational complexity.
Why Entanglement Subverts Classical Repetition
The core reason classical parallel repetition theorems fail in the quantum setting is that entangled provers do not have to treat parallel rounds independently. While they cannot communicate classically, they can perform joint quantum measurements on a shared entangled state that spans across multiple game instances. A choice or question posed in the first round can non-locally influence the optimal strategy or measurement outcome in the second round.
As a result, "strong parallel repetition"—the guarantee that the value of a repeated game decays exponentially based strictly on the single-game value—fails. As demonstrated by Regev 0001, both entangled and non-signaling provers can maintain high success rates over many parallel iterations for much longer than classically predicted.
To see this breakdown in a structural context, consider the Maxmin Label Cover Reconfiguration problem. Ohsaka showed that a naive application of parallel repetition to this problem fails to decrease the soundness error, constructing specific game structures where the value refuses to drop.
Even when the winning probability does decrease, entanglement alters the rate of decay. Vidick proved that parallel repetition can indeed force a decay in the entangled value, but initially established only a polynomial, rather than exponential, reduction. To achieve this, the framework required modified repetition schemes—such as Feige-Kilian or Dinur-Reingold repetition—which deliberately inject "confuse" or "consistency" rounds to disrupt the provers' ability to coordinate across independent instances.
Classical Repetition: [Round 1] x [Round 2] x ... x [Round k] --> Exponential Decay (v^k)
Entangled Repetition: [Round 1] <===(Entanglement)===> [Round k] --> Cross-round coordination
slows down decay
Restoring Exponential Decay via Structural Constraints
To recover the exponential decay necessary for robust hardness amplification, researchers constrain the algebraic or combinatorial structure of the games.
Projection Games and Expander Graphs
A projection game is a two-prover game where the answer of one player is uniquely determined by the answer of the other player and the question asked. This rigid constraint limits how provers can manipulate their shared quantum state.
Using an operator-theoretic framework, Steurer et al. proved an exponential parallel repetition theorem for entangled projection games. They showed that the decay rate reaches its theoretical optimum when the game's constraint graph acts as an expander graph. The high connectivity of expander graphs ensures that the local views of the players remain tightly bound, making it mathematically easier to "round" global vector strategies into valid local quantum strategies.
Complementing this, Steurer et al. introduced an analytical approach based on a perfectly multiplicative relaxation of a game's value. By translating the game into linear algebra and operator theory, the value of a $k$-fold parallel repetition can be analyzed as a simple tensor product, proving that the value of repeated projection games decays according to a bound related to the square root of the initial game's value.
Birthday Repetition
When games lack a projection structure, exponential decay can be forced by changing how questions are distributed. Manurangsi et al. introduced Birthday Repetition. Instead of sending a single query per round, the verifier assigns each prover a random set of questions.
The intuition mirrors the famous birthday paradox: as the size of the question sets grows, the probability that the sets contain overlapping, tightly constrained pairs of questions approaches 1. Once this threshold is crossed, the provers' cross-round coordination collapses, forcing an exponential decay in their success probability and enabling hardness amplification in the sub-exponential time domain.
The Complexity Landscape: Unique vs. General Games
The feasibility of parallel repetition directly impacts how hard it is to computationally approximate the value of these games.
If a game is unique (meaning any answer by the first prover uniquely determines a valid answer for the second, and vice versa), the presence of entanglement actually makes the game computationally easier. Regev 0001 et al. formulated a semidefinite programming (SDP) relaxation to establish an upper bound on the entangled value of unique games. By pairing this SDP with a novel quantum rounding technique, the authors showed that unique games with entangled provers can be approximated efficiently in polynomial time, proving that the classical Unique Games Conjecture does not hold when entanglement is permitted.
For general, non-unique entangled games, the story is entirely different. Kobayashi et al. proved that approximating the value of general entangled games remains NP-hard. Entanglement shifts the boundaries of approximation, but it does not eliminate computational hardness.
Multi-Prover and Infinite-Dimensional Frontiers
When moving beyond two players or expanding the allowed correlations to general non-signaling frameworks, new mathematical phenomena emerge.
For the broad class of non-signaling provers—where strategies are constrained only by the impossibility of faster-than-light communication—Tyagi et al. provided an information-theoretic proof of a multiprover parallel repetition theorem. By leveraging multiuser rate-distortion theory and a "change of measure" technique, the authors bypassed complex combinatorial machinery to prove that the winning probability decays exponentially. Crucially, this decay rate is universally bounded by a constant depending solely on the number of provers, meaning the complexity of the queries or answers cannot prevent the eventual exponential drop.
In contrast, multi-prover quantum games introduce severe analytical hurdles. Ito et al. introduced commuting-operator provers to model multi-prover interactive proof systems, demonstrating that distinguishing game values becomes NP-hard when three or more entangled provers are involved.
Finally, multi-prover coordination can force the physical resources themselves to scale to infinity. Ji et al. constructed a three-player coherent state embezzlement game where achieving a perfect winning probability ($1$) is exclusively possible in the limit of infinite-dimensional entangled states. They established a strict quantitative trade-off: to achieve a success probability of $1-\epsilon$, the local dimension of the provers' entangled states must grow at a rate of $\Omega(\epsilon^{-\alpha})$. This concrete boundary proves that finite non-local games can fundamentally require infinite quantum entanglement to be played optimally.
Key Foundational Work
No Strong Parallel Repetition with Entangled and Non-signaling Provers (2009) — contributed 5 concept elements to this direction.
Generalized Tsirelson Inequalities, Commuting-Operator Provers, and Multi-prover Interactive Proof Systems (2008) — contributed 3 concept elements to this direction.
Entangled Games Are Hard to Approximate (2008) — contributed 2 concept elements to this direction.