論文の概要: Parallel Repetition for Entangled Games via Conditional Relative Entropy

• arxiv url: http://arxiv.org/abs/2610.21410v1
• Date: Thu, 15 Oct 2026 07:26:17 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-16 19:13:16.250902
• Title: Parallel Repetition for Entangled Games via Conditional Relative Entropy
• Title（参考訳）: 条件付き相対エントロピーによるエンタングルゲームに対する並列反復
• Abstract要約: 有限二プレーヤ交絡ゲームに対する立方体並列繰り返しの証明を与える。 我々の情報料金は、質問基準が破棄されたときの相対エントロピーの減少である。
• 参考スコア（独自算出の注目度）: 3.731168012111834
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.
• Abstract（参考訳）: 量子条件付き相対エントロピーを用いた有限2プレーヤ交絡ゲームに対する立方体並列繰り返し境界の証明を与える。 絡み合う値が 1-\varepsilon<1$ で、応答アルファベットが $\mathcal A,\mathcal B$ の場合、その$n$-fold の繰り返し値は最大 \[ \exp[-Ω(\varepsilon^3n/L)],\qquad L:=\max\{1,\log(|\mathcal A|\mathcal B|)\}, \] である。 これは宋の立方率を回復させる。 少なくとも1-\varepsilon+δ$は、$0<δ\le\varepsilon$に対して少なくとも$\exp[-Ω(δ^5n/(\varepsilon^2L))]$である。 我々の情報料金は、質問基準が破棄されたときの相対エントロピーの減少である。 我々の比較状態は、元の条件付き質問法を保存する。 チェーンルールは、チェックされた勝利の条件付けとチェックされた回答の保持のコストを用いて、座標電荷をバウンドする。 我々のメインの補題は、小さな電荷を近くの純状態の記述と局所的な補正に変換し、それぞれが1人のプレイヤーの質問にのみ依存する。 Songのサンプルとともに、これらは条件付きワークスペースのおよその局所的な準備を可能にする。

関連論文リスト

• Nearly Sample-Optimal Estimators for Quantum Rényi and Tsallis Entropies [14.968127458030251]
  我々は、ほぼ最適なサンプル複雑性を持つ量子レニイとツァリスのエントロピーを推定する。 0$の場合、サンプル複雑性は、Rényiエントロピーが$O(d1+1//varepsilon1/ + d1/-1/varepsilon2)、Tsallisエントロピーが$O(d1+1//varepsilon1/)である。
  論文  参考訳（メタデータ） (2026-08-18T17:56:22Z)
• The Physical Cutoff Does Not Restore Homogenization: Phase-Dependent Burning in the Strain G-Equation [2.538209532048867]
  C2$非圧縮性周期フローに対して、すべての$varepsilon$-ward barrier certificateが半径を少なくとも2dvarepsilon$でカバーしていることを証明している。
  論文  参考訳（メタデータ） (2026-08-15T17:41:14Z)
• The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
  AxiotisとSviridenkoは[AS21]において、凸最適化における制限条件数への線形依存はスパース時間アルゴリズムでは改善できないと推測した。 我々は、最小二乗目的に対する予想下界を確立し、ランダム化された完全体積小セット展開仮説に基づく条件付けを行う。
  論文  参考訳（メタデータ） (2026-08-03T17:57:01Z)
• The Sample Complexity of Fidelity Estimation to a Known Rank-$r$ Reference State Is $\widetildeΘ(r^2/\varepsilon^2)$ [0.0]
  量子スペクトル推定の精度を一定に抑えるために、ほぼ四分法以下の$widetilde(r2)$を証明した。 また、量子スペクトル推定を一定精度で行うために、ほぼ四分法以下の$widetilde(r2)$を証明した。
  論文  参考訳（メタデータ） (2026-08-03T06:43:01Z)
• Near-Optimal Dimension Lower Bounds for Single-Vector Embeddings of Maximum Inner Product Similarity [75.14269295861845]
  シングルトンクエリでは、Chamferは最大内部積類似度(MAX-IP)になる。 すべての固定$in(0,1)$に対して、定数は$A_,c_>0$である。 単位球MAX-IPマトリクスは、DNFパターンマトリクスの正確な2値アフィンイメージであり、少なくとも8ドルのギャップがある。
  論文  参考訳（メタデータ） (2026-07-22T17:27:20Z)
• Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits [55.957560311008926]
  そこで本研究では,各文脈の平均値によって腕の質を計測するPSLBモデルを提案する。 PS$varepsilon$BAI$+$は、$varepsilon$-optimal armを、確率$ge 1-delta$と最小限のサンプルで識別することが保証される。
  論文  参考訳（メタデータ） (2024-10-10T06:15:42Z)
• Estimation of Entropy in Constant Space with Improved Sample Complexity [14.718968517824756]
  サンプルの複雑さを$(k/epsilon2)cdot textpolylog (1/epsilon)$に削減する新しい定数メモリスキームを提供する。 これは$textpolylog (1/epsilon)$ factorまで最適であると推測する。
  論文  参考訳（メタデータ） (2022-05-19T18:51:28Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
  論文  参考訳（メタデータ） (2022-03-17T23:52:08Z)
• Learning low-degree functions from a logarithmic number of random queries [77.34726150561087]
  任意の整数 $ninmathbbN$, $din1,ldots,n$ および任意の $varepsilon,deltain(0,1)$ に対して、有界関数 $f:-1,1nto[-1,1]$ に対して、少なくとも$d$ の次数を学ぶことができる。
  論文  参考訳（メタデータ） (2021-09-21T13:19:04Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• A Direct Product Theorem for One-Way Quantum Communication [6.891238879512672]
  一般関係 $fsubseteqmathcalXtimesmathcalYtimesmathcalZ$ の一方交絡支援量子通信複雑性に対する直積定理を証明する。 私たちが知っている限りでは、これは量子通信に対する最初の直接積定理である。
  論文  参考訳（メタデータ） (2020-08-20T13:31:41Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。