Applications of Gaussian Boson Sampling to Solve Problems, Especially Graph-Based Problems

Naomi R. Solomons

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.

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

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

Mehrdad Ghasemi, Hassan Kaatuzian, Houshyar Noshad +3 more

Gaussian boson sampling (GBS) is a tool for demonstrating quantum computational utilities and also exhibits mathematical connections to specific graph-related and quantum chemistry problems. It has been suggested that the samples generated from GBS could be utilized to improve stochastic algorithms in searching for certain graph features. In this study, we employed X8, a noisy intermediate-scale quantum computer, to address graph problems. The samples were produced from a 4-mode quantum photonic processor. This research represents a step toward analyzing Gaussian boson sampling as a tool for solving real-world problems using existing noisy intermediate-scale quantum computers and aims to encourage the development of quantum algorithms.