Experimentally finding dense subgraphs using a time-bin encoded Gaussian boson sampling device
Gaussian Boson Sampling (GBS) is a quantum computing concept based on drawing samples from a multimode nonclassical Gaussian state using photon-number resolving detectors. It was initially posed as a near-term approach aiming to achieve quantum advantage, but several applications have been proposed ever since, such as the calculation of graph features or molecular vibronic spectra, among others. For the first time, we use a time-bin encoded interferometer to implement GBS experimentally and extract samples to enhance the search for dense subgraphs in a graph. Our results indicate an improvement over classical methods for subgraphs of sizes three and four in a graph containing ten nodes. In addition, we numerically explore the role of imperfections in the optical circuit and on the performance of the algorithm.