論文の概要: The curious case of "XOR repetition" of monogamy-of-entanglement games

• arxiv url: http://arxiv.org/abs/2509.01831v1
• Date: Mon, 01 Sep 2025 23:20:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-04 15:17:03.858692
• Title: The curious case of "XOR repetition" of monogamy-of-entanglement games
• Title（参考訳）: モノガミー・オブ・アングルメントゲームにおける「XOR繰り返し」の興味深い事例
• Authors: Andrea Coladangelo, Qipeng Liu, Ziyi Xie,
• Abstract要約: 我々は、Tomamichel, Fehr, Kaniewski, Wehner によるモノガミー・オブ・エンタングルメントゲームの「決定」変種を考える。 ランダムな推測に対する最適の優位性は、絡み合いを共有しない制限された種類の敵に対して、$n$で指数関数的に崩壊することを示す。
• 参考スコア（独自算出の注目度）: 5.3543990359738585
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this work, we consider "decision" variants of a monogamy-of-entanglement game by Tomamichel, Fehr, Kaniewski, and Wehner [New Journal of Physics '13]. In its original "search" variant, Alice prepares a (possibly entangled) state on registers $\mathsf{ABC}$; register $\mathsf{A}$, consisting of $n$ qubits, is sent to a Referee, while $\mathsf{B}$ and $\mathsf{C}$ are sent to Bob and Charlie; the Referee then measures each qubit in the standard or Hadamard basis (chosen uniformly at random). The basis choices are sent to Bob and Charlie, whose goal is to simultaneously guess the Referee's $n$-bit outcome string $x$. Tomamichel et al. show that the optimal winning probability is $\cos^{2n} {(\frac{\pi}{8})}$, following a perfect parallel repetition theorem. We consider the following "decision" variants of this game: - Variant 1, "XOR repetition": Bob and Charlie's goal is to guess the XOR of all the bits of $x$. Ananth et al. [Asiacrypt '24] conjectured that the optimal advantage over random guessing decays exponentially in $n$. Surprisingly, we show that this conjecture is false, and, in fact, there is no decay at all: there exists a strategy that wins with probability $\cos^2{(\frac{\pi}{8})} \approx 0.85$ for any $n$. - Variant 2, "Goldreich-Levin": The Referee additionally samples a uniformly random $n$-bit string $r$ that is sent to Bob and Charlie along with the basis choices. Their goal is to guess the parity of $r\cdot x$. We show that the optimal advantage over random guessing decays exponentially in $n$ for the restricted class of adversaries that do not share entanglement. A similar result was already shown by Champion et al. and \c{C}akan et al.; we give a more direct proof. Additionally, we put forward a reasonably concrete conjecture that is equivalent to exponential decay for general adversaries.
• Abstract（参考訳）: 本研究では、Tomamichel, Fehr, Kaniewski, Wehner によるモノガミー・オブ・エンタングルメントゲームの「決定」変種について考察する。 元の "search" 変種では、Alice はレジスタ上の(おそらく絡み合った)状態を作成する。 $\mathsf{ABC}$; register $\mathsf{A}$ は$n$ qubits で、Referee に送られるが、$\mathsf{B}$ と $\mathsf{C}$ は Bob と Charlie に送られる。 基本選択はBob と Charlie に送られ、その目標は Referee の $n$-bit 結果文字列 $x$ を同時に推測することである。 トマミーチェルらは最適な勝利確率が$\cos^{2n} {(\frac{\pi}{8})}$であることを示し、完全並列反復定理に従う。 Variant 1, "XOR repeatition": BobとCharlieの目標は、x$のすべてのビットのXORを推測することである。 Ananth et al [Asiacrypt '24] は、ランダムな推測よりも最適な利点は指数関数的に$n$で崩壊すると予想した。 意外なことに、この予想は偽であり、実際、崩壊することはない:任意の$n$に対して、確率$\cos^2{(\frac{\pi}{8})} \approx 0.85$で勝利する戦略が存在する。 - Variant 2 "Goldreich-Levin": The Refereeはさらに、Bob と Charlie に送信される一様ランダムな$n$-bit string $r$を基底選択とともにサンプリングする。 彼らの目標は$r\cdot x$のパリティを推測することである。 ランダムな推測に対する最適の優位性は、絡み合いを共有しない制限された種類の敵に対して、$n$で指数関数的に崩壊することを示す。 同様の結果は Champion et al と \c{C}akan et al によって既に示されており、より直接的な証明が得られている。 さらに、一般の敵に対する指数的減衰と等価な、合理的に具体的な予想を提示した。

関連論文リスト

• Winning Rates of $(n,k)$ Quantum Coset Monogamy Games [9.029985847202669]
  我々は$(n,k)$ Coset Monogamy Gameを定式化し、2人のプレイヤーが通信せずにランダムなコセット状態から補完情報を抽出しなければならない。 我々のゲームは、等しい情報サイズ$(k=fracn2)$の場合に対処する以前の作品で考慮されたものを一般化する。
  論文  参考訳（メタデータ） (2025-01-29T16:21:34Z)
• Approximate quantum 3-colorings of graphs and the quantum Max 3-Cut problem [0.0]
  各同期非局所ゲーム $mathcalG=(I,O,lambda)$ with $|I|=n$ and $O=m geq 3$ に対して、関連するグラフ $G_lambda$ が存在することを証明している。 また、グラフの非可換Max-$3$-Cutが$E|$か$E|$以下の$alpha |E|$がRE-hardかどうかを判定する$alpha in (0,1)$が存在することを証明している。
  論文  参考訳（メタデータ） (2024-12-27T02:05:37Z)
• Sharp Noisy Binary Search with Monotonic Probabilities [5.563988395126509]
  我々はKarpとKleinbergのノイズの多いバイナリ検索モデルを再検討する。 我々は[ frac1C_tau, varepsilon cdot left(lg n + O(log2/3 n log 1/3 frac1delta + log frac1delta)右から1-delta$の確率で成功するアルゴリズムを作成する。
  論文  参考訳（メタデータ） (2023-11-01T20:45:13Z)
• Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs [72.40181882916089]
  我々のアルゴリズムが $tildeObig((d+log (|mathcalS|2 |mathcalA|))sqrtKbig)$ regret with full-information feedback, where $d$ is the dimension of a known feature mapping is linearly parametrizing the unknown transition kernel of the MDP, $K$ is the number of episodes, $|mathcalS|$ and $|mathcalA|$ is the standardities of the state and action space。
  論文  参考訳（メタデータ） (2023-05-15T05:37:32Z)
• Online Learning with Adversaries: A Differential-Inclusion Analysis [52.43460995467893]
  我々は,完全に非同期なオンラインフェデレート学習のための観察行列ベースのフレームワークを提案する。 我々の主な結果は、提案アルゴリズムがほぼ確実に所望の平均$mu.$に収束することである。 新たな差分包摂型2時間スケール解析を用いて,この収束を導出する。
  論文  参考訳（メタデータ） (2023-04-04T04:32:29Z)
• Near-Optimal Learning of Extensive-Form Games with Imperfect Information [54.55092907312749]
  本稿では,2プレイヤーゼロサムゲームにおいて,$widetildemathcalO((XA+YB)/varepsilon2)$プレイのエピソードのみを必要とするアルゴリズムの最初の行を,$varepsilon$-approximate Nash平衡を求める。 これにより$widetildemathcalO((X2A+Y2B)/varepsilon2)$が$widetildemathcalO(maxX,
  論文  参考訳（メタデータ） (2022-02-03T18:18:28Z)
• Experimental test of Tsirelson's bound with a single photonic qubit [8.8709589922781]
  Clauser-Horne-Shimony-Holt ゲームでは、Alice と Bob はそれぞれ古典的なビット $a$ と $b$ を割り当てられる。 ゲームでは、プレイヤーが古典的な戦略を使用する場合、最適な成功確率は$w(textCHSH)=0.75$である。 ポープスクとローリッヒは、完全成功確率1ドルは、符号なしの仮定に違反することなくより一般的な理論でも達成できると述べた。
  論文  参考訳（メタデータ） (2022-01-25T09:06:53Z)
• Nonlocal games with noisy maximally entangled states are decidable [5.076419064097734]
  本稿では,非ローカルゲームの特別なクラスである$(G,psi)$について考察する。 ゲーム $(G,psi)$ では、プレイヤーは任意の数の $psi$ のコピーを共有することができる。 任意の精度で$omega*(G,psi)$を計算できる。
  論文  参考訳（メタデータ） (2021-08-20T12:25:55Z)
• 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)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。 我々はCIFARに関する実験結果を示し,その理論を検証した。
  論文  参考訳（メタデータ） (2020-02-08T22:02:14Z)

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

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