Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2606.03196

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

Ravi Sangwan, Prabhat Anand, M Girish Chandra

quant-phSubmitted Jun 2, 2026• Announced Jun 3, 2026• 0 citations
arXivHTMLPDF

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.

Comments
9 pages, 5 figures, and 2 tables

Related papers

Using Gaussian Boson Sampling to Find Dense Subgraphs

Juan Miguel Arrazola, Thomas R. Bromley

Boson sampling devices are a prime candidate for exhibiting quantum supremacy, yet their application for solving problems of practical interest is less well understood. Here we show that Gaussian boson sampling (GBS) can be used for dense subgraph identification. Focusing on the NP-hard densest k-subgraph problem, we find that stochastic algorithms are enhanced through GBS, which selects dense subgraphs with high probability. These findings rely on a link between graph density and the number of perfect matchings-enumerated by the Hafnian-which is the relevant quantity determining sampling probabilities in GBS. We test our findings by constructing GBS-enhanced versions of the random search and simulated annealing algorithms and apply them through numerical simulations of GBS to identify the densest subgraph of a 30 vertex graph.

arXiv:1803.10730•Physical Review Letters•Jul 19, 2018•140 citations

Efficient classical sampling from Gaussian boson sampling distributions on unweighted graphs

Yexin Zhang, Shuo Zhou, Xinzhao Wang +5 more

Gaussian Boson Sampling (GBS) is a promising candidate for demonstrating quantum computational advantage and can be applied to solving graph-related problems. In this work, we propose Markov chain Monte Carlo-based algorithms to sample from GBS distributions on undirected, unweighted graphs. Our main contribution is a double-loop variant of Glauber dynamics, whose stationary distribution matches the GBS distribution. We further prove that it mixes in polynomial time for dense graphs using a refined canonical path argument. Numerically, we conduct experiments on unweighted graphs with 256 vertices, larger than the scales in former GBS experiments as well as classical simulations. In particular, we show that both the single-loop and double-loop Glauber dynamics improve the performance of original random search and simulated annealing algorithms for the max-Hafnian and densest k-subgraph problems up to 10 ×. Overall, our approach offers both theoretical guarantees and practical advantages for efficient classical sampling from GBS distributions on unweighted graphs. The authors propose Markov chain Monte Carlo algorithms to sample from GBS distributions on unweighted graphs, and prove that it mixes in polynomial time for dense graphs. Numerical experiments on 256-vertex graphs are conducted, demonstrating that the algorithm improves the performance up to 10x.

arXiv:2505.02445•Nature Communications•Oct 22, 2025•1 citation

A Quantum Photonic Approach to Graph Coloring

Jesua Epequin, Pascale Bendotti, Joseph Mikael

Gaussian Boson Sampling (GBS) is a quantum computational model that leverages linear optics to solve sampling problems believed to be classically intractable. Recent experimental breakthroughs have demonstrated quantum advantage using GBS, motivating its application to real-world combinatorial optimization problems. In this work, we reformulate the graph coloring problem as an integer programming problem using the independent set formulation. This enables the use of GBS to identify cliques in the complement graph, which correspond to independent sets in the original graph. Our method is benchmarked against classical heuristics and exact algorithms on two sets of instances: Erdős-Rényi random graphs and graphs derived from a smart-charging use case. The results demonstrate that GBS can provide competitive solutions, highlighting its potential as a quantum-enhanced heuristic for graph-based optimization.

quant-pharXiv:2601.20263•Jan 29, 2026•0 citations

Quantum-Inspired Classical Algorithm for Graph Problems by Gaussian Boson Sampling

Changhun Oh, Bill Fefferman, Liang Jiang +1 more

We present a quantum-inspired classical algorithm that can be used for graph-theoretical problems, such as finding the densest k subgraph and finding the maximum weight clique, which are proposed as applications of a Gaussian boson sampler. The main observation from Gaussian boson samplers is that a given graph’s adjacency matrix to be encoded in a Gaussian boson sampler is non-negative and that computing the output probability of Gaussian boson sampling restricted to a non-negative adjacency matrix is thought to be strictly easier than general cases. We first provide how to program a given graph problem into our efficient classical algorithm. We then numerically compare the performance of ideal and lossy Gaussian boson samplers, our quantum-inspired classical sampler, and the uniform sampler for finding the densest k subgraph and finding the maximum weight clique and show that the advantage from Gaussian boson samplers is not significant in general. We finally discuss the potential advantage of a Gaussian boson sampler over the proposed quantum-inspired classical sampler. Published by the American Physical Society 2024

