Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1509.07466 · SIAM Journal on Computing

Anchored Parallel Repetition for Nonlocal Games

Mohammad Bavarian, Thomas Vidick, Henry Yuen

Published Mar 14, 2022• 6 citations
arXivHTMLPDF

Abstract

We introduce a simple transformation on two-player nonlocal games, called “anchoring,” and prove an exponential-decay parallel repetition theorem for all anchored games in the setting of quantum entangled players. This transformation is inspired in part by the Feige--Kilian transformation [ SIAM J. Comput., 30 (2000), pp. 324--346], and has the property that if the quantum value of the original game $G$ is $v$, then the quantum value of the anchored game $G_{{\perp}}$ is $1 - (1 - \alpha)^2 \cdot (1 - v)$, where $\alpha$ is a parameter of the transformation. In particular the anchored game has quantum value 1 if and only if the original game $G$ has quantum value 1. This provides the first gap amplification technique for general two-player nonlocal games that achieves exponential decay of the quantum value.

DOI
10.1137/21m1405927

Related papers

Anchoring games for parallel repetition

Mohammad Bavarian, Thomas Vidick, Henry Yuen

Two major open problems regarding the parallel repetition of games are whether an analogue of Raz's parallel-repetition theorem holds for (a) games with more than two players, and (b) games with quantum players using entanglement. We make progress on both problems: we introduce a class of games we call anchored, and prove exponential-decay parallel repetition theorems for anchored games in the multiplayer and entangled-player settings. We introduce a simple transformation on games called anchoring and show that this transformation turns any game into an anchored game. Together, our parallel repetition theorem and our anchoring transformation provide a simple and efficient hardness-amplification technique in both the classical multiplayer and quantum settings.

•Sep 24, 2015•10 citations

Parallel Repetition via Fortification: Analytic View and the Quantum Case

Mohammad Bavarian, Thomas Vidick, Henry Yuen

