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−ϵ), 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) (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) 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<δ<ϵ, the probability that the players win a
(1−ϵ+δ) fraction of the games in the parallel repetition is at most
exp(−Ωϵ(δ3n/c)) (here the constant may depend on
ϵ); 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
ϵ. By the recent work of Raz [Proceedings of the
49th 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−ϵ) into a two-query PCP with answer length
ck, size
O(ck(2s)k), and soundness
(1−ϵ/2q)Ω(ϵk/q). Another consequence of our bound is that the unique games conjecture of Khot [Proceedings of the
34th 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+ such that for every
ϵ>0, there exists an alphabet size
M(ϵ) for which it is NP-hard to distinguish a unique game with alphabet size M in which a
(1−ϵ2) fraction of the constraints can be satisfied from one in which a
(1−ϵf(1/ϵ)) fraction of the constraints can be satisfied.
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−ε<1 and answer alphabets
A,B, its
n-fold repeated value is at most
exp[−Ω(ε3n/L)],L:=max{1,log(∣A∣∣B∣)}, for every
n≥1. This recovers Song's cubic rate. We also prove a threshold bound: the probability of winning a fraction at least
1−ε+δ is at most
exp[−Ω(δ5n/(ε2L))] for
0<δ≤ε.
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.
We study the behavior of the entangled value of two-player one-round projection games under parallel repetition. We show that for any projection game G of entangled value 1 - εc)k), for some universal constant c ≥ 1. Previously parallel repetition with an exponential decay in k was only known for the case of XOR and unique games. To prove the theorem we extend an analytical framework recently introduced by Dinur and Steurer for the study of the classical value of projection games under parallel repetition. Our proof, as theirs, relies on the introduction of a simple relaxation of the entangled value that is perfectly multiplicative. The main technical component of the proof consists in showing that the relaxed value remains tightly connected to the entangled value, thereby establishing the parallel repetition theorem. More generally, we obtain results on the behavior of the entangled value under products of arbitrary (not necessarily identical) projection games. Relating our relaxed value to the entangled value is done by giving an algorithm for converting a relaxed variant of quantum strategies that we call “vector quantum strategy” to a quantum strategy. The algorithm is considerably simpler in case the bipartite distribution of questions in the game has good expansion properties. When this is not the case, rounding relies on a quantum analogue of Holenstein's correlated sampling lemma which may be of independent interest. Our “quantum correlated sampling lemma” generalizes results of van Dam and Hayden on universal embezzlement to the following approximate scenario: two isolated parties, given classical descriptions of arbitrary bipartite states |ψ〉, |φ〉 respectively such that |ψ〉 ≈ |φ〉, are able to locally generate a joint entangled state|Ψ〉 ≈ |ψ〉 ≈ |φ〉 using an initial entangled state that is independent of their inputs.
We study interactive multiprover games and many-round protocols in which the communication between the verifier and the provers is quantum. Parallel repetition is known to suppress soundness error of classical two-prover games arbitrarily close to zero, as shown by Raz (STOC '95), even with quantum strategies as shown by Yuen (ICALP '16), and Bavarian, Vidick and Yuen (STOC '17). Yet, we show that quantum communication can have the opposite, unexpected effect. Specifically, we exhibit a one-round quantum game and two-round
QMIP protocols whose local (unentangled) value is strictly less than one for a single instance, yet equals one under
n-fold parallel repetition for every
n≥2. The key is that parallel repetition not only imposes additional winning conditions but also supplies additional quantum resources as entanglement in the exchanged states can be exploited jointly across copies.
Our multiround examples build on superactivation of zero-error capacities of quantum channels. To establish this connection, we introduce quantum games and interactive protocols which capture the one-shot zero-error classical and quantum capacities, both with and without entanglement assistance. Our constructions use quantum-state verification and a teleportation-based reduction from two rounds to one.
In contrast, when shared entanglement is allowed, we show that parallel repetition cannot increase the entangled value when at most
3 messages are exchanged, consistent with classical results of Bellare, Impagliazzo and Naor (FOCS '97), and that of single-prover systems by Kitaev and Watrous (STOC '00). Combining this monotonicity with our quantum game-channel correspondence, we show that entanglement-assisted zero-error classical and quantum capacities cannot be superactivated.
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.
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.