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

Entropy Budgets and Weighted Concentration in Parallel Games

Harjas Sandhu

Published Nov 6, 2026• 0 citations
Publisher

Abstract

How do small individual losses accumulate when many tests are performed together and their outcomes may be strongly correlated? This paper proves a weighted concentration theorem from an explicit conditional entropy budget. The natural scale is the sum of the squared benchmark losses, and the bound holds at every finite length without assuming independence of the outcomes. The result For benchmark losses εᵢ, let S = ∑ᵢ εᵢ² and let Z = ∑ᵢ εᵢ(1 − Wᵢ) be the weighted loss. Under the stated budget and charge assumptions, the paper proves Pr[Z ≤ (1 − r)S] ≤ exp[−r⁵S/(2²¹K⁴(1 + C₀))] for 0 < r ≤ 1. A sharper all-wins estimate is also established. How the argument works Independent sparse auxiliary tests reveal selected successful coordinates. An exact posterior entropy identity and a differential bound then control the probability of unusually small total loss. The underlying success indicators themselves may be arbitrarily correlated. The paper also characterises the predicates admitting exact positive-factor mass bounds, proves exponential mass obstructions outside that class, and gives a robust common-information obstruction to uniformly low-mass accurate filters on all near-perfect tested instances with growing answer alphabets. Independent question-free nuisance registers nevertheless cancel exactly from entropy increments under the specified product assumptions. Scope The commuting-operator game applications, including disjoint-block and projection predicates and a charged extension, assume the explicitly stated finite-tracial reconstruction hypothesis FR(K). That hypothesis is not proved here; at its existential level it is equivalent to the corresponding finite-tracial scalar budget. The general quadratic parallel-repetition problem remains open. The factorisation obstructions constrain particular reconstruction methods and do not disprove general quadratic repetition.

AI Summary

The paper studies how small benchmark losses accumulate across parallel tests when the outcomes can be strongly correlated. It derives finite-length concentration from an explicit conditional entropy budget, rather than from independence of the success indicators. For benchmark losses $\varepsilon_i$, define $S=\sum_i\varepsilon_i^2$ and weighted loss $Z=\sum_i\varepsilon_i(1-W_i)$, where $W_i$ indicates success. Under the stated budget and charge assumptions, the main bound is $\Pr[Z\leq(1-r)S]\leq\exp[-r^5S/(2^{21}K^4(1+C_0))]$ for $0<r\leq1$. A sharper bound is obtained for the event that every test succeeds. The argument introduces independent sparse auxiliary tests that reveal selected successful coordinates, then combines an exact posterior entropy identity with a differential bound to control unusually low weighted loss. The paper also characterises predicates admitting exact positive-factor mass bounds and establishes exponential mass obstructions outside that class. A robust common-information obstruction rules out uniformly low-mass accurate filters across all near-perfect tested instances with growing answer alphabets. Independent question-free nuisance registers cancel exactly from entropy increments under specified product assumptions. Applications to commuting-operator games—including disjoint-block and projection predicates and a charged extension—assume an unproved finite-tracial reconstruction hypothesis, $\mathrm{FR}(K)$. At the existential level, this hypothesis is equivalent to the corresponding finite-tracial scalar budget. The general quadratic parallel-repetition problem remains open, and the factorisation obstructions restrict particular reconstruction methods rather than ruling out general quadratic repetition.

No sign of AI-generated textStrong assumptionsMissing comparisonUnclear novelty

Written by gpt-6.1-sol from the abstract only. Automated: it can be wrong.

DOI
10.5281/zenodo.23987560

Related papers

Quadratic Repetition for Commuting Projection Games and Noisy Quantum Communication

Harjas Sandhu

