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

Applications of Gaussian boson sampling in graph theory

Naomi R. Solomons

Published May 1, 2024• 0 citations
OpenAlex

Related papers

Applications of Gaussian Boson Sampling to Solve Some Chemistry Problems

Samaneh Bagheri Novir

Quantum computers, due to their superposition and entanglement properties, provide significant advantages in solving certain problems compared with classical computers. Therefore, it is crucial to identify issues that can be efficiently solved by noisy intermediate-scale quantum (NISQ) systems. Xanadu has introduced the X8 quantum chip, based on integrated photonic technology, along with important photonic platforms such as Strawberry Fields and Gaussian Boson Sampling (GBS), to solve specific computational problems. In this review article, after reviewing Boson Sampling (BS) and Gaussian Boson Sampling (GBS), we discuss the relationship between GBS and graph theory, including how graphs can be encoded in GBS. Some applications of GBS, particularly molecular docking and molecular vibrations, are also considered. The future goal of this study is to identify problems that can be represented as small graphs and solved using GBS with a limited number of optical modes.

Quantum Reports•Nov 28, 2025•0 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•Quantum•Nov 21, 2025•1 citation

Experimental Gaussian Boson sampling

Han-Sen Zhong, Li-Chao Peng, Yuan Li +15 more

arXiv:1905.00170•中国科学通报:英文版•Apr 1, 2019•78 citations

Reducing the classical complexity of boson sampling via algebraic graph theory

Owen Doty

Bulletin of the American Physical Society•Mar 18, 2021•0 citations

Bipartite Gaussian Boson Sampling for Hamiltonian Cycles in Directed Graphs

Miaomiao Yu, Jingyi Lv, Yan Wang +2 more

Bipartite Gaussian boson sampling (BipartiteGBS) produces output probabilities governed by squared permanents of submatrices of arbitrary complex matrices, matching the nonsymmetric structure of directed graphs. Most GBS-based graph algorithms, however, rely on symmetric hafnian structure and are formulated for undirected problems. Here we propose a BipartiteGBS-based framework for directed-graph heuristic optimization. We introduce Max-Perm as a canonical optimization task for BipartiteGBS and derive a closed-form sampling enhancement factor relative to uniform classical sampling in this idealized setting. We then use permanent-biased BipartiteGBS samples to guide a genetic algorithm for the celebrated directed Hamiltonian cycle problem. Numerical experiments on Erdős--Rényi random directed graphs show that the resulting BipartiteGBS-enhanced algorithms improve success rates over a standard genetic algorithm and yield longer valid paths when no Hamiltonian cycle is found, while ablation tests indicate that BipartiteGBS-guided initialization is the dominant contributor. These results show how permanent-based photonic sampling can provide useful algorithmic guidance for asymmetric combinatorial search.

quant-pharXiv:2606.28775•Jun 30, 2026•0 citations

Using Gaussian Boson Sampling for dense subgraph finding with error

Naomi R. Solomons

•Jan 1, 2023•0 citations
Quantum computers, due to their superposition and entanglement properties, provide significant advantages in solving certain problems compared with classical computers. Therefore, it is crucial to identify issues that can be efficiently solved by noisy intermediate-scale quantum (NISQ) systems. Xanadu has introduced the X8 quantum chip, based on integrated photonic technology, along with important photonic platforms such as Strawberry Fields and Gaussian Boson Sampling (GBS), to solve specific computational problems. In this review article, after reviewing Boson Sampling (BS) and Gaussian Boson Sampling (GBS), we discuss the relationship between GBS and graph theory, including how graphs can be encoded in GBS. Some applications of GBS, particularly molecular docking and molecular vibrations, are also considered. The future goal of this study is to identify problems that can be represented as small graphs and solved using GBS with a limited number of optical modes.
Bipartite Gaussian boson sampling (BipartiteGBS) produces output probabilities governed by squared permanents of submatrices of arbitrary complex matrices, matching the nonsymmetric structure of directed graphs. Most GBS-based graph algorithms, however, rely on symmetric hafnian structure and are formulated for undirected problems. Here we propose a BipartiteGBS-based framework for directed-graph heuristic optimization. We introduce Max-Perm as a canonical optimization task for BipartiteGBS and derive a closed-form sampling enhancement factor relative to uniform classical sampling in this idealized setting. We then use permanent-biased BipartiteGBS samples to guide a genetic algorithm for the celebrated directed Hamiltonian cycle problem. Numerical experiments on Erdős--Rényi random directed graphs show that the resulting BipartiteGBS-enhanced algorithms improve success rates over a standard genetic algorithm and yield longer valid paths when no Hamiltonian cycle is found, while ablation tests indicate that BipartiteGBS-guided initialization is the dominant contributor. These results show how permanent-based photonic sampling can provide useful algorithmic guidance for asymmetric combinatorial search.