Sample space filling analysis for boson sampling validation

Abstract

Achieving a quantum computational advantage regime, and thus providing evidence against the extended Church-Turing thesis, remains one of the key challenges of modern science. Boson sampling seems to be a very promising platform in this regard, but to be confident of attaining the advantage regime, one must provide evidence of operating with a correct boson sampling distribution, rather than with a pathological classically simulatable one. This problem is often called the validation problem, and it poses a major challenge to demonstrating unambiguous quantum advantage. In this work, using the recently proposed wave function network approach, we study the sample space filling behavior with increasing the number of collected samples. We show that due to the intrinsic nature of the boson sampling wave function, its filling behavior can be computationally efficiently distinguished from classically simulated cases. Therefore, we propose a new validation protocol based on the sample space filling analysis and test it for problems of up to $20$ photons injected into a $400$-mode interferometer. Due to its simplicity and computational efficiency, it can be used among other protocols to validate future experiments to provide more convincing results.

References in corpus (30)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum computational advantage using photons
• Boson Sampling on a Photonic Chip
• Experimental Boson Sampling
• Experimental boson sampling in arbitrary integrated photonic circuits
• Photonic Boson Sampling in a Tunable Circuit
• Gaussian Boson Sampling
• 12-photon entanglement and scalable scattershot boson sampling with optimal entangled-photon pairs from parametric down-conversion
• Efficient experimental validation of photonic boson sampling against the uniform distribution
• Boson Sampling from Gaussian States
• Experimental Scattershot Boson Sampling
• Generation and sampling of quantum states of light in a silicon chip
• On the experimental verification of quantum complexity in linear optics
• BosonSampling with single-photon Fock states from a bright solid-state source
• No imminent quantum supremacy by boson sampling
• Scalable boson sampling with a single-photon device
• Sufficient Conditions for Efficient Classical Simulation of Quantum Optics
• Toward Scalable Boson Sampling with Photon Loss
• Stringent and efficient assessment of Boson-Sampling devices
• A Statistical Benchmark for BosonSampling
• Experimental statistical signature of many-body quantum interference
• Universality of Generalized Bunching and Efficient Assessment of Boson Sampling
• Pattern recognition techniques for Boson Sampling validation
• Experimental generalized quantum suppression law in Sylvester interferometers
• Distinguishing noisy boson sampling from classical simulations
• Wave function network description and Kolmogorov complexity of quantum many-body systems
• A certification scheme for the boson sampler
• Certification of Gaussian Boson Sampling via graph theory
• Benchmarking a boson sampler with Hamming nets