Faster and improved validation algorithm for boson sampling using coarse graining.

Demonstrating quantum advantage using sampling has been a primary focus in the field of quantum information and computation over the last decade.The main criticism of many such proposals is the difficulty of validation. A validation protocol that is hard to spoof classically is essential. Recently, such a protocol was introduced for the boson sampling problem using coarse-graining by binning the modes Here, we propose a modification to the algorithm that increases its speed and also present various analytical and numerical evidence to analyze the effectiveness of this protocol. We show that the mode-binned probability distribution is sensitive to the way modes are grouped into bins. Since there are exponentially many ways to bin the modes, it becomes difficult to classically spoof without the prior knowledge of the binning strategy. We also propose a similar verification protocol for Gaussian Boson Sampling using the Hafnian Master Theorem. Additionally, we propose a modification to the algorithm using Non-Uniform Discrete Fourier Transform (NUDFT) that can speed up the algorithm by a factor of approximately O(N(B −1)!), where N is the number of photons and B is the number of bins. We find that the exact distribution is well separated from the samples with a random binning strategy, as well as the Haar-averaged distributions in total variation distance metric. This means that we can easily distinguish samples coming from a boson sampler and other classically efficient ways.