arXiv:2302.00536•PRX Quantum•May 23, 2024•11 citations

Gaussian Boson Sampling to Accelerate NP-Complete Vertex-Minor Graph Classification

Mushkan Sureka, Saikat Guha

Gaussian Boson Sampling (GBS) generates random samples of photon-click patterns from a class of probability distributions that are hard for a classical computer to sample from. Despite heroic demonstrations of quantum supremacy using GBS, Boson Sampling, and instantaneous quantum polynomial (IQP) algorithms, systematic evaluations of the power of these quantum-enhanced random samplers when applied to provably hard problems, and performance comparisons with best-known classical algorithms have been lacking. We propose a hybrid quantum-classical algorithm using the GBS for the NP-complete problem of determining if two graphs are a vertex minor of one another. The graphs are encoded in GBS and the generated random samples serve as feature vectors in a support vector machine (SVM) classifier. We find a graph embedding that allows trading between the one-shot classification accuracy and the amount of input squeezing, a hard-to-produce quantum resource, followed by repeated trials and a majority vote to reach an overall desired accuracy. We introduce a new classical algorithm based on graph spectra, which we show outperforms various well-known graph-similarity algorithms. We compare the performance of our algorithm with this classical algorithm and analyze their time versus problem-size scaling, to yield a desired classification accuracy. Our simulation results suggest that with a near-term realizable GBS device—5 dB pulsed squeezers, 12-mode unitary, and reasonable assumptions on coupling efficiency, on-chip losses, and detection efficiency of photon number resolving detectors—we can solve 12-node vertex-minor instances with about 103fold lower time compared to a powerful desktop computer.

arXiv:2402.03524•IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 15, 2024•0 citations

Post-selection in noisy Gaussian boson sampling: part is better than whole

Tian-Yu Yang, Yi-Xin Shen, Zhou‐Kai Cao +1 more

Abstract Gaussian boson sampling (GBS) is originally proposed to show quantum advantage with quantum linear optical elements. Recently, several experimental breakthroughs based on GBS pointing to quantum computing supremacy have been presented. However, due to technical limitations, the outcomes of GBS devices are influenced severely by photon loss. Here, we present a practical method to reduce the negative effect caused by photon loss. We first show with explicit formulas that a GBS process can be mapped to another GBS processes. Based on this result, we propose a post-selection method which discards low-quality data according to our criterion to improve the performance of the final computational results, say part is better than whole. As an example, we show that the post-selection method can turn a GBS experiment that would otherwise fail in a ‘non-classicality test’ into one that can pass that test. Besides improving the robustness of computation results of current GBS devices, this post-selection method may also benefit the further development of GBS-based quantum algorithms.

