Abstract
Boson-sampling has attracted much interest as a simplified approach to implementing a subset of optical quantum computing. Boson-sampling requires indistinguishable photons, but far fewer of them than universal optical quantum computing architectures. In reality, photons are never indistinguishable, and exhibit a rich spectral structure. Here we consider the operation of boson-sampling with photons of arbitrary spectral structure and relate the sampling statistics of the device to matrix permanents. This sheds light on the computational complexity of different regimes of the photons' spectral characteristics, and provides very general results for the operation of linear optics interferometers in the presence of partially distinguishable photons. Our results apply to both the cases of spectrally resolving and non-spectrally resolving detectors.