論文の概要: Quantum Query Complexity of Persistence Statistics in Graph Zigzags

• arxiv url: http://arxiv.org/abs/2609.05813v1
• Date: Sat, 05 Sep 2026 02:16:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-12 12:38:02.250146
• Title: Quantum Query Complexity of Persistence Statistics in Graph Zigzags
• Title（参考訳）: グラフジグザグにおける永続統計量の量子クエリ複雑性
• Abstract要約: 本研究では、スナップショット・アジャシエンスビットからジグザグバー寿命のスカラーサマリーを推定するクエリ複雑性について検討した。 ランクがグラフの回路ランクであるグラフの場合、非線形バーコード関数はエッジと成分数の平均となる。 すべての固定パワーウェイトに対して$xr$,$rge2$、均一ウィンドウ平均では、最悪のケースの複雑さは$widetilde(nsqrt m/varepsilon)$ Quantumと$(n2m)$ classicalである。
• 参考スコア（独自算出の注目度）: 2.895030292351388
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the query complexity of estimating scalar summaries of zigzag bar lifetimes from snapshot-adjacency bits. For graphs $G_1,\ldots,G_m$ on $n$ labeled vertices, let $\ell_b$ be the snapshot lifetime of a degree-one bar $b$ of the intersection zigzag. For a probability generating function $φ(x)=\mathbb{E}[x^R]$, the statistic $F_φ=\sum_bφ(\ell_b/m)$ includes normalized degree-$r$ total persistence and the mean generalized rank over a uniform time window. An exact identity underlies our algorithm: sample $R$ uniform times; the expected generalized rank between their minimum and maximum equals $F_φ$. For graphs that rank is the circuit rank of an intersection graph, so a nonlinear barcode functional becomes an average of edge and component counts, and no barcode is computed. Without spectral-gap, homology-state, or QRAM assumptions, this gives a quantum estimator with additive error $\varepsilon n$ and $\widetilde O(\sqrt{m(K+n)}/\varepsilon)$ queries when a bound $K\ge F_φ$ is supplied, against $\widetilde O(m\min\{n^2,(K+n)/\varepsilon^2\})$ classically, and an adaptive quantum variant with the same instance dependence. These estimators are optimal in two regimes. For every fixed power weight $x^r$, $r\ge2$, and for the uniform-window mean, the worst-case complexities are $\widetildeΘ(n\sqrt m/\varepsilon)$ quantum and $Θ(n^2m)$ classical. On sparse instances, under an explicit split-leakage promise met by power and binomial weights of logarithmic degree and the promise $F_φ\le K$, they are $\widetildeΘ(\sqrt{mK}/\varepsilon)$ and $\widetildeΘ(m\min\{n^2,K/\varepsilon^2\})$. The classical lower bounds hold against fully adaptive algorithms, and fewer than $m$ such statistics cannot determine the positive-lifetime histogram. All bounds concern snapshot access; with an explicit update stream, near-linear full-barcode algorithms are known.
• Abstract（参考訳）: 本研究では、スナップショット・アジャシエンスビットからジグザグバー寿命のスカラーサマリーを推定するクエリ複雑性について検討する。 グラフ $G_1,\ldots,G_m$ on $n$ labeled vertices の場合、$\ell_b$ は交点 zigzag の次数 1 バー $b$ のスナップショット寿命とする。 確率生成関数 $φ(x)=\mathbb{E}[x^R]$ に対して、統計学 $F_φ=\sum_bφ(\ell_b/m)$ は正規化次数-$r$全持続と一様時間窓上の平均一般化階数を含む。 サンプル$R$均一時間; 期待される最小値と最大値の間の一般化ランクは$F_φ$である。 交叉グラフの回路ランクであるグラフの場合、非線形バーコード関数はエッジとコンポーネント数の平均となり、バーコードは計算されない。 スペクトルギャップ、ホモロジー状態、あるいはQRAMの仮定がなければ、加法誤差$\varepsilon n$と$\widetilde O(\sqrt{m(K+n)}/\varepsilon)$クエリは、有界な$K\ge F_φ$が供給されるとき、$\widetilde O(m\min\{n^2,(K+n)/\varepsilon^2\})$古典的には、同じインスタンスに依存する適応量子変量である。 これらの推定器は2つの状態において最適である。 すべての固定パワーウェイトに対して、$x^r$, $r\ge2$ と、一様風下平均に対して、最悪の場合の複素数は$\widetilde\(n\sqrt m/\varepsilon)$ 量子と$(n^2m)$古典的である。 スパースの場合、対数次数と約$F_φ\le K$の力と二項重みで表される明示的な分割推論の約束の下で、それらは$\widetilde'(\sqrt{mK}/\varepsilon)$と$\widetilde'(m\min\{n^2,K/\varepsilon^2\})$である。 古典的な下界は完全適応アルゴリズムに対して成り立ち、そのような統計値が$m$未満では正寿命ヒストグラムを決定できない。 明示的な更新ストリームでは、ほぼ線形のフルバーコードアルゴリズムが知られている。

