論文の概要: Nonlocal games with noisy maximally entangled states are decidable

• arxiv url: http://arxiv.org/abs/2108.09140v1
• Date: Fri, 20 Aug 2021 12:25:55 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-17 23:01:59.562821
• Title: Nonlocal games with noisy maximally entangled states are decidable
• Title（参考訳）: 雑音極大絡み状態を持つ非局所ゲームは決定可能である
• Authors: Minglong Qin and Penghui Yao
• Abstract要約: 本稿では,非ローカルゲームの特別なクラスである$(G,psi)$について考察する。 ゲーム $(G,psi)$ では、プレイヤーは任意の数の $psi$ のコピーを共有することができる。 任意の精度で$omega*(G,psi)$を計算できる。
• 参考スコア（独自算出の注目度）: 5.076419064097734
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper considers a special class of nonlocal games $(G,\psi)$, where $G$ is a two-player one-round game, and $\psi$ is a bipartite state independent of $G$. In the game $(G,\psi)$, the players are allowed to share arbitrarily many copies of $\psi$. The value of the game $(G,\psi)$, denoted by $\omega^*(G,\psi)$, is the supremum of the winning probability that the players can achieve with arbitrarily many copies of preshared states $\psi$. For a noisy maximally entangled state $\psi$, a two-player one-round game $G$ and an arbitrarily small precision $\epsilon>0$, this paper proves an upper bound on the number of copies of $\psi$ for the players to win the game with a probability $\epsilon$ close to $\omega^*(G,\psi)$. Hence, it is feasible to approximately compute $\omega^*(G,\psi)$ to an arbitrarily precision. Recently, a breakthrough result by Ji, Natarajan, Vidick, Wright and Yuen showed that it is undecidable to approximate the values of nonlocal games to a constant precision when the players preshare arbitrarily many copies of perfect maximally entangled states, which implies that $\mathrm{MIP}^*=\mathrm{RE}$. In contrast, our result implies the hardness of approximating nonlocal games collapses when the preshared maximally entangled states are noisy. The paper develops a theory of Fourier analysis on matrix spaces by extending a number of techniques in Boolean analysis and Hermitian analysis to matrix spaces. We establish a series of new techniques, such as a quantum invariance principle and a hypercontractive inequality for random operators, which we believe have further applications.
• Abstract（参考訳）: 本稿では,非ローカルゲームの特別なクラスである$(g,\psi)$を考える。ここでは$g$は2人プレイのワンラウンドゲームであり,$\psi$は$g$とは独立した2部制である。 ゲーム$(G,\psi)$では、プレイヤーは任意の数の$\psi$のコピーを共有することができる。 ゲーム $(G,\psi)$ の値は$\omega^*(G,\psi)$ で表され、プレイヤーが任意の数のプレシェイド状態のコピーで達成できる勝利確率の上限である。 雑音的に最大に絡み合った状態$\psi$, 2人プレイヤの1ラウンドゲーム$G$, 任意に小さな精度$\epsilon>0$に対して、この論文はプレイヤーがゲームに勝つ確率$\epsilon$を$\omega^*(G,\psi)$に近い確率で獲得するための$\psi$のコピー数に対する上限を証明している。 したがって、およそ$\omega^*(G,\psi)$を任意の精度で計算することが可能である。 最近では、Ji, Natarajan, Vidick, Wright, Yuen によるブレークスルーの結果、プレイヤーが完全最大絡み合った状態のコピーを任意に多くのコピーするときに、非局所ゲームの価値を一定の精度で近似することは決定不可能であることが示され、$\mathrm{MIP}^*=\mathrm{RE}$ となる。 対照的に,本研究の結果は,事前共有された最大絡み合い状態が雑音である場合,非局所ゲーム近似の難易度が低下することを示している。 本稿では,行列空間に対するフーリエ解析の理論を,ブール解析とエルミート解析を行列空間に拡張することによって展開する。 我々は、量子不変原理やランダム演算子に対する超収縮的不等式のような一連の新しい手法を確立し、さらなる応用があると信じている。

