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.

Figure 1

When a coherent state and a single-photon state are mixed on a highly reflective beam splitter, and no photon is detected in the transmitted mode, a SPACS is heralded in the transmitted mode.

Figure 2

Wigner function of a SPACS (left) and a coherent state (right), with amplitude ${\left|\alpha \right|}^2=0.01$. The former is seen to take negative values close to the phase-space origin, while that of the latter are strictly positive everywhere. $W\left(0\right)$ is at the center of the plane. Sampling $W\left(0\right)$ would distinguish between a coherent state and a SPACS.

Figure 3

Two-dimensional slices of the Wigner function of SPACS across its major axis, as a function of the coherent amplitude $\left|\alpha \right|$. We see that the negativity vanishes, and the shape tends towards being a Gaussian for increasing values of $\left|\alpha \right|$.