論文の概要: Quantum Speedup for Network Coordination via Fourier Sparsity

• arxiv url: http://arxiv.org/abs/2603.07485v1
• Date: Sun, 08 Mar 2026 06:03:43 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-10 15:13:14.626382
• Title: Quantum Speedup for Network Coordination via Fourier Sparsity
• Title（参考訳）: フーリエ空間によるネットワークコーディネートのための量子スピードアップ
• Authors: Vinayak Dixit,
• Abstract要約: 本稿では、Fourier Network Coordination problem (Fourier-NC)を導入し、8つのアプリケーションドメインを統合する。 アーベル群と二面体群の場合、古典的なスパース変換は同じオラクルモデルの量子と一致し、極端に優位性を制限する。 真の分離は対称群 Sk に対して現れ、非自明なミニミザーを持つクラス関数コストに対する条件付き k! -> poly(k) の超指数的スピードアップである。 最小化共役類が構造的に決定されるとき、問題はNP (int) BQP に関係し、条件付き P の外にある(ロール6.5)。
• 参考スコア（独自算出の注目度）: 0.913755431537592
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Network coordination - synchronising traffic signals, scheduling trains, assigning communication slots requires minimising pairwise costs across coupled systems. These problems are NP-hard yet share a common Fourier-sparse structure exploitable by quantum algorithms. We introduce the Fourier Network Coordination problem (Fourier-NC),unifying eight application domains. For abelian and dihedral groups, classical sparse Fourier transforms match quantum in the same oracle model, limiting the advantage to at most polynomial. The genuine separation emerges for the symmetric group Sk: a conditional super-exponential speedup of k! -> poly(k) for class-function costs with non-trivial minimisers. When the minimising conjugacy class is structurally determined, the problem lies in NP (int) BQP and is conditionally outside P (Corollary 6.5), placing it in the intermediate complexity regime alongside integer factorisation and graph isomorphism. We formalise the abelian index α(G) = [G : Amax] as the structural invariant governing the quantum-classical gap and identify a three-regime complexity trichotomy: abelian ({α= 1, classical sFFT suffices), nearly abelian (α= dmax, polynomial advantage), and strongly non-abelian (α>>dmax, super-exponential advantage).
• Abstract（参考訳）: ネットワーク調整 - 信号の同期、列車のスケジューリング、通信スロットの割り当てには、結合システム間のペアワイズコストを最小化する必要がある。 これらの問題はNPハードであるが、量子アルゴリズムによって悪用される共通のフーリエスパース構造を共有している。 本稿では、Fourier Network Coordination problem (Fourier-NC)を導入し、8つのアプリケーションドメインを統合する。 アーベル群と二面体群の場合、古典的なスパースフーリエ変換は同じオラクルモデルで量子と一致し、ほとんどの多項式に対する優位性を制限する。 真の分離は対称群 Sk に対して現れる: k の条件付き超指数的スピードアップである。 -非自明なミニミザーを用いたクラス機能コストのポリ(k)。 最小化共役類が構造的に決定されるとき、問題はNP (int) BQP に関係し、条件付き P (Crollary 6.5) の外にある。 我々は、アーベル指数 α(G) = [G : Amax] を、量子古典的ギャップを支配する構造不変量として定式化し、アーベル({α=1, 古典的 sFFT サフィス)、ほぼアーベル(α=dmax, 多項式優位)、強非アーベル(α>>dmax, 超指数優位)の三項複素三分法を特定する。

関連論文リスト

• A Scalable Distributed Quantum Optimization Framework via Factor Graph Paradigm [46.08923284345648]
  分散量子最適化のための構造認識フレームワークを提案する。 検索スペースが$N$の場合、我々のフレームワークはプロセッサやセパレータに依存した要素に対して$O(sqrtN)$クエリ複雑性を達成する。 構造を考慮した分解は、量子ネットワーク上でのスケーラブルな分散量子最適化に実践的な道をもたらすことを示す。
  論文  参考訳（メタデータ） (2026-03-08T15:15:52Z)
• Average-case quantum complexity from glassiness [45.57609001239456]
  グラスネス(Glassiness)は、物理学において、不安定な自由エネルギーの風景を特徴とする現象であり、安定な古典的アルゴリズムの難しさを意味する。 レプリカ対称性の破れに基づく標準的な量子ガラス性の概念は、ギブスサンプリングのための安定な量子アルゴリズムを妨げていることを証明している。
  論文  参考訳（メタデータ） (2025-10-09T17:37:33Z)
• Highly-efficient quantum Fourier transformations for some nonabelian groups [0.0]
  我々は、高エネルギー物理学に対する多くの非アーベル群に対する高速量子フーリエ変換を示す。 各グループに対して、明示的な量子回路とフォールトトレラント実装のリソーススケーリングを導出する。
  論文  参考訳（メタデータ） (2024-07-31T18:00:04Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  量子コンピュータを用いた結合型古典的高調波発振器系の周波数応答関数の推定問題について検討する。 提案する量子アルゴリズムは,標準的な$sスパース,オーラクルベースのクエリアクセスモデルで動作する。 そこで,本アルゴリズムの簡単な適応により,時間内に無作為な結束木問題を解くことを示す。
  論文  参考訳（メタデータ） (2024-05-14T15:28:37Z)
• 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)
• Simplifying a classical-quantum algorithm interpolation with quantum singular value transformations [0.0]
  本稿では,量子特異値変換の枠組みにおいて,$alpha$-QPEのスケーリングが自然かつ簡潔に導出可能であることを示す。 符号関数の近似が良くなるほど、符号を正確に決定する必要があるサンプルは少なくなる。
  論文  参考訳（メタデータ） (2022-07-29T17:57:03Z)
• Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
  量子計算の2つのモデル: CQ_dとQC_d。 CQ_dは、d-d-deepth量子コンピュータのシナリオを何度も捉え、QC_dは測定ベースの量子計算に類似している。 CQ_dとQC_dの類似性にもかかわらず、2つのモデルは本質的にはCQ_d $nsubseteq$QC_dとQC_d $nsubseteq$CQ_dである。
  論文  参考訳（メタデータ） (2022-01-06T03:10:53Z)
• Quantum information theory and Fourier multipliers on quantum groups [0.0]
  最小出力エントロピーの正確な値と、行列代数に作用する量子チャネルの完全有界最小エントロピーを計算する。 我々の結果は、$mathrmL1(mathbbG)$から$mathrmLp(mathbbG)$への有界フーリエ乗算の新たな正確な記述を用いている。
  論文  参考訳（メタデータ） (2020-08-27T09:47:10Z)

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

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