How reliably does repeating a quantum verification test amplify its soundness when the players can coordinate all their answers? This paper proves a quadratic-gap parallel-repetition bound for finite two-player games whose winning answer graphs are unions of disjoint complete bipartite blocks. The class includes noninjective and partial projection games, with arbitrary joint question distributions within each independent round and arbitrary commuting-operator strategies. If the single-game commuting value is 1 − ε, the probability of winning all n repetitions is at most exp(−2−75 ε²n). Known binary line games show that the quadratic gap power is optimal within the full block class, up to constants. A separate finite-dimensional tensor theorem uses its own single-game gap. The proof constructs one exact conditioned target with square-root-weighted rectangle labels and two independently normalized one-sided comparison states. Entropy cancellation and finite-tracial local reconstruction give a charged extension, heterogeneous repetition bounds and weighted-threshold concentration. Scalar finite-table closure then transfers the estimates to arbitrary commuting strategies. A further application bounds interactive finite-dimensional quantum protocols communicating through prescribed memoryless channels. Exponential zero-communication soundness survives a strict aggregate entanglement-assisted capacity budget. An explicit erasure-channel coding example illustrates the bound with polynomial encoding and decoding costs. The results do not establish quadratic repetition for arbitrary predicates, uniform finite-dimensional resources for arbitrary commuting strategies, or an efficient locality-preserving Hamiltonian or cryptographic compiler. The paper develops the reconstruction premise left conditional in Entropy Budgets and Weighted Concentration in Parallel Games.

•Nov 7, 2026•0 citations

Parallel Repetition for Entangled Games via Conditional Relative Entropy

Rahul Jain

We give a proof of the cubic parallel-repetition bound for finite two-player entangled games using quantum conditional relative entropy. For a game with entangled value $1-\varepsilon<1$ and answer alphabets $\mathcal A,\mathcal B$, its $n$-fold repeated value is at most \[ \exp[-Ω(\varepsilon^3n/L)],\qquad L:=\max\{1,\log(|\mathcal A||\mathcal B|)\}, \] for every $n\ge1$. This recovers Song's cubic rate. We also prove a threshold bound: the probability of winning a fraction at least $1-\varepsilon+δ$ is at most $\exp[-Ω(δ^5n/(\varepsilon^2L))]$ for $0<δ\le\varepsilon$. Our information charge is the decrease in relative entropy when a question reference is discarded. Our comparison states preserve the original conditional question law. A chain rule bounds the coordinate charges using the cost of conditioning on checked wins and retaining checked answers. Our main lemma converts small charges into nearby pure-state descriptions and local corrections, each depending only on one player's question. Together with Song's sampler, these enable approximate local preparation of the conditioned workspace.

quant-pharXiv:2610.21410•Oct 16, 2026•0 citations

Parallel Repetition in Projection Games and a Concentration Bound

Anup Rao

A two-player game is played by cooperating players who are not allowed to communicate. A referee asks the players questions sampled from some known distribution and decides whether they win or not based on a known predicate of the questions and the players' answers. The parallel repetition of the game is the game in which the referee samples n independent pairs of questions and sends the corresponding questions to the players simultaneously. If the players cannot win the original game with probability better than $(1-\epsilon)$, what's the best they can do in the repeated game? We improve earlier results of [R. Raz, SIAM J. Comput., 27 (1998), pp. 763–803] and [T. Holenstein, Theory Comput., 5 (2009), pp. 141–172], who showed that the players cannot win all copies in the repeated game with probability better than $(1-\epsilon/2)^{\Omega(n\epsilon^2/c)}$ (here c is the length of the answers in the game), in the following ways: (i) We show that the probability of winning all copies is $(1-\epsilon/2)^{\Omega(\epsilon n)}$ as long as the game is a “projection game,” the type of game most commonly used in hardness of approximation results. (ii) We prove a concentration bound for parallel repetition (of general games) showing that for any constant $0<\delta <\epsilon$, the probability that the players win a $(1-\epsilon+\delta)$ fraction of the games in the parallel repetition is at most $\exp\left(-\Omega_{\epsilon}(\delta^3 n/c)\right)$ (here the constant may depend on $\epsilon$); our result has applications to testing Bell inequalities, since it implies that the parallel repetition of the CHSH game can be used to get an experiment that has a very large classical versus quantum gap. Our first bound is independent of the answer length and has a better dependence on $\epsilon$. By the recent work of Raz [Proceedings of the $49$th Annual IEEE Symposium on Foundations of Computer Science, 2008, pp. 369–373], this bound is tight. Our bound gives a generic way to improve the soundness of a probabilistically checkable proof (PCP), in a way that is independent of the answer length of the PCP. Using it, for every k, one can convert any q query PCP with answer length c, size $sc$, and soundness $(1-\epsilon)$ into a two-query PCP with answer length $ck$, size $O(ck (2s)^k)$, and soundness $(1-\epsilon/2q)^{\Omega(\epsilon k/q)}$. Another consequence of our bound is that the unique games conjecture of Khot [Proceedings of the $34$th Annual ACM Symposium on Theory of Computing, 2002, pp. 767–775] can now be shown to be equivalent to the following a priori weaker conjecture: There is an unbounded increasing function $f:\mathbb{R}^+\rightarrow \mathbb{R}^+$ such that for every $\epsilon> 0$, there exists an alphabet size $M(\epsilon)$ for which it is NP-hard to distinguish a unique game with alphabet size M in which a $(1-\epsilon^2)$ fraction of the constraints can be satisfied from one in which a $(1-\epsilon f(1/\epsilon))$ fraction of the constraints can be satisfied.

