Quartic quantum speedups for community detection

• URL: http://arxiv.org/abs/2510.08494v1
• Date: Thu, 09 Oct 2025 17:35:17 GMT
• Title: Quartic quantum speedups for community detection
• Authors: Alexander Schmidhuber, Alexander Zlokapa,
• Abstract summary: We develop a quantum algorithm for hypergraph community detection that achieves a quartic quantum speedup.<n>Our algorithm is based on the Kikuchi method, which we extend beyond previously considered problems such as PCA and $p$XORSAT.
• Score: 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.

Related papers

• Decentralized Optimization on Compact Submanifolds by Quantized Riemannian Gradient Tracking [45.147301546565316]
  This paper considers the problem of decentralized optimization on compact submanifolds.<n>We propose an algorithm where agents update variables using quantized variables.<n>To the best of our knowledge, this is the first algorithm to achieve an $mathcalO (1/K)$ convergence rate in the presence of quantization.
  arXiv  Detail & Related papers  (2025-06-09T01:57:25Z)
• A quantum algorithm for Khovanov homology [42.6618666851542]
  Khovanov homology is a knot that categorifies the Jones topological invariant, recognizes the unknot, and is conjectured to appear as an observable in $4D$ supersymmetric Yang-Mills theory.<n>Despite its rich mathematical and physical significance, the computational complexity of Khovanov homology remains largely unknown.
  arXiv  Detail & Related papers  (2025-01-21T18:54:59Z)
• The quantum super-Krylov method [0.6066442015301664]
  We present a novel KQD method that uses only real-time evolutions and recovery probabilities.<n>We present a novel derivative estimation algorithm that is robust to noisy data.<n>Under assumptions on the spectrum of the Hamiltonian, we prove that our algorithm converges exponentially quickly to the ground-state energy.
  arXiv  Detail & Related papers  (2024-12-23T05:21:43Z)
• Bayesian Quantum Amplitude Estimation [46.03321798937855]
  We present BAE, a problem-tailored and noise-aware Bayesian algorithm for quantum amplitude estimation.<n>In a fault tolerant scenario, BAE is capable of saturating the Heisenberg limit; if device noise is present, BAE can dynamically characterize it and self-adapt.<n>We propose a benchmark for amplitude estimation algorithms and use it to test BAE against other approaches.
  arXiv  Detail & Related papers  (2024-12-05T18:09:41Z)
• Quantum Dissipative Search via Lindbladians [0.0]
  We analyze a purely dissipative quantum random walk on an unstructured classical search space.<n>We show that certain jump operators make the quantum process replicate a classical one, while others yield differences between open quantum (OQRW) and classical random walks.<n>We also clarify a previously observed quadratic speedup, demonstrating that OQRWs are no more efficient than classical search.
  arXiv  Detail & Related papers  (2024-07-16T14:39:18Z)
• Quartic quantum speedups for planted inference [44.820711784498]
  We describe a quantum algorithm for the Planted Noisy $k$XOR problem.<n>Our work suggests that some constructions are susceptible to super-quadratic quantum attacks.
  arXiv  Detail & Related papers  (2024-06-27T17:54:28Z)
• A Faster Algorithm for the Free Energy in One-Dimensional Quantum Systems [0.0]
  We consider the problem of approximating the free energy density of a translation-invariant, one-dimensional quantum spin system with finite range. While the complexity of this problem is nontrivial due to its close connection to problems with known hardness results, a classical subpolynomial-time algorithm has recently been proposed. We propose an algorithm outperforming this resultally and give rigorous bounds on its runtime.
  arXiv  Detail & Related papers  (2024-02-29T10:42:18Z)
• 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)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  We analyze and optimize an improved quantum algorithm for topological data analysis. We show that super-quadratic quantum speedups are only possible when targeting a multiplicative error approximation. We argue that quantum circuits with tens of billions of Toffoli can solve seemingly classically intractable instances.
  arXiv  Detail & Related papers  (2022-09-27T17:56:15Z)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees. Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation. We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
  arXiv  Detail & Related papers  (2022-03-30T02:02:16Z)
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing [0.0]
  We assess the prospects for algorithms within the general framework of quantum annealing (QA) to achieve a quantum speedup. We argue for continued exploration and interest in the QA framework on the basis that improved coherence times and control capabilities will enable the near-term exploration of several quantum optimization algorithms. We argue that all of these protocols can be explored in a state-of-the-art manner by embracing the full range of novel out-of-equilibrium quantum dynamics generated by time-dependent effective transverse-field Ising Hamiltonians.
  arXiv  Detail & Related papers  (2020-08-22T21:25:51Z)
• Towards quantum advantage via topological data analysis [0.0]
  We study the quantum-algorithmic methods behind the algorithm for topological data analysis of Lloyd, Garnerone and Zanardi. We provide a number of new quantum algorithms for problems such as rank estimation and complex network analysis.
  arXiv  Detail & Related papers  (2020-05-06T06:31:24Z)

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.