title: Boson sampling from a Gaussian state.
abstract: We pose a randomized boson-sampling problem. Strong evidence exists that such a problem becomes intractable on a classical computer as a function of the number of bosons. We describe a quantum optical processor that can solve this problem efficiently based on a Gaussian input state, a linear optical network, and nonadaptive photon counting measurements. All the elements required to build such a processor currently exist. The demonstration of such a device would provide empirical evidence that quantum computers can, indeed, outperform classical computers and could lead to applications.
authors.affiliation: Centre for Quantum Computation and Communication Technology, School of Mathematics and Physics, University of Queensland, Brisbane, Queensland 4072, Australia.
authors.forename: A P
authors.initials: AP
authors.lastname: Lund
authors.affiliation: Centre for Quantum Photonics, H. H. Wills Physics Laboratory and Department of Electrical and Electronic Engineering, University of Bristol, Bristol BS8 1UB, United Kingdom.
authors.forename: A
authors.initials: A
authors.lastname: Laing
authors.affiliation: Centre for Quantum Computation and Communication Technology, School of Mathematics and Physics, University of Queensland, Brisbane, Queensland 4072, Australia.
authors.forename: S
authors.initials: S
authors.lastname: Rahimi-Keshari
authors.affiliation: Optics Section, Blackett Laboratory, Imperial College London, London SW7 2AZ, United Kingdom.
authors.forename: T
authors.initials: T
authors.lastname: Rudolph
authors.affiliation: Centre for Quantum Photonics, H. H. Wills Physics Laboratory and Department of Electrical and Electronic Engineering, University of Bristol, Bristol BS8 1UB, United Kingdom.
authors.forename: J L
authors.initials: JL
authors.lastname: O'Brien
authors.affiliation: Centre for Quantum Computation and Communication Technology, School of Mathematics and Physics, University of Queensland, Brisbane, Queensland 4072, Australia.
authors.forename: T C
authors.initials: TC
authors.lastname: Ralph