PaperlayerView exact revision on arXiv

Source-linked AI summary

Parallel Repetition for Entangled Games via Conditional Relative Entropy

Rahul Jain

arXiv:2610.21410v1quant-phcs.CCcs.ITmath.IT

TL;DR

The paper targets a cubic parallel-repetition proof for entangled games under arbitrary question distributions. It uses comparison states that preserve the original conditional question law, telescopes coordinate charges, and converts small charges into local pure-state descriptions. The proof bounds the repeated value by exp[−Ω(ε^3n/L)], arising from a quadratic information threshold and a linear rejection threshold.

  • Problem

    The paper targets a cubic parallel-repetition proof for entangled games under arbitrary question distributions.

    Source: §1 · p. 2

  • Method

    It uses comparison states that preserve the original conditional question law, telescopes coordinate charges, and converts small charges into local pure-state descriptions.

    Source: §1 · p. 2, §1.5 · p. 7

  • Results

    The proof bounds the repeated value by exp[−Ω(ε^3n/L)], arising from a quadratic information threshold and a linear rejection threshold.

    Source: §1.6 · p. 8

  • Takeaways & Limitations

    The comparison framework yields local preparation without requiring full-support or smallest-eigenvalue hypotheses.

    Source: §1 · p. 2, §4.1 · p. 27

    The descriptions, corrections, resources, and preparation maps are fixed before questions arrive, with each player’s choices depending only on their own question.

    Source: §4 · p. 25

Abstract

