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

Displaced Gaussian Boson Sampling for enhanced max-clique search

Ewan Mer, Zhenghao Li, Shang Yu, Ian A. Walmsley, Raj B. Patel

quant-phSubmitted May 26, 2026• Announced May 28, 2026• 1 citation
arXivHTMLPDF

Abstract

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.

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•144 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

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•3 citations

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•1 citation

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•18 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•68 citations
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.
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.
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.
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.
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.
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 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.