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.
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□P2(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].