Complexity of simulating constant-depth BosonSampling

BosonSampling is a restricted model of quantum computation proposed recently, where a nonadaptive linear-optical network is used to solve a sampling problem that seems to be hard for classical computers. Here we show that, even if the linear-optical network has a constant number (greater than four) of beam splitter layers, the exact version of the BosonSampling problem is still classically hard, unless the polynomial hierarchy collapses to its third level. This is based on a similar result known for constant-depth quantum circuits and circuits of 2-local commuting gates (IQP).

Figure 1

The KLM scheme. (a) An arbitrary single-qubit gate, up to a global phase, on qubit Q. (b) A probabilistic two-qubit gate. Q1 and Q2 encode the qubits, ordered such that photons on the innermost modes correspond, respectively, to states ${|1\rangle }_L$ of each qubit. The two central modes are ancilla modes, initialized each with a single photon. If $\varphi \approx 17.{63}^{\circ }$ and $\theta \approx 54.{74}^{\circ }$, and one photon is measured in the output of each ancilla mode, the overall action of the circuit is a $cz$ gate.

Figure 2

(a) The brickwork graph state. (b) Representation of the MBQC protocol as a circuit. Dashed lines conceptually represent the dependence of some measurements based on the others. The color coding shows how, in the translation from (a) to (b), preparation of the state corresponds to only three rounds of $cz$ gates, while almost all of the temporal structure resides on the measurement adaptation.

Figure 3

(a) Standard gate teleportation in the quantum circuit model and its linear-optical version, where the two-mode state $\frac{1}{\sqrt{2}}\left(\right|01\rangle +|10\rangle )$ is mapped to the Fock basis by a balanced beam splitter. (b) The resulting constant-depth linear-optical circuit. Every beam splitter in this figure is balanced, and white rectangles represent phase shifters. Dashed lines represent the probabilistic $cz$ gates of the usual KLM scheme [i.e., the four central modes in Fig. 1], shown implicitly so as to not clutter the figure. The color coding is intended to aid in the mapping from the construction of Sec. 3: yellow regions represent state preparation, gray regions represent gate teleportation, and orange regions represent single-qubit measurements. The depth bottleneck of the model is seen here in the two central modes, each involved in four beam splitters (two explicit and two implicit).