Fugu-MT 論文翻訳(概要): Approximating the quantum value of an LCS game is RE-hard

論文の概要: Approximating the quantum value of an LCS game is RE-hard

arxiv url: http://arxiv.org/abs/2507.22444v1
Date: Wed, 30 Jul 2025 07:43:17 GMT
ステータス: 翻訳完了
システム内更新日: 2025-07-31 16:14:18.067953
Title: Approximating the quantum value of an LCS game is RE-hard
Title（参考訳）: LCSゲームの量子値の近似はre-hardである
Authors: Aviv Taller, Thomas Vidick,
Abstract要約: プロジェクションゲームに対するHrastadの長期コードテストの一般化を行う。完全であり、絡み合ったプローバーに対して健全であることを示す。
参考スコア（独自算出の注目度）: 4.31241676251521
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We generalize H\r{a}stad's long-code test for projection games and show that it remains complete and sound against entangled provers. Combined with a result of Dong et al. \cite{Dong25}, which establishes that $\MIP^*=\RE$ with constant-length answers, we derive that $\LIN^*_{1-\epsilon,s}=\RE$, for some $1/2< s<1$ and for every sufficiently small $\epsilon>0$, where LIN refers to linearity (over $\mathbb{F}_2$) of the verifier predicate. Achieving the same result with $\epsilon=0$ would imply the existence of a non-hyperlinear group.
Abstract（参考訳）: 我々は、H\r{a}stadの射影ゲームに対する長符号テストを一般化し、それが完備であり、絡み合ったプローバーに対して健全であることを示す。 Dong et al \cite{Dong25} の結果と組み合わさって、$\MIP^*=\RE$ が一定長の解を持つことを証明し、$\LIN^*_{1-\epsilon,s}=\RE$ が約 $1/2< s<1$ およびすべての十分小さな $\epsilon>0$ に対して与えられる。同じ結果を$\epsilon=0$で達成することは、非超線型群の存在を意味する。

関連論文リスト

Learning and Computation of $Φ$-Equilibria at the Frontier of Tractability [85.07238533644636]
$Phi$-equilibriaは、オンライン学習とゲーム理論の中心にある、強力で柔軟なフレームワークだ。効率的なオンラインアルゴリズムは、$textpoly(d, k)/epsilon2$ラウンドを使用して、平均$Phi$-regretを最大$epsilon$で生成することを示す。また、オンライン設定において、ほぼ一致した下限を示し、その結果、$Phi$-regretの学習可能性を取得する偏差の族が初めて得られる。
論文参考訳（メタデータ） (2025-02-25T19:08:26Z)
Learning junta distributions, quantum junta states, and QAC$^0$ circuits [0.0]
本稿では, 量子分布(量子ユンタ状態)と$mathsfQAC0$回路の学習問題を考察する。例えば$n$-qubit $mathsfQAC0$の回路は$s$、deep $d$、$a$の補助キュービットは2O(log(s22a)d)log (n)$のChoi状態のコピーから学習可能であることを示す。
論文参考訳（メタデータ） (2024-10-21T09:39:20Z)
Monge-Kantorovich Fitting With Sobolev Budgets [6.748324975906262]
我々は、$rho$が$mtext-d$集合の近くに集中しているとき、これをノイズのあるデータを持つ多様体学習問題と解釈できることを示した。 Monge-Kantorovich $p$-cost $mathbbW_pp(rho, nu)$を介して$rho$を近似する際の$nu$のパフォーマンスを定量化し、$mathrmsupp nu$を$f : mathbbRmでカバーできるようにすることで複雑さを制限します。
論文参考訳（メタデータ） (2024-09-25T01:30:16Z)
Dimension Independent Disentanglers from Unentanglement and Applications [55.86191108738564]
両部非絡み込み入力から次元独立なk-パーティイトディジアンタングル(類似)チャネルを構築する。 NEXP を捉えるためには、$| psi rangle = sqrta | sqrt1-a | psi_+ rangle という形の非負の振幅を持つのに十分であることを示す。
論文参考訳（メタデータ） (2024-02-23T12:22:03Z)
Area laws and tensor networks for maximally mixed ground states [4.527719466355631]
一般ハミルトニアンの地上空間において、最大混合状態$Omega$の相互情報に地域法則を示す。類似性は、2次元フラストレーションのない局所的ハミルトン多様体の相互情報から導かれる。
論文参考訳（メタデータ） (2023-10-29T14:36:30Z)
A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文参考訳（メタデータ） (2023-09-25T17:54:19Z)
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)
On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文参考訳（メタデータ） (2020-02-09T03:39:46Z)

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