Boson sampling with photon-added coherent states

Boson sampling is a simple and experimentally viable model for non-universal linear optics quantum computing. Boson sampling has been shown to implement a classically hard algorithm when fed with single photons. This raises the question as to whether there are other quantum states of light that implement similarly computationally complex problems. We consider a class of continuous variable states---photon-added coherent states---and demonstrate their computational complexity when evolved using linear optical networks and measured using photodetection. We find that, provided the coherent state amplitudes are upper bounded by an inverse polynomial in the size of the system, the sampling problem remains computationally hard.