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:1910.04022

A duality at the heart of Gaussian boson sampling

Kamil Brádler, Robert B. Israel, Maria Schuld, Daiqin Su

Published Oct 9, 2019• 2 citations
arXivHTMLPDF

Abstract

Gaussian boson sampling (GBS) is a near-term quantum computation framework that is believed to be classically intractable, but yet rich of potential applications. In this paper we study the intimate relation between distributions defined over classes of samples from a GBS device with graph matching polynomials. For this purpose, we introduce a new graph polynomial called the displaced GBS polynomial, whose coefficients are the coarse-grained photon-number probabilities of an arbitrary undirected graph $G$ encoded in a GBS device. We report a discovery of a duality between the displaced GBS polynomial of $G$ and the matching polynomial of $G\,\square\,P_2(x)$ - the Cartesian graph product of $G$ with a single weighted edge also known as the prism over $G$. Besides the surprising insight gained into Gaussian boson sampling, it opens the door for the new way of classically simulating the Gaussian boson sampling device. Furthermore, it motivates the recent success of a new type of coarse-grained quantum statistics used to construct feature maps in [Schuld et al. 2019].

DOI
10.48550/arxiv.1910.04022

Related papers

A complexity transition in displaced Gaussian Boson sampling

Zhenghao Li, Naomi R. Solomons, Jacob F. F. Bulmer +2 more

Abstract Gaussian Boson Sampling (GBS) is the problem of sampling from the output of photon-number-resolving measurements of squeezed states input to a linear optical interferometer. For purposes of demonstrating quantum computational advantage as well as practical applications, a large photon number is often desirable. However, producing squeezed states with high photon numbers is experimentally challenging. In this work, we examine the computational complexity implications of increasing the photon number by introducing coherent states. This displaces the state in phase space and as such we call this modified problem Displaced GBS. By utilising a connection to the matching polynomial in graph theory, we first describe an efficient classical algorithm for Displaced GBS when displacement is high or when the output state is represented by a non-negative graph. Then we provide complexity theoretic arguments for the quantum advantage of the problem in the low-displacement regime and numerically quantify where the complexity transition occurs.

npj Quantum Information•Jul 9, 2025•0 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

Simulating Gaussian boson sampling on graphs in polynomial time

Konrad Anand, Zongchen Chen, Mary Cryan +4 more

We show that a distribution related to Gaussian Boson Sampling (GBS) on graphs can be sampled classically in polynomial time. Graphical applications of GBS typically sample from this distribution, and thus quantum algorithms do not provide exponential speedup for these applications. We also show that another distribution related to Boson sampling can be sampled classically in polynomial time.

quant-pharXiv:2511.16558•Nov 21, 2025•0 citations

Measuring the similarity of graphs with a Gaussian boson sampler

Maria Schuld, Kamil Brádler, Robert Israel +2 more

Gaussian boson samplers (GBSs) have initially been proposed as a near-term demonstration of classically intractable quantum computation. We show here that they have a potential practical application: Samples from these devices can be used to construct a feature vector that embeds a graph in Euclidean space, where similarity measures between graphs---so-called graph kernels---can be naturally defined. This is crucial for machine learning with graph-structured data, and we show that the GBS-induced kernel performs remarkably well in classification benchmark tasks. We provide a theoretical motivation for this success, linking the extracted features to the number of $r$ matchings in subgraphs. Our results contribute to a new way of thinking about kernels as a quantum hardware-efficient feature mapping, and lead to a promising application for near-term quantum computing.

arXiv:1905.12646•Physical Review A•Mar 11, 2020•92 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

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 (GBS) is a near-term quantum computation framework that is believed to be classically intractable, but yet rich of potential applications. In this paper we study the intimate relation between distributions defined over classes of samples from a GBS device with graph matching polynomials. For this purpose, we introduce a new graph polynomial called the displaced GBS polynomial, whose coefficients are the coarse-grained photon-number probabilities of an arbitrary undirected graph GGG encoded in a GBS device. We report a discovery of a duality between the displaced GBS polynomial of GGG and the matching polynomial of G □ P2(x)G\,\square\,P_2(x)G□P2​(x) - the Cartesian graph product of GGG with a single weighted edge also known as the prism over GGG. Besides the surprising insight gained into Gaussian boson sampling, it opens the door for the new way of classically simulating the Gaussian boson sampling device. Furthermore, it motivates the recent success of a new type of coarse-grained quantum statistics used to construct feature maps in [Schuld et al. 2019].
Abstract Gaussian Boson Sampling (GBS) is the problem of sampling from the output of photon-number-resolving measurements of squeezed states input to a linear optical interferometer. For purposes of demonstrating quantum computational advantage as well as practical applications, a large photon number is often desirable. However, producing squeezed states with high photon numbers is experimentally challenging. In this work, we examine the computational complexity implications of increasing the photon number by introducing coherent states. This displaces the state in phase space and as such we call this modified problem Displaced GBS. By utilising a connection to the matching polynomial in graph theory, we first describe an efficient classical algorithm for Displaced GBS when displacement is high or when the output state is represented by a non-negative graph. Then we provide complexity theoretic arguments for the quantum advantage of the problem in the low-displacement regime and numerically quantify where the complexity transition occurs.
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.
Gaussian boson samplers (GBSs) have initially been proposed as a near-term demonstration of classically intractable quantum computation. We show here that they have a potential practical application: Samples from these devices can be used to construct a feature vector that embeds a graph in Euclidean space, where similarity measures between graphs---so-called graph kernels---can be naturally defined. This is crucial for machine learning with graph-structured data, and we show that the GBS-induced kernel performs remarkably well in classification benchmark tasks. We provide a theoretical motivation for this success, linking the extracted features to the number of rrr matchings in subgraphs. Our results contribute to a new way of thinking about kernels as a quantum hardware-efficient feature mapping, and lead to a promising application for near-term quantum computing.
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 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.