Boson sampling with displaced single-photon Fock states versus single-photon-added coherent states: The quantum-classical divide and computational-complexity transitions in linear optics

Boson sampling is a specific quantum computation, which is likely hard to implement efficiently on a classical computer. The task is to sample the output photon-number distribution of a linear-optical interferometric network, which is fed with single-photon Fock-state inputs. A question that has been asked is if the sampling problems associated with any other input quantum states of light (other than the Fock states) to a linear-optical network and suitable output detection strategies are also of similar computational complexity as boson sampling. We consider the states that differ from the Fock states by a displacement operation, namely the displaced Fock states and the photon-added coherent states. It is easy to show that the sampling problem associated with displaced single-photon Fock states and a displaced photon-number detection scheme is in the same complexity class as boson sampling for all values of displacement. On the other hand, we show that the sampling problem associated with single-photon-added coherent states and the same displaced photon-number detection scheme demonstrates a computational-complexity transition. It transitions from being just as hard as boson sampling when the input coherent amplitudes are sufficiently small to a classically simulatable problem in the limit of large coherent amplitudes.