論文の概要: StoqMA meets distribution testing
- arxiv url: http://arxiv.org/abs/2011.05733v3
- Date: Tue, 22 Jun 2021 07:58:46 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-24 11:53:05.929159
- Title: StoqMA meets distribution testing
- Title（参考訳）: StoqMAが配布テストに合格
- Authors: Yupan Liu
- Abstract要約: We provide a novel connection between $mathsfStoqMA$ and distribution testing via reversible circuits。
いずれの変種も$mathsfStoqMA$は、任意の無作為な乱数ビットと完全音性を持たず、$mathsfNP$に含まれることを示す。
我々の結果は、$mathsfMA subseteq mathsfStoqMA subseteq mathsfSBP$ [BBT06]という階層構造を崩壊させる一歩を踏み出した。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: $\mathsf{StoqMA}$ captures the computational hardness of approximating the
ground energy of local Hamiltonians that do not suffer the so-called sign
problem. We provide a novel connection between $\mathsf{StoqMA}$ and
distribution testing via reversible circuits. First, we prove that easy-witness
$\mathsf{StoqMA}$ (viz. $\mathsf{eStoqMA}$, a sub-class of $\mathsf{StoqMA}$)
is contained in $\mathsf{MA}$. Easy witness is a generalization of a subset
state such that the associated set's membership can be efficiently verifiable,
and all non-zero coordinates are not necessarily uniform. This sub-class
$\mathsf{eStoqMA}$ contains $\mathsf{StoqMA}$ with perfect completeness
($\mathsf{StoqMA}_1$), which further signifies a simplified proof for
$\mathsf{StoqMA}_1 \subseteq \mathsf{MA}$ [BBT06, BT10]. Second, by showing
distinguishing reversible circuits with ancillary random bits is
$\mathsf{StoqMA}$-complete (as a comparison, distinguishing quantum circuits is
$\mathsf{QMA}$-complete [JWB05]), we construct soundness error reduction of
$\mathsf{StoqMA}$. Additionally, we show that both variants of
$\mathsf{StoqMA}$ that without any ancillary random bit and with perfect
soundness are contained in $\mathsf{NP}$. Our results make a step towards
collapsing the hierarchy $\mathsf{MA} \subseteq \mathsf{StoqMA} \subseteq
\mathsf{SBP}$ [BBT06], in which all classes are contained in $\mathsf{AM}$ and
collapse to $\mathsf{NP}$ under derandomization assumptions.
- Abstract（参考訳）: $\mathsf{StoqMA}$は、いわゆる符号問題に悩まされない地元のハミルトンの基底エネルギーを近似する計算困難さを捉える。
我々は$\mathsf{StoqMA}$と可逆回路による分散テストの間の新しい接続を提供する。
まず、簡単なウィットネス$\mathsf{StoqMA}$ (viz) を証明する。
$\mathsf{eStoqMA}$, $\mathsf{StoqMA}$)のサブクラスは$\mathsf{MA}$に含まれる。
簡単な証人は集合のメンバシップが効率的に検証でき、すべての非零座標が必ずしも一様ではないような部分集合状態の一般化である。
このサブクラス$\mathsf{estoqma}$ は完全完全性を持つ$\mathsf{stoqma}$ (\mathsf{stoqma}_1$) を含み、さらに$\mathsf{stoqma}_1 \subseteq \mathsf{ma}$ [bbt06, bt10] の簡単な証明を示す。
第二に、乱数ビットによる可逆回路の区別を$\mathsf{StoqMA}$-complete(比較として、量子回路の区別は$\mathsf{QMA}$-complete [JWB05])とすることにより、$\mathsf{StoqMA}$の音質誤差低減を構築する。
さらに、$\mathsf{StoqMA}$ のどちらの変種も、任意の非同期乱数ビットと完全音性を持たずに$\mathsf{NP}$ に含まれることを示す。
我々の結果は、階層 $\mathsf{MA} \subseteq \mathsf{StoqMA} \subseteq \mathsf{SBP}$ [BBT06] を崩壊させ、すべてのクラスが$\mathsf{AM}$に含まれ、デランドマイズ仮定の下で$\mathsf{NP}$に崩壊する。
関連論文リスト
- On the Complexity of Pure-State Consistency of Local Density Matrices [0.0]
局所密度行列(mathsfPureCLDM$)および純$N$-representability(mathsfPure$-$N$-$mathsfRepresentability$)問題の純粋整合性について検討する。
この新しいクラスには$mathsfPure$-$N$-$mathsfRepresentability$と$mathsfPureCLDM$の両方が完了していることを証明します。
論文 参考訳（メタデータ） (2024-11-05T13:43:21Z) - The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Quantum Sabotage Complexity [0.7812210699650152]
ここでは$mathsfQ(f_mathsfsab)$を示し、$f_mathsfsab$の量子クエリ複雑性を示す。
f$がインデックス関数であるとき、$mathsfQ(f_mathsfsab)=Theta(sqrtmathsfsab)$は、$mathsfQ(f_mathsfsab)=Theta(sqrtmathsf)の可能性を除外する。
論文 参考訳（メタデータ） (2024-08-22T17:57:58Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - Quantum Oblivious LWE Sampling and Insecurity of Standard Model Lattice-Based SNARKs [4.130591018565202]
Learning Errors With Errors(mathsfLWE$)問題は$(mathbfAmathbfs+mathbfe$)という形式の入力から$mathbfs$を見つけるように要求する
私たちは$mathsfLWE$の解決ではなく、インスタンスをサンプリングするタスクに注力しています。
我々の主な成果は、よく分散された$mathsfLWE$インスタンスをサンプリングする量子時間アルゴリズムである。
論文 参考訳（メタデータ） (2024-01-08T10:55:41Z) - SQ Lower Bounds for Learning Mixtures of Linear Classifiers [43.63696593768504]
この問題に対する既知のアルゴリズムは、一様混合の特別な場合であっても、本質的には最善であることを示す。
重要な技術的要素は、独立した関心を持つかもしれない球面設計の新たな構築である。
論文 参考訳（メタデータ） (2023-10-18T10:56:57Z) - 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) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - The planted matching problem: Sharp threshold and infinite-order phase
transition [25.41713098167692]
ランダムに重み付けされた$ntimes n$ bipartite graphに隠された完全マッチング$M*$を再構築する問題について検討する。
任意の小さな定数 $epsilon>0$ に対して $sqrtd B(mathcalP,mathcalQ) ge 1+epsilon$ が成り立つ場合、任意の推定値の再構築誤差は $0$ から有界であることが示される。
論文 参考訳（メタデータ） (2021-03-17T00:59:33Z) - Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and
ReLUs under Gaussian Marginals [49.60752558064027]
ガウス境界の下では、半空間とReLUを不可知的に学習する基本的な問題について検討する。
我々の下限は、これらのタスクの現在の上限が本質的に最良のものであるという強い証拠を与える。
論文 参考訳（メタデータ） (2020-06-29T17:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。