Using Gaussian boson sampling for dense subgraph identification

Naomi R. Solomons

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.

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.

Naomi R. Solomons

Shuo He, Boxuan Ai, Pengfei Gao +5 more

Gaussian Boson sampling (GBS) has emerged as a promising platform for demonstrating quantum computational advantage. Here, we apply GBS to address classically intractable graph problems in financial security. We demonstrate algorithms for: (1) Community structure analysis for market anomaly screening; (2) Synthetic identity fraud detection via hierarchical dense subgraph identification; (3) Collusive stock manipulation detection through clique enumeration; and (4) Anti-money laundering through isomorphic subgraph matching. Notably, we design non-universal time-domain-multiplexed photonic quantum circuits to effectively map these GBS-based algorithms with a quadratic reduction in hardware complexity, achieving over 99% fidelity in fitting the target unitary matrix. This spatial-temporal hybrid architecture and a hardware-algorithm co-design framework establish a promising approach to complex financial graph analytics. Our work bridges the fields of quantum computing and finance, highlighting GBS as a near-term solution to critical industry challenges.

Samaneh Bagheri Novir