SIAM Journal on Computing•May 17, 2008•159 citations

The Exact Communication Threshold for Parallel Repetition

Daiki Suruga

The parallel repetition theorem is a fundamental tool in theoretical computer science, showing that the probability of winning all $n$ independent instances of a finite two-player game decays exponentially in $n$, provided that the game has no perfect strategy. The classical theorem assumes that the players cannot communicate, raising the question of how much communication can be allowed while preserving this exponential decay. For every finite total relation $g$ and arbitrary input distribution $μ$, we prove exponential decay at every fixed communication rate below a quantity called zero-error internal information complexity, denoted by $\mathrm{IC}_μ(g,0)$. Together with known results showing that $n\,\mathrm{IC}_μ(g,0)+o(n)$ bits of communication suffice to solve all $n$ instances with success probability tending to one, our bound determines the exact communication threshold. As a by-product, we obtain exact characterizations of amortized distributional and randomized communication complexity under the global-error criterion.

arXiv:2611.01339•Oct 31, 2026•0 citations

Threshold parallel repetition for finite-dimensional entangled games

OpenAI

For every finite two-player game with entangled value v<1, we prove exponential decay for the probability of winning at least a v+\delta fraction of k independent repetitions, uniformly over all finite-dimensional joint strategies. The result allows arbitrary correlated question distributions and holds for every 0\lt \delta\lt 1-v and k\ge1. Its universal rate is proportional to \delta^5/(1+\log(|\mathcal A||\mathcal B|)), where \mathcal A,\mathcal B are the answer alphabets. For each fixed question distribution, we also obtain an explicit cubic rate in \delta.

•Oct 6, 2026•0 citations

Concentration Bounds from Parallel Repetition Theorems

Taylor Hornby

This thesis contributes to the study of parallel repetition theorems and concentration bounds for nonlocal games and quantum interactive proofs. We make the following contributions: \n \n- A lemma that is useful for converting parallel repetition theorems (bounds on the probability of winning all instances of a nonlocal game which is being repeated in parallel) into concentration bounds (bounds on winning a certain fraction of the instances). \n \n- Exponentially-decaying concentration bounds for two-player games on the uniform distribution and k-player free games, against quantum strategies. \n \n- A proof that given a quantum interactive proof system with parameters α (the probability with which the verifier can be convinced to accept when they should accept) and β (the soundness error), as long as α > β, both the soundness error and completeness error can be reduced exponentially by repeating the protocol in parallel and requiring an (α + β)/2 fraction of the repetitions to be won. Our result requires a log-factor more repetitions than are necessary in the classical case.