from arXiv · show

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[-\Omega(\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+\delta$ is at most $\exp[-\Omega(\delta^5n/(\varepsilon^2L))]$ for $0<\delta\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.

1 Introduction

The section presents a conditional-relative-entropy approach to cubic parallel repetition and a threshold bound for finite two-player entangled games, including the extraction argument that prepares the conditioned workspace from local descriptions and corrections. It also contrasts this conditional-comparison proof with earlier approaches.

1 Introduction

  • The paper gives a different proof of the cubic bound, using conditional comparison states that preserve the original question law and yield compatible pure-state descriptions for each player.A chain rule cancels intermediate relative entropies, leaving a parent bound that supports local preparation of the conditioned workspace.Source: §1 · p. 2

1.1 All-win and threshold repetition

  • The cited theorem announces a cubic-repetition result using Song’s sampler for every finite two-player game with ε>0 and every integer n≥1.Source: §1.1 · p. 2
  • For every finite-dimensional repeated strategy and 0<δ≤ε, the paper gives a universal threshold rate Ω(δ^5/L), improving [14]’s universal rate by a factor of 1/ε^2 in gap dependence.Source: §1.1 · pp. 2–3

1.2 Proof strategy: extraction and conditioning

  • The extraction step converts high success on unchecked coordinates conditioned on checked wins into a single-game strategy using fresh questions from μ.Preparation and question-law errors are controlled by the cost of conditioning on checked wins and retaining checked answers; sufficiently small errors force unchecked rejection probability Ω(ε).Source: §1.2 · p. 3

1.3 The conditional relative-entropy charge

  • The quantum conditional relative-entropy charge preserves the original conditional question law while allowing each comparison to depend locally on its player’s question.This avoids charging prior question correlations or missing phase dependence; for fixed workspaces it can vanish even under correlated question sources.Source: §1.3 · pp. 5–6

1.4 Conditioning and allocation of the charge

  • A chain rule expresses each coordinate charge as a difference of successive relative entropies, so each player’s total charge is at most the parent bound BC.The separate D(q_i∥μ) bound pays for changing to fresh questions from μ during extraction, since conditional charges need not control the joint question law for correlated μ.Source: §1.4 · p. 7

1.5 From the information budget to local preparation

  • Small information charges yield compatible local pure-state descriptions and local corrections, enabling approximate preparation of the conditioned workspace.Song’s sampler prepares one player’s description approximately; the players’ question-dependent corrections then connect it to the target workspace.Source: §1.5 · pp. 7–8

1.6 Completing extraction and repetition

  • The extracted strategy prepares history correlations in the workspace and answers fresh questions using local maps on a shared unchecked coordinate and its preparation resource.The designated answer registers reproduce coordinates of the conditioned strategy, and every such legal strategy rejects with probability at least ε.Source: §1.6 · p. 8
  • exp[-Ω(ε^3 n/L)] bounds the n-fold repeated value, using checked-coordinate rejection and balancing its decrease against the growth of the information budget.The extraction estimate yields unchecked rejection Ω(ε) while the information threshold is a sufficiently small universal multiple of ε^2; each check then reduces p_C by a factor 1 − Ω(ε).Source: §1.6 · p. 8

1.7 Comparison with the previous proofs

  • Unlike the reveal-process approach refined by Song, this proof derives pure descriptions from conditional comparisons and local corrections, while preparing history correlations with the remaining workspace.Both arguments use Song’s sampling bound; the comparison is summarized in Table 1. Earlier conditional-relative-entropy applications include classical strong direct-product results and channel-loss results [18, 19, 20, 21, Theorem 3.12].Source: §1.7 · p. 9, Table 1 · p. 9

2 Preliminaries and information-theoretic tools

This section fixes the finite-dimensional setting and conventions used for games, states, entropy, and distance. It also specifies how conditioning and copied question registers are represented.

2 Preliminaries and information-theoretic tools

  • The framework assumes finite-dimensional systems and collects estimates used for conditioning, local preparation, and extraction.Source: §2 · p. 10

2.1 Games and information conventions

  • A finite two-player game specifies question alphabets, answer alphabets, a question law, and a binary predicate; repetition samples question pairs independently and requires every coordinate to be won.Source: §2.1 · p. 10
  • Relative entropy is defined for density operators, with support inclusion required when finite divergences are subtracted; the conventions also distinguish relative, measured, and max-relative entropy.Source: §2.1 · p. 10
  • The notation fixes purified distance, fidelity, and infidelity conventions, and matching-copy support restricts question-copy registers to equal-label basis states.Source: §2.1 · pp. 10–11
  • Conditioning subscripts identify records used to condition a state, while omitted conditioning registers are traced out; hats mark basis-copy registers and protected references are specified separately.Source: §2.1 · p. 11

2.2 Copied-input families and conditional comparisons

Copied-input families encode question-conditioned workspaces while preserving the prescribed question law. Conditional comparison states retain coherent dependence on one player’s local question and support pure-state descriptions used for local reconstruction.

2.2 Copied-input families and conditional comparisons

  • A copied-input family associates a workspace vector with each question pair and stores both questions in protected matching-copy registers.Source: §2.2 · p. 11
  • An Alice conditional comparison uses a local state with matching-copy support and applies the prescribed conditional law of Bob’s question while retaining coherent blocks across Alice’s questions.Source: §2.2 · p. 12
  • The comparison has an equivalent purification form using a distribution over Alice’s questions and a question-indexed family of pure vectors; the symmetric characterization holds for Bob.Source: §2.2 · p. 12
  • The joint choice of question-indexed vectors determines coherent off-diagonal blocks, so independently chosen canonical purifications can change the comparison state.Source: §2.2 · p. 13
  • Conditional relative entropy measures the divergence lost when the question reference is traced out, and local preparation restricts each player’s channel to that player’s own question.Source: §2.2 · p. 13

2.3 Distances and rejection probabilities

This section relates state-preparation error to rejection probability and records the distance inequalities used in that transfer. It also handles finite families whose question law changes.

2.3 Distances and rejection probabilities

  • The square-root rejection comparison bounds the change in rejection probability using purified distance between the states.Source: §2.3 · pp. 13–14
  • Relative entropy and purified distance contract under channels, purified distance obeys the triangle inequality, and divergence bounds purified-distance error for normalized states.Source: §2.3 · pp. 13–14
  • For a family of states and effects indexed by questions, the rejection estimates extend to averages under different label laws, with data processing controlling the law-change term.Source: §2.3 · p. 14
  • Block fidelity relates the fidelity of mixtures to their component blocks, and zero-probability blocks may be completed arbitrarily.Source: §2.3 · p. 14

2.4 Canonical purifications

Canonical purifications place local density descriptions in a fixed vector convention, allowing the sampler to use nearby vectors. Uhlmann’s theorem supplies local isometric corrections to the desired purifications.

2.4 Canonical purifications

  • Canonical purifications use a fixed reference basis and vectorization convention, independent of eigenbasis choices within degenerate eigenspaces.Source: §2.4 · p. 15
  • For two purifications of states on the same subsystem, Uhlmann’s theorem supplies an isometry on the purifying system after finite padding.Source: §2.4 · p. 15
  • A local isometric correction can align an approximate preparation with the desired purification, and only the correcting party must know that target purification.Source: §2.4 · p. 15
  • When local density descriptions have mean squared purified-distance error e, their canonical vectors have mean squared discrepancy at most 2e.Source: §2.4 · p. 15

2.5 Classical and classical–quantum information

This section collects information identities used to track conditioning and question-distribution changes, then presents correlated sampling for locally described states.

2.5 Classical and classical–quantum information

  • For finite classical Z, conditional entropy lies between 0 and log |Z|, and the stated divergence identities also apply after fixing and averaging over a classical record.The averaging uses the actual target distribution.Source: §2.5 · p. 16
  • The JPY postselection and product-marginal identities provide tools for relating conditioned distributions and coordinate marginals.The section also states Rao’s conditional-success concentration bound for events without assuming independence.Source: §2.5 · pp. 16–17

2.6 Correlated sampling

  • Song’s sampler turns two nearby local descriptions into a shared approximation using finite, input-independent shared resources and local channels that depend on each player’s description.The resources and maps are fixed before the labels arrive; the guarantee concerns the designated output after tracing environments.Source: §2.6 · p. 17
  • The section gives an optimized parameter choice for Song’s sampling estimate, with finite resources also available at zero distance.For D ≥ 1/16, the stated cap follows from probability being at most one.Source: §2.6 · p. 17

2.7 Conditioning and the parent divergence budget

The section bounds the divergence cost of conditioning on a finite record and event, then allocates parent divergence across ordered coordinate comparisons by telescoping.

2.7 Conditioning and the parent divergence budget

  • Conditioning on an event determined by H and finite record Z yields a bound charging Z and the event, but not the alphabet of H.The bound also holds for corresponding reduced systems.Source: §2.7 · pp. 17–18

2.8 Chain rule and ordered conditional comparisons

  • The ordered chain rule expresses coordinate charges through successive relative entropies, whose intermediate terms cancel when summed.For the retained-record identity, the average uses the target record law rather than the comparison law.Source: §2.8 · pp. 18–19
  • Conditioning and tracing preserve the comparison form at each supported coordinate, with Bob’s allocation using the reverse coordinate order.The prior factors across coordinates, allowing the comparison map to factor into the selected-coordinate map and the maps for other references.Source: §2.8 · pp. 18–19

2.9 Information controlled by conditional relative entropy

The section relates conditional relative-entropy charges to information about the other player’s question, and introduces matrix tools for replacing a comparison marginal.

2.9 Information controlled by conditional relative entropy

  • A conditional charge lower-bounds the information between the other player’s question and a player’s residual system, plus a divergence between question laws.For copied-input families the left-hand side is the Alice charge; interchanging players gives the corresponding Bob bound.Source: §2.9 · p. 19
  • When both states are diagonal, the information inequality is an equality because tracing the copied question register is reversible by copying it back.The proof uses data processing followed by the chain rule.Source: §2.9 · pp. 19–20

2.10 Matrix tools for marginal replacement

  • The matrix tools are introduced to replace the comparison’s local marginal and turn a conditional charge into a fidelity estimate.They include a four-matrix trace inequality and variational formulas for relative and measured divergences.Source: §2.10 · p. 20

3 Extraction objective and conditional information budget

The section sets up extraction from a strategy conditioned on checked wins and allocates its divergence budget across coordinate views. Its target is approximate preparation of an unchecked coordinate’s conditional workspace on fresh questions.

3.1 The extraction objective

  • The extraction objective bounds the gap between √ε and √AC by Cext t^1/4; sufficiently small t forces AC ≥ ε/4, the rejection guarantee needed for greedy checking.The preparation target is the conditional workspace of a uniformly chosen unchecked coordinate on fresh questions from μ.Source: §3.1 · p. 21

3.2 The two global states and their parent marginals

  • The preselection and postselection states encode the strategy before and after conditioning on checked wins, while parent comparisons condition on checked questions and average over checked answers.The target conditions on the checked-answer value; the comparison averages over checked answers conditional on the checked questions.Source: §3.2 · p. 21

3.3 Coordinate targets and conditional relative-entropy charges

  • Each coordinate view partitions the postselection state into a protected question reference and residual workspaces, with a comparison that averages over checked answers.The extracted strategy prepares the residual workspaces from fresh questions; the protected reference is used only in the conditional relative entropies.Source: §3.3 · pp. 22–23

3.4 Conditioning and allocation of the charge

  • The budget proof conditions on the checked-win event, allocates the parent divergence through retained-record and ordered-chain identities, and bounds the coordinate charges.The coordinate views are consistent targets, and the local isometries preserve the original question law for the separate question-law bound.Source: §3.4 · pp. 23–24

4 Local preparation from conditional relative entropy

The section turns small conditional-relative-entropy charges into local pure-state descriptions and corrections, then uses those descriptions to obtain approximate preparation. Marginal replacement preserves the conditional comparison while matching a retained marginal.

4 Local preparation from conditional relative entropy

  • A total charge s = bA + bB yields mean infidelity O(√s) for local preparation, using pure descriptions and question-dependent corrections.Alice’s descriptions and corrections depend only on x, and Bob’s only on y; the preparation guarantee is obtained with finite resources.Source: §4 · p. 25
  • Song’s sampler turns the nearby pure descriptions into an approximate preparation of the conditional workspace.The proof derives the preparation estimate from the pure descriptions and extends it to finite-resource preparations.Source: §4 · p. 25

4.1 Marginal replacement for conditional comparisons

  • Marginal replacement matches the retained marginal while bounding measured divergence by the decrease in full relative entropy.The replacement can preserve the Alice conditional-comparison form for the original question law.Source: §4.1 · p. 27
  • The replacement and conditional-comparison preservation require neither a full-support nor a smallest-eigenvalue hypothesis.Source: §4.1 · p. 27

5 Completing extraction and repetition

The paper combines an information budget with local preparation to extract a single-game strategy under fresh questions. Its rejection bound supports all-win repetition by greedy checking and threshold repetition by concentration.

5 Completing extraction and repetition

  • The extraction estimate and local preparation provide the single-game strategy used to establish the repetition bounds.Source: §5 · p. 28

5.1 Single-copy extraction under fresh questions

  • Under the stated charge and question-law budgets, the extracted strategy uses fresh questions and has rejection probability at least ε.The strategy shares a uniformly chosen unchecked coordinate and its preparation resource before receiving questions.Source: §5.1 · pp. 28–29

5.2 All-win repetition

  • ω*(G⊗n) ≤ exp[−csmε^3n/L] is the all-win repetition bound obtained by substituting the checking thresholds.Source: §5.2 · p. 30

5.3 Threshold parallel repetition

  • For 0 < δ ≤ ε, Corollary 5.2 gives a universal threshold bound for N, the number of won coordinates.The proof applies Rao’s concentration bound to the extraction estimate.Source: §5.3 · p. 31

A Product-question specialization

For product question laws, the appendix identifies the optimized conditional-comparison charge with a mutual-information term and a marginal question divergence. The posterior need not be product, and the identity does not change the comparisons used in allocation.

A Product-question specialization

B Parameter correspondence for Rao’s concentration bound

The appendix verifies the conditional-success form of Rao’s bound, including constants and rounding. It tracks conditional success until a probability cutoff, then uses random subsets and threshold-event counting.

B Parameter correspondence for Rao’s concentration bound

Loading 2610.21410v1…