Experimental boson sampling

Universal quantum computers(1) promise a dramatic increase in speed over classical computers, but their full-size realization remains challenging(2). However, intermediate quantum computational models(3-5) have been proposed that are not universal but can solve problems that are believed to be classically hard. Aaronson and Arkhipov(6) have shown that interference of single photons in random optical networks can solve the hard problem of sampling the bosonic output distribution. Remarkably, this computation does not require measurement-based interactions(7,8) or adaptive feed-forward techniques(9). Here, we demonstrate this model of computation using laser-written integrated quantum networks that were designed to implement unitary matrix transformations. We characterize the integrated devices using an in situ reconstruction method and observe three-photon interference(10-12) that leads to the boson-sampling output distribution. Our results set a benchmark for a type of quantum computer with the potential to out-perform a conventional computer through the use of only a few photons and linear-optical elements(13).