  Multiphoton interference is an essential phenomenon at the very heart not
only of fundamental quantum optics and applications in quantum information
processing and sensing but also of demonstrations of quantum computational
supremacy in boson sampling experiments relying only on linear optical
interferometers. However, scalable boson sampling experiments with either
photon-number states or squeezed states are challenged by the need to generate
a large number of photons with fixed temporal and frequency spectra from one
experimental run to another. Unfortunately, even the well established standard
multiplexing techniques employed to generate photons with fixed spectral
properties are affected by the detrimental effects of losses, spectral
distorsions and reduction in purity. Here, we employ sampling correlation
measurements in the photonic inner modes, time and frequency, at the
interferometer input and output to ensure the occurrence of multiphoton
interference even with pure states of input photons with random spectral
overlap from one sample to another. Indeed, by introducing a random
multiplexing technique where photons are generated with random inner-mode
parameters, it is possible to substantially enhance the probability to
successfully generate samples and overcome the typical drawbacks in standard
multiplexing. Remarkably, we demonstrate the classical hardness of the
resulting problem of scattershot multiboson correlation sampling based on this
technique. Therefore, these results not only shed new light in the
computational complexity of multiboson interference but also allow us to
enhance the experimental scalability of boson sampling schemes with the
potential of future applications in quantum information processing and sensing
even beyond boson sampling.
