論文の概要: Unique Games hardness of Quantum Max-Cut, and a conjectured
vector-valued Borell's inequality
- arxiv url: http://arxiv.org/abs/2111.01254v3
- Date: Wed, 28 Sep 2022 19:24:48 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-09 16:51:51.965052
- Title: Unique Games hardness of Quantum Max-Cut, and a conjectured
vector-valued Borell's inequality
- Title（参考訳）: 量子マックスコートの特異ゲーム硬度と予想ベクトル値ボレルの不等式
- Authors: Yeongwoo Hwang, Joe Neeman, Ojas Parekh, Kevin Thompson, John Wright
- Abstract要約: 関数 $f:mathbbRn の -1, 1$ への雑音安定性は $f(boldsymbolx) cdot f(boldsymboly)$ の期待値であることを示す。
我々は $langle f(boldsymbolx), f(boldsymboly)rangle$ の期待値は、関数 $f(x) = x_leq k / Vert x_leq k / によって最小化されると予想する。
- 参考スコア（独自算出の注目度）: 6.621324975749854
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Gaussian noise stability of a function $f:\mathbb{R}^n \to \{-1, 1\}$ is
the expected value of $f(\boldsymbol{x}) \cdot f(\boldsymbol{y})$ over
$\rho$-correlated Gaussian random variables $\boldsymbol{x}$ and
$\boldsymbol{y}$. Borell's inequality states that for $-1 \leq \rho \leq 0$,
this is minimized by the halfspace $f(x) = \mathrm{sign}(x_1)$. In this work,
we generalize this result to hold for functions $f:\mathbb{R}^n \to S^{k-1}$
which output $k$-dimensional unit vectors. Our main conjecture, which we call
the $\textit{vector-valued Borell's inequality}$, asserts that the expected
value of $\langle f(\boldsymbol{x}), f(\boldsymbol{y})\rangle$ is minimized by
the function $f(x) = x_{\leq k} / \Vert x_{\leq k} \Vert$, where $x_{\leq k} =
(x_1, \ldots, x_k)$. We give several pieces of evidence in favor of this
conjecture, including a proof that it does indeed hold in the special case of
$n = k$.
As an application of this conjecture, we show that it implies several
hardness of approximation results for a special case of the local Hamiltonian
problem related to the anti-ferromagnetic Heisenberg model known as Quantum
Max-Cut. This can be viewed as a natural quantum analogue of the classical
Max-Cut problem and has been proposed as a useful testbed for developing
algorithms. We show the following, assuming our conjecture:
(1) The integrality gap of the basic SDP is $0.498$, matching an existing
rounding algorithm. Combined with existing results, this shows that the basic
SDP does not achieve the optimal approximation ratio.
(2) It is Unique Games-hard (UG-hard) to compute a
$(0.956+\varepsilon)$-approximation to the value of the best product state,
matching an existing approximation algorithm.
(3) It is UG-hard to compute a $(0.956+\varepsilon)$-approximation to the
value of the best (possibly entangled) state.
- Abstract（参考訳）: 函数 $f:\mathbb{R}^n \to \{-1, 1\}$ のガウス的雑音安定性は $f(\boldsymbol{x}) \cdot f(\boldsymbol{y})$ over $\rho$-correlated Gaussian random variables $\boldsymbol{x}$ and $\boldsymbol{y}$ の期待値である。
ボレルの不等式は、$-1 \leq \rho \leq 0$ に対して、半空間 $f(x) = \mathrm{sign}(x_1)$ によって最小化される。
本研究では、この結果を一般化して、$k$次元単位ベクトルを出力する関数 $f:\mathbb{R}^n \to S^{k-1}$ を保持する。
我々の予想は、$\textit{vector-valued Borell's inequality}$と呼ばれ、期待値 $\langle f(\boldsymbol{x}), f(\boldsymbol{y})\rangle$ は函数 $f(x) = x_{\leq k} / \Vert x_{\leq k} \Vert$ で最小化され、$x_{\leq k} = (x_1, \ldots, x_k)$ となる。
この予想を支持するいくつかの証拠を与えるが、これは実際に$n = k$の特別な場合において成り立つという証明を含む。
この予想の適用例として、量子マックスカットとして知られる反強磁性ハイゼンベルクモデルに関連する局所ハミルトン問題の特別な場合に対して、近似結果のいくつかの困難さを示すことを示す。
これは古典的マックスカット問題の自然な量子アナログと見なすことができ、アルゴリズムを開発するための有用なテストベッドとして提案されている。
1) 基本 SDP の積分性ギャップは 0.498$ であり、既存の丸めアルゴリズムと一致する。
既存の結果と組み合わせることで,基本SDPが最適近似比を達成できないことを示す。
(2) 最適生成状態の値に$(0.956+\varepsilon)$を近似し、既存の近似アルゴリズムに一致する一意なゲームハード(ug-hard)である。
(3) (0.956+\varepsilon)$を最良(おそらくは絡み合っている)状態の値に近似することは難しい。
関連論文リスト
- Sample-Efficient Linear Regression with Self-Selection Bias [7.605563562103568]
未知のインデックス設定における自己選択バイアスを伴う線形回帰の問題を考察する。
我々は,$mathbfw_1,ldots,mathbfw_kinを復元する,新しい,ほぼ最適なサンプル効率($k$)アルゴリズムを提案する。
このアルゴリズムは雑音の仮定をかなり緩めることに成功し、従って関連する最大線形回帰の設定にも成功している。
論文 参考訳（メタデータ） (2024-02-22T02:20:24Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Fitting an ellipsoid to a quadratic number of random points [12.519286388088958]
問題 $(mathrmP)$ が $n$ の標準ガウス確率ベクトルを $mathbbRd$ で中心楕円体の境界に収まることを $n, d to infty$ とみなす。
任意の$varepsilon > 0$ に対して、$n leq (1 - varepsilon) d2 / 4$ ならば、$(mathrmP)$ は高い確率の解を持つ。
論文 参考訳（メタデータ） (2023-07-03T17:46:23Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - Low-degree learning and the metric entropy of polynomials [49.1574468325115]
少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
論文 参考訳（メタデータ） (2022-03-17T23:52:08Z) - Private Convex Optimization via Exponential Mechanism [16.867534746193833]
我々は、$ellcave2$ regularizerを$F(x)$に追加することで指数的なメカニズムを変更することで、既知の最適経験的リスクと人口損失の両方を$(epsilon,delta)$-DPで回復することを示した。
また、DP-SCOに対して$widetildeO(n min(d, n))クエリを使って$f_i(x)にこのメカニズムを実装する方法を示す。
論文 参考訳（メタデータ） (2022-03-01T06:51:03Z) - Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。
我々はこの$d$への依存が対数的要因まで最適であることを示す。
また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
論文 参考訳（メタデータ） (2021-11-09T00:20:01Z) - Random matrices in service of ML footprint: ternary random features with
no performance loss [55.30329197651178]
我々は、$bf K$ の固有スペクトルが$bf w$ の i.d. 成分の分布とは独立であることを示す。
3次ランダム特徴(TRF)と呼ばれる新しいランダム手法を提案する。
提案したランダムな特徴の計算には乗算が不要であり、古典的なランダムな特徴に比べてストレージに$b$のコストがかかる。
論文 参考訳（メタデータ） (2021-10-05T09:33:49Z) - 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) - $k$-Forrelation Optimally Separates Quantum and Classical Query
Complexity [3.4984289152418753]
我々は、$N$ビット上の任意の部分関数は、$q$量子クエリを作れば、ランダムな推測よりも$delta$で計算できることを示した。
我々はまた、$k$-Forrelation問題 -- $q = lceil k/2 rceil$量子クエリで計算できる部分関数 -- を予想した。
論文 参考訳（メタデータ） (2020-08-16T21:26:46Z) - On the robustness of the minimum $\ell_2$ interpolator [2.918940961856197]
一般高次元線形回帰フレームワークにおいて最小$ell$-norm$hatbeta$で補間を解析する。
高い確率で、この推定器の予測損失は、上から$(|beta*|2r_cn(Sigma)vee |xi|2)/n$で有界であることを証明する。
論文 参考訳（メタデータ） (2020-03-12T15:12:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。