Fugu-MT 論文翻訳(概要): A Note on the Complexity of the Spectral Gap Problem

論文の概要: A Note on the Complexity of the Spectral Gap Problem

arxiv url: http://arxiv.org/abs/2503.02747v1
Date: Tue, 04 Mar 2025 16:13:30 GMT
ステータス: 翻訳完了
システム内更新日: 2025-03-05 19:14:37.724302
Title: A Note on the Complexity of the Spectral Gap Problem
Title（参考訳）: スペクトルギャップ問題の複雑性に関する一考察
Authors: Justin Yirka,
Abstract要約: 局所ハミルトニアンのスペクトルギャップを推定する問題は、クラス$PQMA[log]$:QMAクエリの対数的な数にアクセスする時間に含まれていることが知られている。スペクトルギャップ問題は、多対一(Karp)還元の下でQMAハードであることの簡単な証明を与える。スペクトルギャップ問題(Spectral Gap problem)の複雑さは、多くの還元の下で特徴づけられる。
参考スコア（独自算出の注目度）: 0.0
License:
Abstract: The problem of estimating the spectral gap of a local Hamiltonian is known to be contained in the class $P^{QMA[log]}$: polynomial time with access to a logarithmic number of QMA queries. The problem was shown to be hard for $P^{UQMA[log]}$, a weaker class, under Turing reductions by Gharibian and Yirka [arXiv:1606.05626]. I give a brief proof that the Spectral Gap problem is QMA-hard under a many-one (Karp) reduction. Consequently, the problem is $P^{QMA[log]}$-complete under truth-table reductions. It remains open to characterize the complexity of the Spectral Gap problem under many-one reductions. I conjecture that the problem belongs to a strict subclass of $P^{QMA[log]}$.
Abstract（参考訳）: 局所ハミルトニアンのスペクトルギャップを推定する問題は、クラス$P^{QMA[log]}$: QMAクエリの対数的数にアクセスする多項式時間に含まれることが知られている。この問題は、ガリビアンとヤルカによるチューリング還元(arXiv:1606.05626)の下で、より弱いクラスである$P^{UQMA[log]}$に対して難しいことが示されている。スペクトルギャップ問題は、多対一(Karp)還元の下でQMAハードであることの簡単な証明を与える。したがって、真理値の削減の下では、問題は$P^{QMA[log]}$-completeである。スペクトルギャップ問題(Spectral Gap problem)の複雑さは、多くの還元の下で特徴づけられる。私は、この問題は$P^{QMA[log]}$の厳密な部分クラスに属すると推測する。

関連論文リスト

Optimal level set estimation for non-parametric tournament and crowdsourcing problems [49.75262185577198]
クラウドソーシングによって動機づけられた我々は、$d$の質問に対する$n$の専門家の回答の正しさを部分的に観察する問題を考える。本稿では、専門家$i$が疑問に答える確率を含む行列$M$が、行と列の置換までの双等方性であることを仮定する。我々は,この分類問題に対して最小限のアルゴリズムを最適に構築する。
論文参考訳（メタデータ） (2024-08-27T18:28:31Z)
Matching the Statistical Query Lower Bound for $k$-Sparse Parity Problems with Sign Stochastic Gradient Descent [83.85536329832722]
我々は、2層完全連結ニューラルネットワーク上での符号勾配降下(SGD)による$k$スパースパリティ問題を解く。このアプローチは、$d$次元ハイパーキューブ上での$k$スパースパリティ問題を効率的に解くことができることを示す。次に、符号SGDを持つトレーニングニューラルネットワークが、この優れたネットワークを効果的に近似し、小さな統計的誤差で$k$-parity問題を解く方法を示す。
論文参考訳（メタデータ） (2024-04-18T17:57:53Z)
The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。 QMA(2) が $textQMA+(2)$ に等しいことを示す。
論文参考訳（メタデータ） (2024-02-29T01:35:46Z)
Gapped Clique Homology on weighted graphs is $\text{QMA}_1$-hard and contained in $\text{QMA}$ [0.0]
計算トポロジにおける古典問題の複雑性, ホモロジー問題について検討する。複雑性は量子複雑性クラスによって特徴づけられる。我々の結果は、ホモロジーと超対称量子力学の結びつきの側面と見なすことができる。
論文参考訳（メタデータ） (2023-11-28T21:15:30Z)
Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
論文参考訳（メタデータ） (2023-02-13T22:51:07Z)
Complexity of Supersymmetric Systems and the Cohomology Problem [0.0]
我々は、$mathcal N=2 $ 超対称性を持つフェルミオンハミルトニアンの文脈における局所ハミルトニアン問題の複雑さを考える。これを研究する主な動機は、超対称系の基底状態エネルギーがちょうどゼロであることと、あるコホモロジー群が非自明であることである。
論文参考訳（メタデータ） (2021-06-30T18:00:01Z)
Quantum Logarithmic Space and Post-selection [0.4588028371034406]
ポストセレクション(Post-Selection)は、アーロンソンによって量子複雑性理論の分野に導入された影響力ある概念である(Royal Society A, 2005 の論文)。我々の主な結果は、$sf PostBQL=$、すなわち、選択後(sf PostBQL$)で境界付きエラー(polynomial-time)対数空間量子アルゴリズムによって解決できる問題のクラスを示す。また、$sf$は時間制限のない有界誤差対数空間量子アルゴリズムによって解くことができる問題のクラスと一致することを示す。
論文参考訳（メタデータ） (2021-05-06T14:02:01Z)
Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
論文参考訳（メタデータ） (2020-12-17T16:43:11Z)
Short proof of a spectral Chernoff bound for local Hamiltonians [0.0]
ワイルの不等式に基づいて、$k$局所ハミルトニアンのスペクトルに対するチャーノフ境界の簡単な証明を与える。例えば、$epsilon(n)=d-n$ の場合、問題はNPハードであり、QMAハードであるとしても、$a>1$ が存在して、$epsilon(n)=a-n$ は自明である。
論文参考訳（メタデータ） (2020-09-10T17:05:18Z)
Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks [48.32532049640782]
ガウス境界の下で, 1層ReLUネットワークを$k$の隠れ単位で学習する問題をmathbbRd$で研究する。正の係数の場合、この学習問題の初回アルゴリズムを$k$から$tildeOOmega(sqrtlog d)$まで与える。
論文参考訳（メタデータ） (2020-06-22T17:53:54Z)
Can graph properties have exponential quantum speedup? [5.101801159418223]
特に、(部分)グラフの性質に対して指数的スピードアップが可能かどうかを問うのは自然である。この疑問に対する答えは入力モデルに強く依存していることを示す。
論文参考訳（メタデータ） (2020-01-28T18:45:48Z)

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