論文の概要: Complexity of Normalized Persistence Problems for Topological Data Analysis and Local Hamiltonians
- arxiv url: http://arxiv.org/abs/2607.03278v1
- Date: Fri, 03 Jul 2026 12:46:53 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-07 22:26:29.569207
- Title: Complexity of Normalized Persistence Problems for Topological Data Analysis and Local Hamiltonians
- Title（参考訳）: トポロジカルデータ解析における正規化パーシステンス問題の複雑さと局所ハミルトニアン
- Abstract要約: トポロジデータ分析(TDA)は、トポロジを用いてデータからパターンを抽出する機械学習技術である。
異なる長さスケールで持続する穴の数を数える正規化永続化の問題を考察する。
局所ハミルトニアンの低エネルギー部分空間において、正規化持続性とスペクトル量の推定の複雑さの密接な関係を見出した。
- 参考スコア（独自算出の注目度）: 3.2782119351918606
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Topological data analysis (TDA) is a machine learning technique that uses topology to extract patterns from data and has shown the potential to exhibit quantum advantage. A key concept in TDA is persistent homology, which measures the robustness of topological information at different lengthscales. In this paper, we introduce and study the problem of normalized persistence, a practically motivated and easily interpretable version of persistent homology that counts the fraction of holes that persist at different lengthscales. We prove that a variant of normalized persistence is $\mathsf{DQC}_1$-hard and contained in $\mathsf{BQP}$, giving evidence of an exponential quantum speedup for TDA under the standard assumption that $\mathsf{DQC}_1 \not\subseteq \mathsf{BPP}$. These are the first $\mathsf{DQC}_1$-hardness results that are directly applicable to TDA instances. We also find a close connection between normalized persistence and the complexity of estimating spectral quantities in the low-energy subspace of local Hamiltonians. We study a family of such problems, including a low-energy normalized subtrace and spectral density. We show that these are $\mathsf{DQC}_1$-hard for $O(1)$-local Hamiltonians, strengthening previous results that required log-local interactions. We also introduce a variant of $\mathsf{DQC}_1$ with perfect completeness ($\mathsf{SDQC}_1$) to characterize the hardness of problems normalized by an exact kernel. This includes normalized persistence for $O(1)$-local Hamiltonians, which we show is $\mathsf{SDQC}_1$-hard.
- Abstract（参考訳）: トポロジカルデータ分析(TDA)は、トポロジを用いてデータからパターンを抽出する機械学習技術であり、量子優位性を示す可能性を示している。
TDAにおける鍵となる概念は、異なる長さスケールで位相情報の堅牢性を測定する永続ホモロジーである。
本稿では, 異なる長さスケールで持続する穴の数を数える, 事実上動機付けられた, 容易に解釈可能な永続ホモロジーである正規化永続問題を紹介し, 研究する。
正規化永続化の変種が$\mathsf{DQC}_1$-hardで、$\mathsf{BQP}$に含まれ、標準仮定の下でTDAの指数的量子スピードアップの証拠を、$\mathsf{DQC}_1 \not\subseteq \mathsf{BPP}$に与える。
これらは、TDAインスタンスに直接適用可能な最初の$\mathsf{DQC}_1$-hardnessの結果である。
また、正規化パーシステンスと局所ハミルトンの低エネルギー部分空間におけるスペクトル量の推定の複雑さの密接な関係も見いだす。
低エネルギーの正規化部分トレースとスペクトル密度を含む,そのような問題の族について検討する。
我々は、これらが$O(1)$-ローカルハミルトニアンに対して$\mathsf{DQC}_1$-hardであることを示し、対数局所相互作用を必要とする以前の結果を強化する。
また、完全性を持つ$\mathsf{DQC}_1$の変種($\mathsf{SDQC}_1$)を導入して、正確なカーネルによって正規化される問題の硬さを特徴付ける。
これは、$O(1)$-local Hamiltonians に対する正規化された永続化を含み、ここでは $\mathsf{SDQC}_1$-hard を示す。
関連論文リスト
- Information Hierarchy in Many-Body Berry Phase [0.0]
多体トポロジーは、現代固体理論における中心的な概念である。
この研究は、相互作用する多体基底状態の幾何学的情報が、有限個の局所相関から推測できる範囲について研究する。
論文 参考訳（メタデータ） (2026-06-01T12:20:41Z) - DQC1-completeness of normalized trace estimation for functions of log-local Hamiltonians [20.990700912031773]
正規化トレース 2-nTr[f(A)]$ を対数局所ハミルトニアン$A$ で$n$ qubits に作用させることの計算複雑性について検討する。
この問題は自然に DQC1 モデルで生じるが、その複雑性は限定された函数のクラス$f(x)$に対してのみ理解される。
f(x)$ が近似次数 $(rm poly(n))$ の連続関数であれば、2-nTr[f(A)]$ を定数加法誤差まで見積もる。
論文 参考訳（メタデータ） (2026-04-02T01:15:12Z) - Hardness of High-Dimensional Linear Classification [58.29089693778071]
我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。
どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
論文 参考訳（メタデータ） (2026-03-19T15:53:41Z) - Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-to-Hamiltonian Constructions [1.43494686131174]
1-varepsilon)n)$ for any $varepsilon>0$ for any $varepsilon>0$ under the Strong Exponential-Time hypothesis (SETH)。
我々は、任意の1/mathrmpoly(n)$相対誤差に対して$O(sqrt2n)$ timeで実行し、下位境界にマッチし、Bravyi、Chowdhury、Gossによる最先端アルゴリズムを改善する量子アルゴリズムを提供する。
論文 参考訳（メタデータ） (2026-02-16T01:11:55Z) - Slow Mixing of Quantum Gibbs Samplers [47.373245682678515]
一般化されたボトルネック補題を用いて、これらのツールの量子一般化を示す。
この補題は、古典的なハミング距離に類似する距離の量子測度に焦点を当てるが、一意に量子原理に根ざしている。
ポアソン・ファインマン・カック法を用いて古典的な緩やかな混合結果を持ち上げる方法を示す。
論文 参考訳（メタデータ） (2024-11-06T22:51:27Z) - Quantum computing and persistence in topological data analysis [41.16650228588075]
トポロジカルデータ解析(TDA)は、そのトポロジにおけるホールの数と持続性を調べることによって、データセットからノイズ・ロバストの特徴を抽出することを目的としている。
TDAのコアタスクと密接に関連する計算問題は$mathsfBQP_1$-hardであり、$mathsfBQP$に含まれることを示す。
我々のアプローチは、誘導されたスパースハミルトニアン問題(英語版)の変種における穴の永続化を符号化することに依存している。
論文 参考訳（メタデータ） (2024-10-28T17:54:43Z) - On stability of k-local quantum phases of matter [0.4999814847776097]
一般量子低密度パリティチェック符号に対応するハミルトンのユークリッドに対するエネルギーギャップの安定性を解析する。
局所ハミルトニアンは広い零温度エントロピーを持つことができるので、熱力学の第3法則の意味を論じる。
論文 参考訳（メタデータ） (2024-05-29T18:00:20Z) - Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。
本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
論文 参考訳（メタデータ） (2024-04-29T15:04:07Z) - 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) - Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。
低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
論文 参考訳（メタデータ） (2023-02-13T22:51:07Z) - Hamiltonian simulation with random inputs [74.82351543483588]
ランダム初期状態を持つハミルトンシミュレーションの平均ケース性能の理論
数値的な証拠は、この理論がコンクリート模型の平均誤差を正確に特徴づけていることを示唆している。
論文 参考訳（メタデータ） (2021-11-08T19:08:42Z) - Complexity of Supersymmetric Systems and the Cohomology Problem [0.0]
我々は、$mathcal N=2 $ 超対称性を持つフェルミオンハミルトニアンの文脈における局所ハミルトニアン問題の複雑さを考える。
これを研究する主な動機は、超対称系の基底状態エネルギーがちょうどゼロであることと、あるコホモロジー群が非自明であることである。
論文 参考訳（メタデータ） (2021-06-30T18:00:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。