Quantum computers are unnecessary for exponentially-efficient computation or simulation if the Extended Church-Turing thesis---a foundational tenet of computer science---is correct. The thesis would be directly contradicted by a physical device that efficiently performs a task believed to be intractable for classical computers. Such a task is \textsc{BosonSampling}: obtaining a distribution of $n$ bosons scattered by some linear-optical unitary process. Here we test the central premise of \textsc{BosonSampling}, experimentally verifying that the amplitudes of 3-photon scattering processes are given by the permanents of submatrices generated from a unitary describing a 6-mode integrated optical circuit. We find the protocol to be robust, working even with the unavoidable effects of photon loss, non-ideal sources, and imperfect detection. Strong evidence against the Extended-Church-Turing thesis will come from scaling to large numbers of photons, which is a much simpler task than building a universal quantum computer.
–
Authors
Andrew White
University of Queensland, ARC Centre for Engineered Quantum Systems, School of Mathematics and Physics, University of Queensland, Brisbane, Australia
Matthew Broome
University of Queensland, ARC Centre for Engineered Quantum Systems, School of Mathematics and Physics, University of Queensland, Brisbane, Australia
Alessandro Fedrizzi
University of Queensland, ARC Centre for Engineered Quantum Systems, School of Mathematics and Physics, University of Queensland, Brisbane, Australia
Saleh Rahimi-Keshari
University of Queensland
Timothy Ralph
University of Queensland, ARC Centre for Quantum Computer and Communication Technology, School of Mathematics and Physics, University of Queensland, Brisbane, Australia
