Evidence for the conjecture that sampling generalized cat states with linear optics is hard

Boson sampling has been presented as a simplified model for linear optical quantum computing. In the boson-sampling model, Fock states are passed through a linear optics network and sampled via number-resolved photodetection. It has been shown that this sampling problem likely cannot be efficiently classically simulated. This raises the question as to whether there are other quantum states of light for which the equivalent sampling problem is also computationally hard. We present evidence, without using a full complexity proof, that a very broad class of quantum states of light—arbitrary superpositions of two or more coherent states—when evolved via passive linear optics and sampled with number-resolved photodetection, likely implements a classically hard sampling problem.

Figure 1

The boson-sampling model for quantum computation. A series of single-photon and vacuum states are prepared, $|1,\cdots ,1,0,\cdots ,0\rangle$, and passed through a linear optics network, $\widehat{U}$. The experiment is repeated many times and each time the output distribution is measured via coincidence number-resolved photodetection, sampling from the distribution $P_S$.

Figure 2

The model for generalized boson sampling with superpositions of coherent states—cat states. The input state to each mode is an arbitrary superposition of coherent states, some of which are set to the vacuum. Following the application of a linear optics network, the distribution is sampled via number-resolved photodetection.