•Aug 22, 2018•1 citation
How do small individual losses accumulate when many tests are performed together and their outcomes may be strongly correlated? This paper proves a weighted concentration theorem from an explicit conditional entropy budget. The natural scale is the sum of the squared benchmark losses, and the bound holds at every finite length without assuming independence of the outcomes. The result For benchmark losses εᵢ, let S = ∑ᵢ εᵢ² and let Z = ∑ᵢ εᵢ(1 − Wᵢ) be the weighted loss. Under the stated budget and charge assumptions, the paper proves Pr[Z ≤ (1 − r)S] ≤ exp[−r⁵S/(2²¹K⁴(1 + C₀))] for 0 < r ≤ 1. A sharper all-wins estimate is also established. How the argument works Independent sparse auxiliary tests reveal selected successful coordinates. An exact posterior entropy identity and a differential bound then control the probability of unusually small total loss. The underlying success indicators themselves may be arbitrarily correlated. The paper also characterises the predicates admitting exact positive-factor mass bounds, proves exponential mass obstructions outside that class, and gives a robust common-information obstruction to uniformly low-mass accurate filters on all near-perfect tested instances with growing answer alphabets. Independent question-free nuisance registers nevertheless cancel exactly from entropy increments under the specified product assumptions. Scope The commuting-operator game applications, including disjoint-block and projection predicates and a charged extension, assume the explicitly stated finite-tracial reconstruction hypothesis FR(K). That hypothesis is not proved here; at its existential level it is equivalent to the corresponding finite-tracial scalar budget. The general quadratic parallel-repetition problem remains open. The factorisation obstructions constrain particular reconstruction methods and do not disprove general quadratic repetition.
The paper studies how small benchmark losses accumulate across parallel tests when the outcomes can be strongly correlated. It derives finite-length concentration from an explicit conditional entropy budget, rather than from independence of the success indicators.
For benchmark losses εi\varepsilon_iεi​, define S=∑iεi2S=\sum_i\varepsilon_i^2S=∑i​εi2​ and weighted loss Z=∑iεi(1−Wi)Z=\sum_i\varepsilon_i(1-W_i)Z=∑i​εi​(1−Wi​), where WiW_iWi​ indicates success. Under the stated budget and charge assumptions, the main bound is Pr⁡[Z≤(1−r)S]≤exp⁡[−r5S/(221K4(1+C0))]\Pr[Z\leq(1-r)S]\leq\exp[-r^5S/(2^{21}K^4(1+C_0))]Pr[Z≤(1−r)S]≤exp[−r5S/(221K4(1+C0​))] for 0<r≤10<r\leq10<r≤1. A sharper bound is obtained for the event that every test succeeds. The argument introduces independent sparse auxiliary tests that reveal selected successful coordinates, then combines an exact posterior entropy identity with a differential bound to control unusually low weighted loss.
The paper also characterises predicates admitting exact positive-factor mass bounds and establishes exponential mass obstructions outside that class. A robust common-information obstruction rules out uniformly low-mass accurate filters across all near-perfect tested instances with growing answer alphabets. Independent question-free nuisance registers cancel exactly from entropy increments under specified product assumptions.
Applications to commuting-operator games—including disjoint-block and projection predicates and a charged extension—assume an unproved finite-tracial reconstruction hypothesis, FR(K)\mathrm{FR}(K)FR(K). At the existential level, this hypothesis is equivalent to the corresponding finite-tracial scalar budget. The general quadratic parallel-repetition problem remains open, and the factorisation obstructions restrict particular reconstruction methods rather than ruling out general quadratic repetition.
How reliably does repeating a quantum verification test amplify its soundness when the players can coordinate all their answers? This paper proves a quadratic-gap parallel-repetition bound for finite two-player games whose winning answer graphs are unions of disjoint complete bipartite blocks. The class includes noninjective and partial projection games, with arbitrary joint question distributions within each independent round and arbitrary commuting-operator strategies. If the single-game commuting value is 1 − ε, the probability of winning all n repetitions is at most exp(−2−75 ε²n). Known binary line games show that the quadratic gap power is optimal within the full block class, up to constants. A separate finite-dimensional tensor theorem uses its own single-game gap. The proof constructs one exact conditioned target with square-root-weighted rectangle labels and two independently normalized one-sided comparison states. Entropy cancellation and finite-tracial local reconstruction give a charged extension, heterogeneous repetition bounds and weighted-threshold concentration. Scalar finite-table closure then transfers the estimates to arbitrary commuting strategies. A further application bounds interactive finite-dimensional quantum protocols communicating through prescribed memoryless channels. Exponential zero-communication soundness survives a strict aggregate entanglement-assisted capacity budget. An explicit erasure-channel coding example illustrates the bound with polynomial encoding and decoding costs. The results do not establish quadratic repetition for arbitrary predicates, uniform finite-dimensional resources for arbitrary commuting strategies, or an efficient locality-preserving Hamiltonian or cryptographic compiler. The paper develops the reconstruction premise left conditional in Entropy Budgets and Weighted Concentration in Parallel Games.
We give a proof of the cubic parallel-repetition bound for finite two-player entangled games using quantum conditional relative entropy. For a game with entangled value 1−ε<11-\varepsilon<11−ε<1 and answer alphabets A,B\mathcal A,\mathcal BA,B, its nnn-fold repeated value is at most exp⁡[−Ω(ε3n/L)],L:=max⁡{1,log⁡(∣A∣∣B∣)}, \exp[-Ω(\varepsilon^3n/L)],\qquad L:=\max\{1,\log(|\mathcal A||\mathcal B|)\}, exp[−Ω(ε3n/L)],L:=max{1,log(∣A∣∣B∣)}, for every n≥1n\ge1n≥1. This recovers Song's cubic rate. We also prove a threshold bound: the probability of winning a fraction at least 1−ε+δ1-\varepsilon+δ1−ε+δ is at most exp⁡[−Ω(δ5n/(ε2L))]\exp[-Ω(δ^5n/(\varepsilon^2L))]exp[−Ω(δ5n/(ε2L))] for 0<δ≤ε0<δ\le\varepsilon0<δ≤ε. Our information charge is the decrease in relative entropy when a question reference is discarded. Our comparison states preserve the original conditional question law. A chain rule bounds the coordinate charges using the cost of conditioning on checked wins and retaining checked answers. Our main lemma converts small charges into nearby pure-state descriptions and local corrections, each depending only on one player's question. Together with Song's sampler, these enable approximate local preparation of the conditioned workspace.
A two-player game is played by cooperating players who are not allowed to communicate. A referee asks the players questions sampled from some known distribution and decides whether they win or not based on a known predicate of the questions and the players' answers. The parallel repetition of the game is the game in which the referee samples n independent pairs of questions and sends the corresponding questions to the players simultaneously. If the players cannot win the original game with probability better than (1−ϵ)(1-\epsilon)(1−ϵ), what's the best they can do in the repeated game? We improve earlier results of [R. Raz, SIAM J. Comput., 27 (1998), pp. 763–803] and [T. Holenstein, Theory Comput., 5 (2009), pp. 141–172], who showed that the players cannot win all copies in the repeated game with probability better than (1−ϵ/2)Ω(nϵ2/c)(1-\epsilon/2)^{\Omega(n\epsilon^2/c)}(1−ϵ/2)Ω(nϵ2/c) (here c is the length of the answers in the game), in the following ways: (i) We show that the probability of winning all copies is (1−ϵ/2)Ω(ϵn)(1-\epsilon/2)^{\Omega(\epsilon n)}(1−ϵ/2)Ω(ϵn) as long as the game is a “projection game,” the type of game most commonly used in hardness of approximation results. (ii) We prove a concentration bound for parallel repetition (of general games) showing that for any constant 0<δ<ϵ0<\delta <\epsilon0<δ<ϵ, the probability that the players win a (1−ϵ+δ)(1-\epsilon+\delta)(1−ϵ+δ) fraction of the games in the parallel repetition is at most exp⁡(−Ωϵ(δ3n/c))\exp\left(-\Omega_{\epsilon}(\delta^3 n/c)\right)exp(−Ωϵ​(δ3n/c)) (here the constant may depend on ϵ\epsilonϵ); our result has applications to testing Bell inequalities, since it implies that the parallel repetition of the CHSH game can be used to get an experiment that has a very large classical versus quantum gap. Our first bound is independent of the answer length and has a better dependence on ϵ\epsilonϵ. By the recent work of Raz [Proceedings of the 494949th Annual IEEE Symposium on Foundations of Computer Science, 2008, pp. 369–373], this bound is tight. Our bound gives a generic way to improve the soundness of a probabilistically checkable proof (PCP), in a way that is independent of the answer length of the PCP. Using it, for every k, one can convert any q query PCP with answer length c, size scscsc, and soundness (1−ϵ)(1-\epsilon)(1−ϵ) into a two-query PCP with answer length ckckck, size O(ck(2s)k)O(ck (2s)^k)O(ck(2s)k), and soundness (1−ϵ/2q)Ω(ϵk/q)(1-\epsilon/2q)^{\Omega(\epsilon k/q)}(1−ϵ/2q)Ω(ϵk/q). Another consequence of our bound is that the unique games conjecture of Khot [Proceedings of the 343434th Annual ACM Symposium on Theory of Computing, 2002, pp. 767–775] can now be shown to be equivalent to the following a priori weaker conjecture: There is an unbounded increasing function f:R+→R+f:\mathbb{R}^+\rightarrow \mathbb{R}^+f:R+→R+ such that for every ϵ>0\epsilon> 0ϵ>0, there exists an alphabet size M(ϵ)M(\epsilon)M(ϵ) for which it is NP-hard to distinguish a unique game with alphabet size M in which a (1−ϵ2)(1-\epsilon^2)(1−ϵ2) fraction of the constraints can be satisfied from one in which a (1−ϵf(1/ϵ))(1-\epsilon f(1/\epsilon))(1−ϵf(1/ϵ)) fraction of the constraints can be satisfied.
The parallel repetition theorem is a fundamental tool in theoretical computer science, showing that the probability of winning all nnn independent instances of a finite two-player game decays exponentially in nnn, provided that the game has no perfect strategy. The classical theorem assumes that the players cannot communicate, raising the question of how much communication can be allowed while preserving this exponential decay. For every finite total relation ggg and arbitrary input distribution μμμ, we prove exponential decay at every fixed communication rate below a quantity called zero-error internal information complexity, denoted by ICμ(g,0)\mathrm{IC}_μ(g,0)ICμ​(g,0). Together with known results showing that n ICμ(g,0)+o(n)n\,\mathrm{IC}_μ(g,0)+o(n)nICμ​(g,0)+o(n) bits of communication suffice to solve all nnn instances with success probability tending to one, our bound determines the exact communication threshold. As a by-product, we obtain exact characterizations of amortized distributional and randomized communication complexity under the global-error criterion.
For every finite two-player game with entangled value v<1, we prove exponential decay for the probability of winning at least a v+\delta fraction of k independent repetitions, uniformly over all finite-dimensional joint strategies. The result allows arbitrary correlated question distributions and holds for every 0\lt \delta\lt 1-v and k\ge1. Its universal rate is proportional to \delta^5/(1+\log(|\mathcal A||\mathcal B|)), where \mathcal A,\mathcal B are the answer alphabets. For each fixed question distribution, we also obtain an explicit cubic rate in \delta.
This thesis contributes to the study of parallel repetition theorems and concentration bounds for nonlocal games and quantum interactive proofs. We make the following contributions: \n \n- A lemma that is useful for converting parallel repetition theorems (bounds on the probability of winning all instances of a nonlocal game which is being repeated in parallel) into concentration bounds (bounds on winning a certain fraction of the instances). \n \n- Exponentially-decaying concentration bounds for two-player games on the uniform distribution and k-player free games, against quantum strategies. \n \n- A proof that given a quantum interactive proof system with parameters α (the probability with which the verifier can be convinced to accept when they should accept) and β (the soundness error), as long as α > β, both the soundness error and completeness error can be reduced exponentially by repeating the protocol in parallel and requiring an (α + β)/2 fraction of the repetitions to be won. Our result requires a log-factor more repetitions than are necessary in the classical case.