A duality at the heart of Gaussian boson sampling
arXiv:1910.04022
Abstract
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 encoded in a GBS device. We report a discovery of a duality between the displaced GBS polynomial of and the matching polynomial of - the Cartesian graph product of with a single weighted edge also known as the prism over . 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].
References in corpus (10)
- Gaussian Boson Sampling
- Boson Sampling for Molecular Vibronic Spectra
- Boson Sampling from Gaussian States
- A detailed study of Gaussian Boson Sampling
- Using Gaussian Boson Sampling to Find Dense Subgraphs
- Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
- Gaussian Boson Sampling for perfect matchings of arbitrary graphs
- What can quantum optics say about computational complexity theory?
- Graph isomorphism and Gaussian boson sampling
- An efficient tree decomposition method for permanents and mixed discriminants