Quantum Speedup for Network Coordination via Fourier Sparsity

• URL: http://arxiv.org/abs/2603.07485v1
• Date: Sun, 08 Mar 2026 06:03:43 GMT
• Title: Quantum Speedup for Network Coordination via Fourier Sparsity
• Abstract summary: We introduce the Fourier Network Coordination problem (Fourier-NC),unifying eight application domains.<n>For abelian and dihedral groups, classical sparse transforms match quantum in the same oracle model, limiting the advantage to at most.<n>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.<n>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
• Score: 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).

Related papers

• Optimal Lower Bounds for Hamiltonian Simulation [42.227880669333835]
  For Hamiltonian $H = sum_j h_j$, we proveally tight lower bounds on the gate and query complexities of simulating time evolution on a quantum computer.<n>Our hold for arbitrary term norms $|h_j|$, time $t$, and trace-distance error $$.
  arXiv  Detail & Related papers  (2026-07-22T07:41:32Z)
• From Hilbert's Tenth Problem to Quantum Speedup: Explicit Oracles for Bounded Diophantine Systems [0.0]
  We introduce a fully reversible algorithmic framework to solve Diophantine equations over bounded integer domains.<n>By moving beyond abstract black-box assumptions, this explicit architectural synthesis guarantees that the necessary quantum arithmetic acts as a bounded overhead.
  arXiv  Detail & Related papers  (2026-05-13T18:01:01Z)
• Probabilistic modeling over permutations using quantum computers [0.0]
  We develop a quantum algorithm that encodes the exact probabilistic model into the amplitudes of a quantum state.<n>We envision the scaling, limitations, and practical use of such an approach, which we envision to be a first step towards useful applications of non-Abelian QFTs.
  arXiv  Detail & Related papers  (2026-03-23T18:00:12Z)
• A Scalable Distributed Quantum Optimization Framework via Factor Graph Paradigm [46.08923284345648]
  We introduce a structure-aware framework for distributed quantum optimization.<n>We find that for a search space of size $N$, our framework achieves $O(sqrtN)$ query complexity up to processors and separator dependent factors.<n>We show that structure-aware decomposition delivers a practical path to scalable distributed quantum optimization on quantum networks.
  arXiv  Detail & Related papers  (2026-03-08T15:15:52Z)
• Average-case quantum complexity from glassiness [45.57609001239456]
  Glassiness -- a phenomenon in physics characterized by a rough free-energy landscape -- implies hardness for stable classical algorithms.<n>We prove that the standard notion of quantum glassiness based on replica symmetry breaking obstructs stable quantum algorithms for Gibbs sampling.
  arXiv  Detail & Related papers  (2025-10-09T17:37:33Z)
• Highly-efficient quantum Fourier transformations for some nonabelian groups [0.0]
  We present fast quantum Fourier transformations for a number of nonabelian groups of interest for high energy physics. For each group, we derive explicit quantum circuits and estimate resource scaling for fault-tolerant implementations.
  arXiv  Detail & Related papers  (2024-07-31T18:00:04Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  We study the problem of estimating frequency response functions of systems of coupled, classical harmonic oscillators using a quantum computer.<n>Our proposed quantum algorithm operates in the standard $s-sparse, oracle-based query access model.<n>We show that a simple adaptation of our algorithm solves the random glued-trees problem in time.
  arXiv  Detail & Related papers  (2024-05-14T15:28:37Z)
• On the quantum time complexity of divide and conquer [42.7410400783548]
  We study the time complexity of quantum divide and conquer algorithms for classical problems. We apply these theorems to an array of problems involving strings, integers, and geometric objects.
  arXiv  Detail & Related papers  (2023-11-28T01:06:03Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach. We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers. We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
  arXiv  Detail & Related papers  (2022-09-28T17:53:25Z)
• Simplifying a classical-quantum algorithm interpolation with quantum singular value transformations [0.0]
  We show that the scaling of $alpha$-QPE can be naturally and succinctly derived within framework of Quantum Singular Value Transformation. The better the approximation to the sign function, the fewer samples one needs to determine the sign accurately.
  arXiv  Detail & Related papers  (2022-07-29T17:57:03Z)
• Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
  Two models of quantum computation: CQ_d and QC_d. CQ_d captures the scenario of a d-depth quantum computer many times; QC_d is more analogous to measurement-based quantum computation. We show that, despite the similarities between CQ_d and QC_d, the two models are intrinsically, i.e. CQ_d $nsubseteq$ QC_d and QC_d $nsubseteq$ CQ_d relative to an oracle.
  arXiv  Detail & Related papers  (2022-01-06T03:10:53Z)
• Quantum information theory and Fourier multipliers on quantum groups [0.0]
  We compute the exact values of the minimum output entropy and the completely bounded minimal entropy of quantum channels acting on matrix algebras. Our results use a new and precise description of bounded Fourier multipliers from $mathrmL1(mathbbG)$ into $mathrmLp(mathbbG)$ for $1 p leq infty$ where $mathbbG$ is a co-amenable locally compact quantum group.
  arXiv  Detail & Related papers  (2020-08-27T09:47:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.