論文の概要: Average-case hardness of Betti number estimation
- arxiv url: http://arxiv.org/abs/2609.12777v1
- Date: Fri, 11 Sep 2026 12:30:30 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-15 07:38:31.741648
- Title: Average-case hardness of Betti number estimation
- Title（参考訳）: ベティ数推定における平均ケース硬度
- Abstract要約: 本研究では, ランダムクリッド錯体上でのベッチ数推定の平均硬度を, 植込みクリッド問題からの還元により確立する。
我々は,古典的および量子的トポロジカルデータ解析における多くの問題に対して,この削減は一連の硬度結果を意味することを示す。
- 参考スコア（独自算出の注目度）: 1.6312989763677892
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: We establish the average-case hardness of Betti number estimation on random clique complexes via a reduction from the planted clique problem. We further show that our reduction implies a series of hardness results for many problems in both classical and quantum Topological Data Analysis (qTDA). Under the classical planted clique conjecture, no randomized polynomial-time Betti number estimator achieves additive error below $\tfrac12$ with constant advantage. Under a new quantum planted clique conjecture that we introduce, the same conclusion holds for quantum polynomial-time algorithms. We also obtain related conditional hardness results for homology vanishing, additive approximations with larger error tolerances, preparation of simplex and harmonic states, cycle recovery, and counting eigenvalues at low energy. Our reduction clarifies the structural requirements for quantum advantage in TDA and provides a new lens to investigate the classical and quantum complexity of related problems.
- Abstract（参考訳）: 本研究では, ランダムクリッド錯体上でのベッチ数推定の平均硬度を, 植込みクリッド問題からの還元により確立する。
さらに,古典的および量子的トポロジカルデータ解析(qTDA)における多くの問題に対して,この削減は一連の硬度結果を意味することを示す。
古典的プランテッド・クリッド予想の下では、ランダム化された多項式時間ベッチ数推定器は、一定の優位性を持って$\tfrac12$以下の加法誤差を達成できない。
私たちが導入した新しい量子プランテッド・クリッド予想の下では、量子多項式時間アルゴリズムについても同じ結論が成立する。
また, ホモロジーの消滅, より大きな誤差耐性を持つ加法近似, 単純および調和状態の生成, サイクル回復, 低エネルギーでの固有値の算定に関する条件付き硬度結果も得られた。
我々の削減は、TDAにおける量子優位性の構造的要件を明らかにし、関連する問題の古典的および量子的複雑さを調べるための新しいレンズを提供する。
関連論文リスト
- A rigorous quasipolynomial-time classical algorithm for SYK thermal expectations [51.660331450043806]
ギブス状態における局所観測可能量の推定は、量子シミュレーションにおける中心的な問題である。
我々は,SYK局所熱予測を十分高い温度で推定する準ポリノミカル時間古典アルゴリズムの証明を与える。
この結果は、量子多体システムに広く役立つと思われる新しいWick-pair展開をもたらす。
論文 参考訳（メタデータ） (2026-04-22T21:14:04Z) - Quartic quantum speedups for community detection [84.14713515477784]
我々は,準量子スピードアップを実現するハイパーグラフコミュニティ検出のための量子アルゴリズムを開発した。
提案アルゴリズムは,従来検討されていた PCA や $p$XORSAT といった問題を超えて拡張した Kikuchi 法に基づいている。
論文 参考訳（メタデータ） (2025-10-09T17:35:17Z) - New aspects of quantum topological data analysis: Betti number estimation, and testing and tracking of homology and cohomology classes [3.2268950104324965]
ホモロジー不変量,特にベッチ数と持続ベッチ数を推定するための新しい量子アルゴリズムを提案する。
提案手法は(永続的な)ラプラシアンを効率的にブロックエンコーディングし,指数階数法による推定を可能にする。
これらの結果は、量子トポロジカルデータ解析における新しい方向性を開き、計算トポロジカル不変量における証明可能な量子アドバンテージを示す。
論文 参考訳（メタデータ） (2025-06-02T08:43:58Z) - Reducing the sampling complexity of energy estimation in quantum many-body systems using empirical variance information [45.18582668677648]
パウリ分解において、与えられたハミルトニアンに対する量子状態準備のエネルギーを推定する問題を考える。
状態の実際の分散を用いた適応推定器を構築する。
論文 参考訳（メタデータ） (2025-02-03T19:00:01Z) - Lower bounds on the number of rounds of the quantum approximate optimization algorithm required for guaranteed approximation ratios [0.0]
本稿では、QAOAに必要なラウンド数(QAOAランタイムの主成分)について、最初の低い係数をいくつか提示する。
従来の横フィールドミキサーの場合、(iv)我々のフレームワークは、すべての有界共起局所コスト問題に自明な下限を与える。
厳密には$k$-local cost Hamiltonian matching known results that constant approximation ratio is obtained with a constant-round QAOA。
論文 参考訳（メタデータ） (2023-08-29T17:10:20Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳（メタデータ） (2022-09-28T17:53:25Z) - Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
我々は、トポロジカルデータ解析のための改良された量子アルゴリズムを解析し、最適化する。
超二次量子スピードアップは乗法誤差近似をターゲットとする場合にのみ可能であることを示す。
数百億のトフォリを持つ量子回路は、古典的に難解なインスタンスを解くことができると我々は主張する。
論文 参考訳（メタデータ） (2022-09-27T17:56:15Z) - Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
証明可能な性能保証を伴う忠実度推定のための新しい,効率的な量子アルゴリズムを開発した。
我々のアルゴリズムは量子特異値変換のような高度な量子線型代数技術を用いる。
任意の非自明な定数加算精度に対する忠実度推定は一般に困難であることを示す。
論文 参考訳（メタデータ） (2022-03-30T02:02:16Z) - Experimental violations of Leggett-Garg's inequalities on a quantum
computer [77.34726150561087]
単一および多ビット系におけるLeggett-Garg-Bellの不等式違反を実験的に観察する。
本分析では, 量子プラットフォームの限界に注目し, 上記の相関関数は, 量子ビットの数や回路深さが大きくなるにつれて, 理論的予測から逸脱することを示した。
論文 参考訳（メタデータ） (2021-09-06T14:35:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。