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:2204.05254 · Physical Review X

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

S. Sempere-Llagostera, Raj B. Patel, Ian A. Walmsley, W. Steven Kolthammer

Published Sep 30, 2022• 20 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physrevx.12.031045

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

Probing Graph Similarity Through Multiple Photons in Frequency-Time Bin Modes Generated by a Silicon Nitride Microresonator

Massimo Borghi, Emanuele Brusaschi, Marco Liscidini +2 more

Boson-sampling problems are specific cases of multi-photon quantum interference in which the complexity of sampling from the output distribution of multiple photons on multiple modes arises from its relation to certain matrix functions that cannot be efficiently computed in polynomial time using the best-known classical algorithms. Specifically, gaussian boson sampling (GBS) is a protocol that employs Gaussian states as inputs to a linear interferometer, and whose output samples can be used to accelerate graph search and optimization problems [1]. To date, GBS experiments have been reported by using path or time-bin encoding of the optical modes.

Conference on Lasers and Electro-Optics Europe & European Quantum Electronics Conference (CLEO/Europe-EQEC)•Jun 23, 2025•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

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

Sample efficient graph classification using binary Gaussian boson sampling

Amanuel Anteneh, Olivier Pfister

We present a variation of a quantum algorithm for the machine learning task of classification with graph-structured data. The algorithm implements a feature extraction strategy that is based on Gaussian boson sampling (GBS), a near-term model of quantum computing. However, unlike the currently proposed algorithms for this problem, our GBS setup requires only binary (light or no light) detectors, as opposed to photon-number-resolving detectors. Binary detectors are technologically simpler and can operate near room temperature, making our algorithm much less complex and costly to implement physically. We also investigate the connection between graph theory and the Torontonian matrix function which characterizes the probabilities of binary GBS detection events.

arXiv:2301.01232•Physical Review A•Dec 11, 2023•3 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
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.
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.
Boson-sampling problems are specific cases of multi-photon quantum interference in which the complexity of sampling from the output distribution of multiple photons on multiple modes arises from its relation to certain matrix functions that cannot be efficiently computed in polynomial time using the best-known classical algorithms. Specifically, gaussian boson sampling (GBS) is a protocol that employs Gaussian states as inputs to a linear interferometer, and whose output samples can be used to accelerate graph search and optimization problems [1]. To date, GBS experiments have been reported by using path or time-bin encoding of the optical modes.
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 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.
We present a variation of a quantum algorithm for the machine learning task of classification with graph-structured data. The algorithm implements a feature extraction strategy that is based on Gaussian boson sampling (GBS), a near-term model of quantum computing. However, unlike the currently proposed algorithms for this problem, our GBS setup requires only binary (light or no light) detectors, as opposed to photon-number-resolving detectors. Binary detectors are technologically simpler and can operate near room temperature, making our algorithm much less complex and costly to implement physically. We also investigate the connection between graph theory and the Torontonian matrix function which characterizes the probabilities of binary GBS detection events.
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.