Equivalence between spin Hamiltonians and boson sampling

Aaronson and Arkhipov showed that predicting or reproducing the measurement statistics of a general linear optics circuit with a single Fock-state input is a classically hard problem. Here we show that this problem, known as boson sampling, is as hard as simulating the short time evolution of a large but simple spin model with long-range $XY$ interactions. The conditions for this equivalence are the same for efficient boson sampling, namely, having a small number of photons (excitations) as compared to the number of modes (spins). This mapping allows efficient implementations of boson sampling in small quantum computers and simulators and sheds light on the complexity of time evolution with critical spin models.

Figure 1

(a) A setup that consists of beam splitters and free propagation implements boson sampling if the input state has a fixed number of single photons on each port (red wiggles). (b) We can regard those photons as arising from the spontaneous emission of two-level systems onto the circuit (up spins), which after propagation map onto other two-level systems at the end, via the unitary matrix $R$.

Figure 2

The distance between the full bosonic state $|\varphi \left(t\right)\rangle$ and the state approximated with spins, $|\psi \left(t\right)\rangle$, is covered by two error vectors: one $|\delta \rangle$ that lives in the hard-core-boson space (red dashed line) and another one that covers the distance between the projected state $Q|\varphi \left(t\right)\rangle$ and the full boson state, $|\varphi \rangle$ (black dashed line).

Figure 3

Numerical estimates of the norm $\parallel Q{H}_{\text{BS}}{P}_{1\text{bpair}}{\parallel }_2$ as a function of the number of bosonic modes, $M$, for different number of excitations, $N$.