関連論文リスト

• Dimension Independent Disentanglers from Unentanglement and Applications [55.86191108738564]
  両部非絡み込み入力から次元独立なk-パーティイトディジアンタングル(類似)チャネルを構築する。 NEXP を捉えるためには、$| psi rangle = sqrta | sqrt1-a | psi_+ rangle という形の非負の振幅を持つのに十分であることを示す。
  論文  参考訳（メタデータ） (2024-02-23T12:22:03Z)
• $\ell_p$-Regression in the Arbitrary Partition Model of Communication [59.89387020011663]
  コーディネータモデルにおける分散$ell_p$-regression問題のランダム化通信複雑性について考察する。 p = 2$、すなわち最小二乗回帰の場合、$tildeTheta(sd2 + sd/epsilon)$ bitsの最初の最適境界を与える。 p in (1,2)$ に対して、$tildeO(sd2/epsilon + sd/mathrmpoly(epsilon)$ upper bound を得る。
  論文  参考訳（メタデータ） (2023-07-11T08:51:53Z)
• Model-Based Reinforcement Learning for Offline Zero-Sum Markov Games [18.832436856339587]
  本稿では,オフラインデータから2プレイヤーゼロサムマルコフゲームにおけるナッシュ均衡の学習に向けて前進する。 ベルンシュタイン型低信頼境界を持つ悲観的モデルベースアルゴリズム(VI-LCB-Game)を提案する。
  論文  参考訳（メタデータ） (2022-06-08T17:58:06Z)
• 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)
• Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise [9.378684220920562]
  マスアートノイズの存在下でハーフスペースを学習するための、最も厳密な統計クエリ(SQ)の下界。 任意の $eta in [0,1/2]$ に対して、$eta$ よりも誤り分類誤差の少ない全ての SQ アルゴリズムは、スーパーポリノミカルな精度のクエリを必要とすることを示す。
  論文  参考訳（メタデータ） (2022-01-24T17:33:19Z)
• When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently? [10.397170312149067]
  本稿では,m$-player General-sum Markovゲームの設定において,学習目標がより優れたサンプル複雑性を許容するものについて検討する。 まず,$epsilon$-Coarse Correlated Equilibrium (CCE)を$widetildemathcalO(H5Smax_ile m A_i / epsilon2)$ episodesで学習するアルゴリズムを設計する。 第二に、マルコフポテンシャルゲームの重要な特別な場合を考え、$widet内で$epsilon$-approximate Nash平衡を学ぶアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2021-10-08T15:06:22Z)
• A bounded-noise mechanism for differential privacy [3.9596068699962323]
  ベクトル $vecx(i) の平均 $frac1nsum_i=1n vecx(i)$ を [0,1]k$ で出力し、任意の $vecx(i)$ に対してプライバシーを保持します。 我々は、ほとんどの値$delta$に対して最適な$ell_infty$エラーを持つ$(epsilon,delta)$-privateメカニズムを示す。
  論文  参考訳（メタデータ） (2020-12-07T16:03:21Z)
• On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
  我々は、$n$ユーザのそれぞれが離散集合から要素を保持する設定について研究する。 目標は、すべてのユーザーに対して異なる要素の数を数えることだ。
  論文  参考訳（メタデータ） (2020-09-21T04:13:34Z)
• 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)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。 このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
  論文  参考訳（メタデータ） (2020-02-17T10:53:50Z)
• Complexity limitations on one-turn quantum refereed games [0.6091702876917281]
  本論文は,量子参照ゲームの理論的側面を研究する。 抽象ゲームは、審判に量子状態を送信する2人のプレーヤーの間のものである。 審判は、2つの状態に対して効率よく実施可能な共同測定を行い、どのプレイヤーが勝つかを判定する。
  論文  参考訳（メタデータ） (2020-02-04T19:28:03Z)

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

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