Abstract

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 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.