関連論文リスト

• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。 フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
  論文  参考訳（メタデータ） (2026-07-08T17:49:40Z)
• On the complexity of quantum numerical integration: an angle-structure characterization [1.376408511310322]
  量子振幅推定(QAE)による$[0,1]$の数値積分について検討し,振幅オラクルの構築コストに着目した。 格子関数クラス $mathcalG_n(d)$ の階層を導入し、角写像 $_g:0,1nto[0,]$ を最大$d$ の次数として定義する。 $d=1$の場合、これは$O(varepsilon-1log(1/varepsilon))$となり、古典的なモンテカルロを$geで改善する。
  論文  参考訳（メタデータ） (2026-04-27T10:23:24Z)
• Optimal Scalar Quantization for Matrix Multiplication: Closed-Form Density and Phase Transition [50.36362492608702]
  乗算前の2つの行列のエントリーワイズスカラー量子化について検討した。 我々は、閉形式の最適点密度 [ star(u) propto exp!left(-fracu26right)bigl( (1-2)+2u22bigr), qquad u=fracx_X を求め、相関駆動相転移を証明した。
  論文  参考訳（メタデータ） (2026-03-20T01:53:44Z)
• Sublinear Time Quantum Sensitivity Sampling [57.356528942341534]
  本稿では、量子感応サンプリングのための統一的なフレームワークを提案し、量子コンピューティングの利点を古典近似問題の幅広いクラスに拡張する。 我々のフレームワークは、コアセットを構築するための合理化されたアプローチを提供し、クラスタリング、回帰、低ランク近似などのアプリケーションにおいて、大幅なランタイム改善を提供します。
  論文  参考訳（メタデータ） (2025-09-20T20:18:49Z)
• Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
  本研究では、量子ビットの対数数を用いて、加算誤差$epsilonDelta_k$まで値を近似する量子アルゴリズムを提案する。 この分析における重要な技術的ステップは、適切なランダム初期状態の準備であり、最終的には閾値よりも小さい固有値の数を効率的に数えることができる。
  論文  参考訳（メタデータ） (2025-08-28T17:04:18Z)
• Improved convergence rate of kNN graph Laplacians [11.93971616098517]
  k$NNグラフの一般クラスで、グラフ親和性は$W_ij = epsilon-d/2 である。 制限多様体作用素に対する$k$NNグラフ Laplacian の点収束性を証明する。
  論文  参考訳（メタデータ） (2024-10-30T17:01:00Z)
• Solving Dense Linear Systems Faster Than via Preconditioning [1.8854491183340518]
  我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$であることを示す。 特に、我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$である。 主アルゴリズムはランダム化ブロック座標降下法とみなすことができる。
  論文  参考訳（メタデータ） (2023-12-14T12:53:34Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• Do you know what q-means? [42.96240569413475]
  古典的な$varepsilon$-$k$-meansアルゴリズムは、ロイドのアルゴリズムの1つの反復の近似バージョンを時間的複雑さで実行する。 また,時間的複雑さを考慮した$q$-means量子アルゴリズムも提案する。
  論文  参考訳（メタデータ） (2023-08-18T17:52:12Z)
• A Quantum Approximation Scheme for k-Means [0.16317061277457]
  QRAMモデルにおける古典的な$k$-meansクラスタリング問題に対する量子近似スキームを提案する。 我々の量子アルゴリズムは、時間$tildeO left(2tildeO(frackvarepsilon) eta2 dright)$で実行される。 教師なし学習の以前の研究とは異なり、我々の量子アルゴリズムは量子線型代数のサブルーチンを必要としない。
  論文  参考訳（メタデータ） (2023-08-16T06:46:37Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  制約付き非線形最適化問題のオンライン統計的推測を考察する。 これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
  論文  参考訳（メタデータ） (2022-05-27T00:34:03Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。 実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
  論文  参考訳（メタデータ） (2021-10-21T18:43:00Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。