arXiv:2205.02586•Quantum Science and Technology•Aug 15, 2023•3 citations
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.
Boson sampling devices are a prime candidate for exhibiting quantum supremacy, yet their application for solving problems of practical interest is less well understood. Here we show that Gaussian boson sampling (GBS) can be used for dense subgraph identification. Focusing on the NP-hard densest k-subgraph problem, we find that stochastic algorithms are enhanced through GBS, which selects dense subgraphs with high probability. These findings rely on a link between graph density and the number of perfect matchings-enumerated by the Hafnian-which is the relevant quantity determining sampling probabilities in GBS. We test our findings by constructing GBS-enhanced versions of the random search and simulated annealing algorithms and apply them through numerical simulations of GBS to identify the densest subgraph of a 30 vertex graph.
Gaussian Boson Sampling (GBS) is a promising candidate for demonstrating quantum computational advantage and can be applied to solving graph-related problems. In this work, we propose Markov chain Monte Carlo-based algorithms to sample from GBS distributions on undirected, unweighted graphs. Our main contribution is a double-loop variant of Glauber dynamics, whose stationary distribution matches the GBS distribution. We further prove that it mixes in polynomial time for dense graphs using a refined canonical path argument. Numerically, we conduct experiments on unweighted graphs with 256 vertices, larger than the scales in former GBS experiments as well as classical simulations. In particular, we show that both the single-loop and double-loop Glauber dynamics improve the performance of original random search and simulated annealing algorithms for the max-Hafnian and densest k-subgraph problems up to 10 ×. Overall, our approach offers both theoretical guarantees and practical advantages for efficient classical sampling from GBS distributions on unweighted graphs. The authors propose Markov chain Monte Carlo algorithms to sample from GBS distributions on unweighted graphs, and prove that it mixes in polynomial time for dense graphs. Numerical experiments on 256-vertex graphs are conducted, demonstrating that the algorithm improves the performance up to 10x.
Gaussian Boson Sampling (GBS) is a quantum computational model that leverages linear optics to solve sampling problems believed to be classically intractable. Recent experimental breakthroughs have demonstrated quantum advantage using GBS, motivating its application to real-world combinatorial optimization problems. In this work, we reformulate the graph coloring problem as an integer programming problem using the independent set formulation. This enables the use of GBS to identify cliques in the complement graph, which correspond to independent sets in the original graph. Our method is benchmarked against classical heuristics and exact algorithms on two sets of instances: Erdős-Rényi random graphs and graphs derived from a smart-charging use case. The results demonstrate that GBS can provide competitive solutions, highlighting its potential as a quantum-enhanced heuristic for graph-based optimization.
We present a quantum-inspired classical algorithm that can be used for graph-theoretical problems, such as finding the densest k subgraph and finding the maximum weight clique, which are proposed as applications of a Gaussian boson sampler. The main observation from Gaussian boson samplers is that a given graph’s adjacency matrix to be encoded in a Gaussian boson sampler is non-negative and that computing the output probability of Gaussian boson sampling restricted to a non-negative adjacency matrix is thought to be strictly easier than general cases. We first provide how to program a given graph problem into our efficient classical algorithm. We then numerically compare the performance of ideal and lossy Gaussian boson samplers, our quantum-inspired classical sampler, and the uniform sampler for finding the densest k subgraph and finding the maximum weight clique and show that the advantage from Gaussian boson samplers is not significant in general. We finally discuss the potential advantage of a Gaussian boson sampler over the proposed quantum-inspired classical sampler. Published by the American Physical Society 2024
Gaussian Boson Sampling (GBS) generates random samples of photon-click patterns from a class of probability distributions that are hard for a classical computer to sample from. Despite heroic demonstrations of quantum supremacy using GBS, Boson Sampling, and instantaneous quantum polynomial (IQP) algorithms, systematic evaluations of the power of these quantum-enhanced random samplers when applied to provably hard problems, and performance comparisons with best-known classical algorithms have been lacking. We propose a hybrid quantum-classical algorithm using the GBS for the NP-complete problem of determining if two graphs are a vertex minor of one another. The graphs are encoded in GBS and the generated random samples serve as feature vectors in a support vector machine (SVM) classifier. We find a graph embedding that allows trading between the one-shot classification accuracy and the amount of input squeezing, a hard-to-produce quantum resource, followed by repeated trials and a majority vote to reach an overall desired accuracy. We introduce a new classical algorithm based on graph spectra, which we show outperforms various well-known graph-similarity algorithms. We compare the performance of our algorithm with this classical algorithm and analyze their time versus problem-size scaling, to yield a desired classification accuracy. Our simulation results suggest that with a near-term realizable GBS device—5 dB pulsed squeezers, 12-mode unitary, and reasonable assumptions on coupling efficiency, on-chip losses, and detection efficiency of photon number resolving detectors—we can solve 12-node vertex-minor instances with about 103fold lower time compared to a powerful desktop computer.
Abstract Gaussian boson sampling (GBS) is originally proposed to show quantum advantage with quantum linear optical elements. Recently, several experimental breakthroughs based on GBS pointing to quantum computing supremacy have been presented. However, due to technical limitations, the outcomes of GBS devices are influenced severely by photon loss. Here, we present a practical method to reduce the negative effect caused by photon loss. We first show with explicit formulas that a GBS process can be mapped to another GBS processes. Based on this result, we propose a post-selection method which discards low-quality data according to our criterion to improve the performance of the final computational results, say part is better than whole. As an example, we show that the post-selection method can turn a GBS experiment that would otherwise fail in a ‘non-classicality test’ into one that can pass that test. Besides improving the robustness of computation results of current GBS devices, this post-selection method may also benefit the further development of GBS-based quantum algorithms.