In a recent work, Moshkovitz [FOCS'14] presented a transformation n two-player games called "fortification", and gave an elementary proof of an (exponential decay) parallel repetition theorem for fortified two-player projection games. In this paper, we give an analytic reformulation of Moshkovitz's fortification framework, which was originally cast in combinatorial terms. This reformulation allows us to expand the scope of the fortification method to new settings. First, we show any game (not just projection games) can be fortified, and give a simple proof of parallel repetition for general fortified games. Then, we prove parallel repetition and fortification theorems for games with players sharing quantum entanglement, as well as games with more than two players. This gives a new gap amplification method for general games in the quantum and multiplayer settings, which has recently received much interest. An important component of our work is a variant of the fortification transformation, called "ordered fortification", that preserves the entangled value of a game. The original fortification of Moshkovitz does not in general preserve the entangled value of a game, and this was a barrier to extending the fortification framework to the quantum setting.

Leibniz international proceedings in informatics•Jan 1, 2017•0 citations

Parallel repetition via fortification: analytic view and the quantum case

Mohammad Bavarian, Thomas Vidick, Henry Yuen

In a recent work, Moshkovitz [FOCS '14] presented a transformation on two-player games called "fortification", and gave an elementary proof of an (exponential decay) parallel repetition theorem for fortified two-player projection games. In this paper, we give an analytic reformulation of Moshkovitz's fortification framework, which was originally cast in combinatorial terms. This reformulation allows us to expand the scope of the fortification method to new settings. First, we show any game (not just projection games) can be fortified, and give a simple proof of parallel repetition for general fortified games. Then, we prove parallel repetition and fortification theorems for games with players sharing quantum entanglement, as well as games with more than two players. This gives a new gap amplification method for general games in the quantum and multiplayer settings, which has recently received much interest. An important component of our work is a variant of the fortification transformation, called "ordered fortification", that preserves the entangled value of a game. The original fortification of Moshkovitz does not in general preserve the entangled value of a game, and this was a barrier to extending the fortification framework to the quantum setting.

arXiv:1603.05349•Mar 17, 2016•6 citations

Multiplayer parallel repetition without dependency-breaking and anchoring variables: monotonic, concave amplification

Pete Rigas

We obtain quantitative estimates on the decay of the multiplayer optimal value under parallel repetition. In comparison to a previous work of the author in 2025 (arXiv: 2508.09380) which sought to generalize dependency-breaking and anchoring variables from two-player Quantum games, being able to establish quantitative estimates on the decay of the optimal value of a multiplayer game under parallel repetition is of interest to establish under different assumptions. Specifically, independently of the dependency-breaking and anchoring variables that have previously been employed to remove correlations from entangled information shared between Alice and Bob (hence removing dependencies), monotonic concave functions can be used in place of such variables to obtain rates of decay on the optimal value. The game-theoretic setting with two players was first analyzed with monotonic concave functions by Lanzenberger and Maurer. For $q_i , x_i > 0$ $\forall 1 \leq i \leq N$ where $N > 0 $ is the total number of players we adddress an open question raised in their work regarding potential generalizations of two-player monotonic concave functions, through amplification functions of the form $Ψ_{\textit{Mult}} \equiv Ψ= N - \underset{1 \leq i \leq N}{\prod} \mathrm{exp} \big[ - q_i x_i \big]$, which in the multiplayer game-theoretic setting have more intricate combinatorial structures.

quant-pharXiv:2605.08259•May 11, 2026•0 citations

Hardness amplification for entangled games via anchoring

Mohammad Bavarian, Thomas Vidick, Henry Yuen

We study the parallel repetition of one-round games involving players that can use quantum entanglement. A major open question in this area is whether parallel repetition reduces the entangled value of a game at an exponential rate - in other words, does an analogue of Raz's parallel repetition theorem hold for games with players sharing quantum entanglement? Previous results only apply to special classes of games.

ACM Symposium on Theory of Computing (STOC)•Jun 15, 2017•19 citations

Multiplayer parallel repetition for expander games

Irit Dinur, Prahladh Harsha, Rakesh Venkat +1 more

We investigate the value of parallel repetition of one-round games with any number of players $k\ge 2$. It has been an open question whether an analogue of Raz's Parallel Repetition Theorem holds for games with more than two players, i.e., whether the value of the repeated game decays exponentially with the number of repetitions. Verbitsky has shown, via a reduction to the density Hales-Jewett theorem, that the value of the repeated game must approach zero, as the number of repetitions increases. However, the rate of decay obtained in this way is extremely slow, and it is an open question whether the true rate is exponential as is the case for all two-player games. Exponential decay bounds are known for several special cases of multi-player games, e.g., free games and anchored games. In this work, we identify a certain expansion property of the base game and show all games with this property satisfy an exponential decay parallel repetition bound. Free games and anchored games satisfy this expansion property, and thus our parallel repetition theorem reproduces all earlier exponential-decay bounds for multiplayer games. More generally, our parallel repetition bound applies to all multiplayer games that are connected in a certain sense. We also describe a very simple game, called the GHZ game, that does not satisfy this connectivity property, and for which we do not know an exponential decay bound. We suspect that progress on bounding the value of this the parallel repetition of the GHZ game will lead to further progress on the general question.

arXiv:1610.08349•Electronic colloquium on computational complexity•Oct 26, 2016•4 citations
We introduce a simple transformation on two-player nonlocal games, called “anchoring,” and prove an exponential-decay parallel repetition theorem for all anchored games in the setting of quantum entangled players. This transformation is inspired in part by the Feige--Kilian transformation [ SIAM J. Comput., 30 (2000), pp. 324--346], and has the property that if the quantum value of the original game GGG is vvv, then the quantum value of the anchored game G⊥G_{{\perp}}G⊥​ is 1−(1−α)2⋅(1−v)1 - (1 - \alpha)^2 \cdot (1 - v)1−(1−α)2⋅(1−v), where α\alphaα is a parameter of the transformation. In particular the anchored game has quantum value 1 if and only if the original game GGG has quantum value 1. This provides the first gap amplification technique for general two-player nonlocal games that achieves exponential decay of the quantum value.
Two major open problems regarding the parallel repetition of games are whether an analogue of Raz's parallel-repetition theorem holds for (a) games with more than two players, and (b) games with quantum players using entanglement. We make progress on both problems: we introduce a class of games we call anchored, and prove exponential-decay parallel repetition theorems for anchored games in the multiplayer and entangled-player settings. We introduce a simple transformation on games called anchoring and show that this transformation turns any game into an anchored game. Together, our parallel repetition theorem and our anchoring transformation provide a simple and efficient hardness-amplification technique in both the classical multiplayer and quantum settings.
In a recent work, Moshkovitz [FOCS'14] presented a transformation n two-player games called "fortification", and gave an elementary proof of an (exponential decay) parallel repetition theorem for fortified two-player projection games. In this paper, we give an analytic reformulation of Moshkovitz's fortification framework, which was originally cast in combinatorial terms. This reformulation allows us to expand the scope of the fortification method to new settings. First, we show any game (not just projection games) can be fortified, and give a simple proof of parallel repetition for general fortified games. Then, we prove parallel repetition and fortification theorems for games with players sharing quantum entanglement, as well as games with more than two players. This gives a new gap amplification method for general games in the quantum and multiplayer settings, which has recently received much interest. An important component of our work is a variant of the fortification transformation, called "ordered fortification", that preserves the entangled value of a game. The original fortification of Moshkovitz does not in general preserve the entangled value of a game, and this was a barrier to extending the fortification framework to the quantum setting.
In a recent work, Moshkovitz [FOCS '14] presented a transformation on two-player games called "fortification", and gave an elementary proof of an (exponential decay) parallel repetition theorem for fortified two-player projection games. In this paper, we give an analytic reformulation of Moshkovitz's fortification framework, which was originally cast in combinatorial terms. This reformulation allows us to expand the scope of the fortification method to new settings. First, we show any game (not just projection games) can be fortified, and give a simple proof of parallel repetition for general fortified games. Then, we prove parallel repetition and fortification theorems for games with players sharing quantum entanglement, as well as games with more than two players. This gives a new gap amplification method for general games in the quantum and multiplayer settings, which has recently received much interest. An important component of our work is a variant of the fortification transformation, called "ordered fortification", that preserves the entangled value of a game. The original fortification of Moshkovitz does not in general preserve the entangled value of a game, and this was a barrier to extending the fortification framework to the quantum setting.
We obtain quantitative estimates on the decay of the multiplayer optimal value under parallel repetition. In comparison to a previous work of the author in 2025 (arXiv: 2508.09380) which sought to generalize dependency-breaking and anchoring variables from two-player Quantum games, being able to establish quantitative estimates on the decay of the optimal value of a multiplayer game under parallel repetition is of interest to establish under different assumptions. Specifically, independently of the dependency-breaking and anchoring variables that have previously been employed to remove correlations from entangled information shared between Alice and Bob (hence removing dependencies), monotonic concave functions can be used in place of such variables to obtain rates of decay on the optimal value. The game-theoretic setting with two players was first analyzed with monotonic concave functions by Lanzenberger and Maurer. For qi,xi>0q_i , x_i > 0qi​,xi​>0 ∀1≤i≤N\forall 1 \leq i \leq N∀1≤i≤N where $N > 0 $ is the total number of players we adddress an open question raised in their work regarding potential generalizations of two-player monotonic concave functions, through amplification functions of the form ΨMult≡Ψ=N−∏1≤i≤Nexp[−qixi]Ψ_{\textit{Mult}} \equiv Ψ= N - \underset{1 \leq i \leq N}{\prod} \mathrm{exp} \big[ - q_i x_i \big]ΨMult​≡Ψ=N−1≤i≤N∏​exp[−qi​xi​], which in the multiplayer game-theoretic setting have more intricate combinatorial structures.
We investigate the value of parallel repetition of one-round games with any number of players k≥2k\ge 2k≥2. It has been an open question whether an analogue of Raz's Parallel Repetition Theorem holds for games with more than two players, i.e., whether the value of the repeated game decays exponentially with the number of repetitions. Verbitsky has shown, via a reduction to the density Hales-Jewett theorem, that the value of the repeated game must approach zero, as the number of repetitions increases. However, the rate of decay obtained in this way is extremely slow, and it is an open question whether the true rate is exponential as is the case for all two-player games. Exponential decay bounds are known for several special cases of multi-player games, e.g., free games and anchored games. In this work, we identify a certain expansion property of the base game and show all games with this property satisfy an exponential decay parallel repetition bound. Free games and anchored games satisfy this expansion property, and thus our parallel repetition theorem reproduces all earlier exponential-decay bounds for multiplayer games. More generally, our parallel repetition bound applies to all multiplayer games that are connected in a certain sense. We also describe a very simple game, called the GHZ game, that does not satisfy this connectivity property, and for which we do not know an exponential decay bound. We suspect that progress on bounding the value of this the parallel repetition of the GHZ game will lead to further progress on the general question.