論文の概要: Quartic quantum speedups for community detection

• arxiv url: http://arxiv.org/abs/2510.08494v1
• Date: Thu, 09 Oct 2025 17:35:17 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-10 17:54:15.250456
• Title: Quartic quantum speedups for community detection
• Title（参考訳）: コミュニティ検出のための量子量子スピードアップ
• Authors: Alexander Schmidhuber, Alexander Zlokapa,
• Abstract要約: 我々は,準量子スピードアップを実現するハイパーグラフコミュニティ検出のための量子アルゴリズムを開発した。 提案アルゴリズムは,従来検討されていた PCA や $p$XORSAT といった問題を超えて拡張した Kikuchi 法に基づいている。
• 参考スコア（独自算出の注目度）: 84.14713515477784
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Community detection is a foundational problem in data science. Its natural extension to hypergraphs captures higher-order correlations beyond pairwise interactions. In this work, we develop a quantum algorithm for hypergraph community detection that achieves a quartic quantum speedup over the best known classical algorithm, along with superpolynomial savings in space. Our algorithm is based on the Kikuchi method, which we extend beyond previously considered problems such as Tensor PCA and $p$XORSAT to a broad family of generalized stochastic block models. To demonstrate (near) optimality of this method, we prove matching lower bounds (up to logarithmic factors) in the low-degree framework, showing that the algorithm saturates a smooth statistical-computational tradeoff. The quantum speedup arises from a quantized version of the Kikuchi method and is based on the efficient preparation of a guiding state correlated with the underlying community structure. Our work suggests that prior quantum speedups using the Kikuchi method are sufficiently robust to encompass a broader set of problems than previously believed; we conjecture that a quantity known as marginal order characterizes the existence of these quantum speedups.
• Abstract（参考訳）: コミュニティ検出は、データサイエンスにおける基礎的な問題である。 ハイパーグラフへの自然な拡張は、対の相互作用を超えた高次相関を捉える。 本研究では,最もよく知られた古典的アルゴリズムの量子スピードアップを実現するハイパーグラフコミュニティ検出のための量子アルゴリズムを開発し,空間のスーパーポリノミカルセーブを行う。 提案アルゴリズムは,従来検討されていたTensor PCAや$p$XORSATといった問題を,より広範な確率ブロックモデルに拡張した菊池法に基づいている。 この手法の(近く)最適性を示すために、低次フレームワークにおける下界(対数係数まで)のマッチングを証明し、このアルゴリズムがスムーズな統計的-計算的トレードオフを飽和させることを示す。 量子スピードアップは、菊池法の量子化バージョンから発生し、基礎となるコミュニティ構造と相関する誘導状態の効率的な調製に基づいている。 我々の研究は、菊池法を用いた以前の量子スピードアップが、従来考えられていたよりも幅広い問題の集合を包含するのに十分頑健であることを示唆している。

関連論文リスト

• The quantum super-Krylov method [0.6066442015301664]
  リアルタイムの進化と回復確率のみを利用する新しいKQD法を提案する。 ノイズの多いデータに対して頑健な新しい微分推定アルゴリズムを提案する。 ハミルトニアンスペクトルの仮定の下で、我々のアルゴリズムは指数関数的に基底状態エネルギーに収束することが証明される。
  論文  参考訳（メタデータ） (2024-12-23T05:21:43Z)
• Bayesian Quantum Amplitude Estimation [46.03321798937855]
  量子振幅推定のための問題調整およびノイズ認識ベイズアルゴリズムであるBAEを提案する。 耐障害性シナリオでは、BAEはハイゼンベルク限界を飽和させることができ、デバイスノイズが存在する場合、BAEはそれを動的に特徴付け、自己適応することができる。 本稿では,振幅推定アルゴリズムのベンチマークを提案し,他の手法に対してBAEをテストする。
  論文  参考訳（メタデータ） (2024-12-05T18:09:41Z)
• Quantum Dissipative Search via Lindbladians [0.0]
  我々は、構造化されていない古典的な探索空間上の純粋に散逸した量子ランダムウォークを解析する。 ある種のジャンプ演算子は量子過程を古典的過程に複製させ、他方はオープン量子(OQRW)と古典的ランダムウォークの違いをもたらすことを示す。 また,従来観測されていた2次高速化も明らかにし,OQRWは古典的検索ほど効率的ではないことを示した。
  論文  参考訳（メタデータ） (2024-07-16T14:39:18Z)
• A Faster Algorithm for the Free Energy in One-Dimensional Quantum Systems [0.0]
  翻訳不変な1次元量子スピン系の自由エネルギー密度を有限範囲で近似する問題を考える。 この問題の複雑さは、既知の硬度問題と密接な関係にあるため自明ではないが、最近、古典的なサブポリノミカル時間アルゴリズムが提案されている。 そこで本研究では,これより優れたアルゴリズムを提案し,その実行時に厳密なバウンダリを与える。
  論文  参考訳（メタデータ） (2024-02-29T10:42:18Z)
• 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)
• Towards quantum advantage via topological data analysis [0.0]
  ロイズ,ガーネロン,ザナルディのトポロジカルデータ解析のためのアルゴリズムの背後にある量子アルゴリズムについて検討する。 ランク推定や複雑なネットワーク解析などの問題に対して,多数の新しい量子アルゴリズムを提供する。
  論文  参考訳（メタデータ） (2020-05-06T06:31:24Z)

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

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