Practical Applications of Gaussian Boson Sampling

We investigate the feasibility of using a quantum-inspired Gaussian boson sampler (GBS) to demonstrate practical advantage for certain problems. Originally theorized to show quantum advantage, practical applications have since been identified in the fields of optimization, drug discovery, molecular chemistry and more. These applications usually map to NP-Hard graph problems, which, using an Autonne-Takagi decomposition, we are able to encode into GBS setups. Through this process, taking a sample is akin to sampling from the probability distribution of the hafnian of the adjacency matrix of the graph, resulting in a direct sample of nodes from the graph. We specifically explored the usage of GBS algorithms for densest k-subgraph, maximum weighted clique, and graph classification. We observed that GBS-sampled subgraphs have a higher average density than those which are randomly sampled, and the Charikar resizing heuristic for densest k-subgraph converges faster using the GBS sampled seeds. We similarly demonstrated improved performance using GBS seeds for the weighted maximum clique problem. Additionally, our simulation proved to be viable for generating graph similarity kernels competitive with current state-of-the-art classical algorithms for graph classification.