Towards a Hybrid Quantum Enhanced Solution for Densest k-Subgraph Problem

• URL: http://arxiv.org/abs/2606.03196v1
• Date: Tue, 02 Jun 2026 05:55:09 GMT
• Title: Towards a Hybrid Quantum Enhanced Solution for Densest k-Subgraph Problem
• Abstract summary: We study the application of Gaussian Boson Sampling (GBS) to the densest k-subgraph problem (DkSP)<n>We introduce effective classical post-processing strategies that transform, otherwise discarded, near-k samples into feasible solutions.
• Score: 0.6649512409446104
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the application of Gaussian Boson Sampling (GBS) to the densest k-subgraph problem (DkSP). GBS with hard post-selection suffers from poor sampling efficiency due to strict cardinality constraints. To address this limitation, we introduce effective classical post-processing strategies that transform, otherwise discarded, near-k samples into feasible solutions. A comprehensive set of simulations is carried out, demonstrating that these approaches achieve near-optimal solution quality while improving sampling efficiency by approximately 4X compared to post-selection on community-structured graphs, and also post-selection often fails to reach the optimal solution on sparse random graphs even with large number of samples. Furthermore, the proposed methods perform on par with, and in some cases outperform, established classical approaches for graphs up to moderate size. Overall, the results indicate that while GBS with post-selection alone is insufficient, its combination with lightweight classical refinement can be highly effective. This underscores the potential of hybrid quantum-classical frameworks and positions GBS as a promising sampling primitive for combinatorial graph optimization.

Related papers

• A Quantum Photonic Approach to Graph Coloring [0.688204255655161]
  Gaussian Boson Sampling (GBS) is a quantum computational model that leverages linear optics to solve sampling problems.<n>Recent experimental breakthroughs have demonstrated quantum advantage using GBS, motivating its application to real-world optimization problems.
  arXiv  Detail & Related papers  (2026-01-28T05:18:27Z)
• Gauging practical computational advantage using a classical, threshold-based Gaussian boson sampler [0.10923877073891444]
  We describe an efficient scalable Gaussian boson sampler based on a classical description of squeezed quantum light and a deterministic model of single-photon detectors.<n>We map several NP-Complete graph theoretic problems to equivalent Gaussian boson sampling problems and numerically explore the practical efficacy of our approach.
  arXiv  Detail & Related papers  (2025-07-23T14:58:18Z)
• Efficient Classical Sampling from Gaussian Boson Sampling Distributions on Unweighted Graphs [31.937752933240674]
  We propose Markov chain Monte Carlo-based algorithms to sample from GBS distributions on undirected, unweighted graphs.<n>Our main contribution is a double-loop variant of Glauber dynamics, whose stationary distribution matches the GBS distribution.<n>Our approach offers both theoretical guarantees and practical advantages for efficient classical sampling from GBS distributions on unweighted graphs.
  arXiv  Detail & Related papers  (2025-05-05T08:13:57Z)
• A Greedy Strategy for Graph Cut [95.2841574410968]
  We propose a greedy strategy to solve the problem of Graph Cut, called GGC.<n>It starts from the state where each data sample is regarded as a cluster and dynamically merges the two clusters.<n>GGC has a nearly linear computational complexity with respect to the number of samples.
  arXiv  Detail & Related papers  (2024-12-28T05:49:42Z)
• Proximal Oracles for Optimization and Sampling [18.77973093341588]
  We consider convex optimization with non-smooth objective function and log-concave sampling with non-smooth potential.<n>To overcome the challenges caused by non-smoothness, our algorithms employ two powerful proximal frameworks in optimization and sampling.
  arXiv  Detail & Related papers  (2024-04-02T18:52:28Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  We introduce a novel theoretical framework for analyzing the effectiveness of DeepMatching Networks and Reinforcement Learning methods. Our main contribution holds for a broad class of problems including Max-and Min-Cut, Max-$k$-Bipartite-Bi, Maximum-Weight-Bipartite-Bi, and Traveling Salesman Problem. As a byproduct of our analysis we introduce a novel regularization process over vanilla descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.
  arXiv  Detail & Related papers  (2023-10-08T23:39:38Z)
• High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noise [96.80184504268593]
  gradient, clipping is one of the key algorithmic ingredients to derive good high-probability guarantees. Clipping can spoil the convergence of the popular methods for composite and distributed optimization.
  arXiv  Detail & Related papers  (2023-10-03T07:49:17Z)
• Comparative Benchmark of a Quantum Algorithm for the Bin Packing Problem [0.8434687648198277]
  The Bin Packing Problem (BPP) stands out as a paradigmatic optimization problem in logistics. We have recently proposed a hybrid approach to the one dimensional BPP. We compare the performance of our procedure with other classical approaches.
  arXiv  Detail & Related papers  (2022-07-15T13:09:12Z)
• Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework [100.36569795440889]
  This work is on the iteration of zero-th-order (ZO) optimization which does not require first-order information. We show that with a graceful design in coordinate importance sampling, the proposed ZO optimization method is efficient both in terms of complexity as well as as function query cost.
  arXiv  Detail & Related papers  (2020-12-21T17:29:58Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• Cross Entropy Hyperparameter Optimization for Constrained Problem Hamiltonians Applied to QAOA [68.11912614360878]
  Hybrid quantum-classical algorithms such as Quantum Approximate Optimization Algorithm (QAOA) are considered as one of the most encouraging approaches for taking advantage of near-term quantum computers in practical applications. Such algorithms are usually implemented in a variational form, combining a classical optimization method with a quantum machine to find good solutions to an optimization problem. In this study we apply a Cross-Entropy method to shape this landscape, which allows the classical parameter to find better parameters more easily and hence results in an improved performance.
  arXiv  Detail & Related papers  (2020-03-11T13:52:41Z)

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.