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:1803.10730 · Physical Review Letters

Using Gaussian Boson Sampling to Find Dense Subgraphs

Juan Miguel Arrazola, Thomas R. Bromley

Published Jul 19, 2018• 140 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physrevlett.121.030503

Related papers

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

Ravi Sangwan, Prabhat Anand, M Girish Chandra

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.

quant-pharXiv:2606.03196•Jun 3, 2026•0 citations

Gaussian-boson-sampling-enhanced dense subgraph finding shows limited advantage over efficient classical algorithms

Naomi R. Solomons, O. Thomas, Dara P. S. McCutcheon

Recent claims of achieving exponential quantum advantage have attracted attention to Gaussian boson sampling (GBS), a potential application of which is dense subgraph finding. We investigate the effects of sources of error including loss and spectral impurity on GBS applied to dense subgraph finding algorithms. We find that the effectiveness of these algorithms is remarkably robust to errors, to such an extent that there exist efficient classical algorithms that can simulate the underlying GBS. These results imply that the speedup of GBS-based algorithms for the dense subgraph problem over classical approaches is at most polynomial, though this could be achieved on a quantum device with dramatically less stringent requirements on loss and photon purity than general GBS.

arXiv:2301.13217•Jan 30, 2023•0 citations

Displaced Gaussian Boson Sampling for enhanced max-clique search

Ewan Mer, Zhenghao Li, Shang Yu +2 more

Gaussian Boson Sampling (GBS) is capable of solving certain classes of graph problems owing to the samples produced by such a device having a connection to the hafnian matrix function. In particular, a GBS device has been shown to provide an enhancement in the search of cliques -- or complete subgraphs -- in undirected weighted graphs over classical algorithms. A graph can be mapped to a GBS experiment by configuring the squeezing parameters of the input states and programming the linear optical network. In practice, limited squeezing and photon loss degrade the performance of the GBS device for max-clique search. In comparison, coherent states -- often considered a classical resource due to their Poissonian statistics -- can be readily prepared across many modes using an attenuated laser. In this paper, we report an enhancement of the success rate of GBS in finding maximum weighted cliques by adding displacements under lossy conditions or when a limited amount of squeezing is available. Moreover, we report that this enhancement can be scaled up to large graphs with limited resource overheads.

quant-pharXiv:2605.27522•May 28, 2026•0 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

Experimentally Finding Dense Subgraphs Using a Time-Bin Encoded Gaussian Boson Sampling Device

S. Sempere-Llagostera, Raj B. Patel, Ian A. Walmsley +1 more

Gaussian boson sampling is a quantum computing concept based on drawing samples from a multimode nonclassical Gaussian state using photon-number resolving detectors.It was initially posed as a near-term approach to achieve quantum advantage, and several applications have been proposed since, including the calculation of graph features.For the first time, we use a time-bin encoded interferometer to implement Gaussian boson sampling experimentally and extract samples to enhance the search for dense subgraphs in a graph.Our results indicate an improvement over classical methods for subgraphs of sizes three and four in a graph containing ten nodes.In addition, we numerically explore the role of imperfections in the optical circuit and on the performance of the algorithm.

arXiv:2204.05254•Physical Review X•Sep 30, 2022•20 citations

Solving Graph Problems Using Gaussian Boson Sampling

Yu‐Hao Deng, Si-Qiu Gong, Yi-Chao Gu +21 more

Gaussian boson sampling (GBS) is not only a feasible protocol for demonstrating quantum computational advantage, but also mathematically associated with certain graph-related and quantum chemistry problems. In particular, it is proposed that the generated samples from the GBS could be harnessed to enhance the classical stochastic algorithms in searching some graph features. Here, we use Jiǔzhāng, a noisy intermediate-scale quantum computer, to solve graph problems. The samples are generated from a 144-mode fully connected photonic processor, with photon click up to 80 in the quantum computational advantage regime. We investigate the open question of whether the GBS enhancement over the classical stochastic algorithms persists-and how it scales-with an increasing system size on noisy quantum devices in the computationally interesting regime. We experimentally observe the presence of GBS enhancement with a large photon-click number and a robustness of the enhancement under certain noise. Our work is a step toward testing real-world problems using the existing noisy intermediate-scale quantum computers and hopes to stimulate the development of more efficient classical and quantum-inspired algorithms.

arXiv:2302.00936•Physical Review Letters•May 9, 2023•60 citations
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.
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.
Recent claims of achieving exponential quantum advantage have attracted attention to Gaussian boson sampling (GBS), a potential application of which is dense subgraph finding. We investigate the effects of sources of error including loss and spectral impurity on GBS applied to dense subgraph finding algorithms. We find that the effectiveness of these algorithms is remarkably robust to errors, to such an extent that there exist efficient classical algorithms that can simulate the underlying GBS. These results imply that the speedup of GBS-based algorithms for the dense subgraph problem over classical approaches is at most polynomial, though this could be achieved on a quantum device with dramatically less stringent requirements on loss and photon purity than general GBS.
Gaussian Boson Sampling (GBS) is capable of solving certain classes of graph problems owing to the samples produced by such a device having a connection to the hafnian matrix function. In particular, a GBS device has been shown to provide an enhancement in the search of cliques -- or complete subgraphs -- in undirected weighted graphs over classical algorithms. A graph can be mapped to a GBS experiment by configuring the squeezing parameters of the input states and programming the linear optical network. In practice, limited squeezing and photon loss degrade the performance of the GBS device for max-clique search. In comparison, coherent states -- often considered a classical resource due to their Poissonian statistics -- can be readily prepared across many modes using an attenuated laser. In this paper, we report an enhancement of the success rate of GBS in finding maximum weighted cliques by adding displacements under lossy conditions or when a limited amount of squeezing is available. Moreover, we report that this enhancement can be scaled up to large graphs with limited resource overheads.
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 is a quantum computing concept based on drawing samples from a multimode nonclassical Gaussian state using photon-number resolving detectors.It was initially posed as a near-term approach to achieve quantum advantage, and several applications have been proposed since, including the calculation of graph features.For the first time, we use a time-bin encoded interferometer to implement Gaussian boson sampling experimentally and extract samples to enhance the search for dense subgraphs in a graph.Our results indicate an improvement over classical methods for subgraphs of sizes three and four in a graph containing ten nodes.In addition, we numerically explore the role of imperfections in the optical circuit and on the performance of the algorithm.
Gaussian boson sampling (GBS) is not only a feasible protocol for demonstrating quantum computational advantage, but also mathematically associated with certain graph-related and quantum chemistry problems. In particular, it is proposed that the generated samples from the GBS could be harnessed to enhance the classical stochastic algorithms in searching some graph features. Here, we use Jiǔzhāng, a noisy intermediate-scale quantum computer, to solve graph problems. The samples are generated from a 144-mode fully connected photonic processor, with photon click up to 80 in the quantum computational advantage regime. We investigate the open question of whether the GBS enhancement over the classical stochastic algorithms persists-and how it scales-with an increasing system size on noisy quantum devices in the computationally interesting regime. We experimentally observe the presence of GBS enhancement with a large photon-click number and a robustness of the enhancement under certain noise. Our work is a step toward testing real-world problems using the existing noisy intermediate-scale quantum computers and hopes to stimulate the development of more efficient classical and quantum-inspired algorithms.