Fugu-MT 論文翻訳(概要): Fermionic Independent Set and Laplacian of an independence complex are QMA-hard

論文の概要: Fermionic Independent Set and Laplacian of an independence complex are QMA-hard

arxiv url: http://arxiv.org/abs/2411.03230v1
Date: Tue, 05 Nov 2024 16:21:48 GMT
ステータス: 翻訳完了
システム内更新日: 2024-11-06 14:58:41.497060
Title: Fermionic Independent Set and Laplacian of an independence complex are QMA-hard
Title（参考訳）: 独立錯体のフェルミオン独立集合とラプラシアンはQMAハードである
Authors: Chaithanya Rayudu,
Abstract要約: 摂動ガジェットを用いた$k$-粒子部分空間における最適化問題はQMAハードであることが証明された。自然位相データ解析問題 QMA-hard の最初の例を示す。
参考スコア（独自算出の注目度）: 0.0
License:
Abstract: The Independent Set is a well known NP-hard optimization problem. In this work, we define a fermionic generalization of the Independent Set problem and prove that the optimization problem is QMA-hard in a $k$-particle subspace using perturbative gadgets. We discuss how the Fermionic Independent Set is related to the problem of computing the minimum eigenvalue of the $k^{\text{th}}$-Laplacian of an independence complex of a vertex weighted graph. Consequently, we use the same perturbative gadget to prove QMA-hardness of the later problem resolving an open conjecture from arXiv:2311.17234 and give the first example of a natural topological data analysis problem that is QMA-hard.
Abstract（参考訳）: 独立集合はよく知られたNPハード最適化問題である。本研究では、独立集合問題のフェルミオン一般化を定義し、最適化問題は摂動ガジェットを用いた$k$-粒子部分空間においてQMAハードであることを証明する。我々は、フェルミオン独立集合が、頂点重み付きグラフの独立複素数の$k^{\text{th}}$-Laplacianの最小固有値を計算する問題とどのように関係しているかについて議論する。その結果、同じ摂動ガジェットを用いて、arXiv:2311.17234からの開予想を解く後の問題のQMA硬さを証明し、QMA硬である自然位相データ解析問題の最初の例を示す。

関連論文リスト

Curvature-Independent Last-Iterate Convergence for Games on Riemannian Manifolds [77.4346324549323]
本研究では, 多様体の曲率に依存しないステップサイズが, 曲率非依存かつ直線的最終点収束率を達成することを示す。我々の知る限りでは、曲率非依存率や/または最終点収束の可能性はこれまでに検討されていない。
論文参考訳（メタデータ） (2023-06-29T01:20:44Z)
Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
論文参考訳（メタデータ） (2023-06-21T17:03:22Z)
Approximation of optimization problems with constraints through kernel Sum-Of-Squares [77.27820145069515]
我々は、点的不等式が非負の kSoS 関数のクラス内で等式となることを示す。また, 等式制約に焦点をあてることで, 散乱不等式を用いることで, 制約のサンプリングにおける次元性の呪いを軽減することができることを示す。
論文参考訳（メタデータ） (2023-01-16T10:30:04Z)
A Riemannian ADMM [7.128839268767137]
問題のクラスは、機械学習と統計学において重要な応用を見出す。本稿では,各方向のスパース計算可能ステップの反復法を提案する。
論文参考訳（メタデータ） (2022-11-03T22:12:18Z)
Clique Homology is QMA1-hard [0.0]
simplicial complex のホモロジー群を決定する決定問題は QMA1-hard である。これは、古典的と思われる問題は、実際には量子力学である可能性を示唆している。本稿では、トポロジカルデータ解析における量子優位性の問題への潜在的な影響について論じる。
論文参考訳（メタデータ） (2022-09-23T18:14:16Z)
Isogeometric Analysis of Bound States of a Quantum Three-Body Problem in 1D [0.0]
B-スプライン基底関数の線形結合により波動関数を表現し,行列固有値問題として解く。固有値は固有状態エネルギーを与えるが、固有ベクトルは固有状態に導くB-スプラインの係数を与える。我々は、IGAが3体問題を解くための有望な技術を提供する、様々な数値実験を通して実証する。
論文参考訳（メタデータ） (2022-02-21T04:27:31Z)
Partial Counterfactual Identification from Observational and Experimental Data [83.798237968683]
観測データと実験データの任意の組み合わせから最適境界を近似する有効なモンテカルロアルゴリズムを開発した。我々のアルゴリズムは、合成および実世界のデータセットに基づいて広範囲に検証されている。
論文参考訳（メタデータ） (2021-10-12T02:21:30Z)
Minimax Estimation of Linear Functions of Eigenvectors in the Face of Small Eigen-Gaps [95.62172085878132]
固有ベクトル摂動解析は様々な統計データ科学の応用において重要な役割を果たす。未知の固有ベクトルの任意の線型関数の摂動を特徴付ける統計理論の一組を開発する。自然の「プラグイン」推定器に固有の非無視バイアス問題を緩和するために,非バイアス推定器を開発する。
論文参考訳（メタデータ） (2021-04-07T17:55:10Z)
On the Convexity of Discrete Time Covariance Steering in Stochastic Linear Systems with Wasserstein Terminal Cost [1.1602089225841632]
端末状態の共分散が上界であるとき、L"所有者部分順序に関して、この問題は一意に大域的最小化状態フィードバックゲインを許容することを示す。本研究の結果は, 特殊制御設計ツールの開発に向けての段階を定めている。
論文参考訳（メタデータ） (2021-03-25T03:24:52Z)
Stochastic Approximation for Online Tensorial Independent Component Analysis [98.34292831923335]
独立成分分析(ICA)は統計機械学習や信号処理において一般的な次元削減ツールである。本稿では,各独立成分を推定する副産物オンライン時系列アルゴリズムを提案する。
論文参考訳（メタデータ） (2020-12-28T18:52:37Z)
On the Sample Complexity and Optimization Landscape for Quadratic Feasibility Problems [7.722592882475735]
複素ベクトル $mathbfxin mathbbCn$ を $mangle A-imathbfx, mathbfxr_i=1m から復元する問題を考える。一般に、NP-ハードが解ける二次問題であるだけでなく、実際には特定できないかもしれない。
論文参考訳（メタデータ） (2020-02-04T00:35:09Z)

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