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:2507.17567 · IEEE International Conference on Quantum Computing and Engineering (QCE)

Gauging Practical Computational Advantage Using a Classical, Threshold-Based Gaussian Boson Sampler

Sarvesh Raghuraman, Aditya Patwardhan, Brian R. La Cour

Published Aug 30, 2025• 0 citations
arXivHTMLPDF

Abstract

We describe an efficient, scalable, quantum-inspired, Gaussian boson sampler based on a classical description of squeezed quantum light and a deterministic model of singlephoton detectors that “click” when the incident amplitude falls above a given threshold. Using this model, we map several NPComplete graph theoretic problems to equivalent Gaussian boson sampling problems and numerically explore the practical efficacy of our approach. Specifically, for a given weighted, undirected graph we examined finding the densest$k$-subgraph and the maximum weighted clique. We also examined the graph classification problem. Compared to traditional classical solvers, we found that our method provides better solutions in a comparable amount of samples for graphs with up to 2000 nodes.

DOI
10.1109/qce65121.2025.00162

Related papers

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

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

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

Molecular docking with Gaussian Boson Sampling

Leonardo Banchi, Mark Fingerhuth, Tomas Babej +2 more

Gaussian Boson Samplers are photonic quantum devices with the potential to perform intractable tasks for classical systems. As with other near-term quantum technologies, an outstanding challenge is to identify specific problems of practical interest where these devices can prove useful. Here, we show that Gaussian Boson Samplers can be used to predict molecular docking configurations, a central problem for pharmaceutical drug design. We develop an approach where the problem is reduced to finding the maximum weighted clique in a graph, and show that Gaussian Boson Samplers can be programmed to sample large-weight cliques, i.e., stable docking configurations, with high probability, even with photon losses. We also describe how outputs from the device can be used to enhance the performance of classical algorithms. To benchmark our approach, we predict the binding mode of a ligand to the tumor necrosis factor-α converting enzyme, a target linked to immune system diseases and cancer.

arXiv:1902.00462•Science Advances•Jun 5, 2020•169 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

Certification of Gaussian Boson Sampling via graphs feature vectors and kernels

Taira Giordani, Valerio Mannucci, Nicolò Spagnolo +4 more

Abstract Gaussian Boson Sampling (GBS) is a non-universal model for quantum computing inspired by the original formulation of the Boson Sampling (BS) problem. Nowadays, it represents a paradigmatic quantum platform to reach the quantum advantage regime in a specific computational model. Indeed, thanks to the implementation in photonics-based processors, the latest GBS experiments have reached a level of complexity where the quantum apparatus has solved the task faster than currently up-to-date classical strategies. In addition, recent studies have identified possible applications beyond the inherent sampling task. In particular, a direct connection between photon counting of a genuine GBS device and the number of perfect matchings in a graph has been established. In this work, we propose to exploit such a connection to benchmark GBS experiments. We interpret the properties of the feature vectors of the graph encoded in the device as a signature of correct sampling from the true input state. Within this framework, two approaches are presented. The first method exploits the distributions of graph feature vectors and classification via neural networks. The second approach investigates the distributions of graph kernels. Our results provide a novel approach to the actual need for tailored algorithms to benchmark large-scale Gaussian Boson Samplers.

arXiv:2202.07711•Quantum Science and Technology•Sep 30, 2022•9 citations
We describe an efficient, scalable, quantum-inspired, Gaussian boson sampler based on a classical description of squeezed quantum light and a deterministic model of singlephoton detectors that “click” when the incident amplitude falls above a given threshold. Using this model, we map several NPComplete graph theoretic problems to equivalent Gaussian boson sampling problems and numerically explore the practical efficacy of our approach. Specifically, for a given weighted, undirected graph we examined finding the densestkkk-subgraph and the maximum weighted clique. We also examined the graph classification problem. Compared to traditional classical solvers, we found that our method provides better solutions in a comparable amount of samples for graphs with up to 2000 nodes.
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) 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) 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.
Gaussian Boson Samplers are photonic quantum devices with the potential to perform intractable tasks for classical systems. As with other near-term quantum technologies, an outstanding challenge is to identify specific problems of practical interest where these devices can prove useful. Here, we show that Gaussian Boson Samplers can be used to predict molecular docking configurations, a central problem for pharmaceutical drug design. We develop an approach where the problem is reduced to finding the maximum weighted clique in a graph, and show that Gaussian Boson Samplers can be programmed to sample large-weight cliques, i.e., stable docking configurations, with high probability, even with photon losses. We also describe how outputs from the device can be used to enhance the performance of classical algorithms. To benchmark our approach, we predict the binding mode of a ligand to the tumor necrosis factor-α converting enzyme, a target linked to immune system diseases and cancer.
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.
Abstract Gaussian Boson Sampling (GBS) is a non-universal model for quantum computing inspired by the original formulation of the Boson Sampling (BS) problem. Nowadays, it represents a paradigmatic quantum platform to reach the quantum advantage regime in a specific computational model. Indeed, thanks to the implementation in photonics-based processors, the latest GBS experiments have reached a level of complexity where the quantum apparatus has solved the task faster than currently up-to-date classical strategies. In addition, recent studies have identified possible applications beyond the inherent sampling task. In particular, a direct connection between photon counting of a genuine GBS device and the number of perfect matchings in a graph has been established. In this work, we propose to exploit such a connection to benchmark GBS experiments. We interpret the properties of the feature vectors of the graph encoded in the device as a signature of correct sampling from the true input state. Within this framework, two approaches are presented. The first method exploits the distributions of graph feature vectors and classification via neural networks. The second approach investigates the distributions of graph kernels. Our results provide a novel approach to the actual need for tailored algorithms to benchmark large-scale Gaussian Boson Samplers.