Photonic Boson Sampling in a Tunable Circuit

TLDR

Quantum computers are unnecessary for exponentially‑efficient computation if the Extended Church‑Turing thesis holds; the thesis would be contradicted by a device that efficiently performs BosonSampling, which samples the distribution of n bosons scattered by a linear‑optical unitary process. The study tests BosonSampling by experimentally verifying that 3‑photon scattering amplitudes are given by permanents of submatrices from a 6‑mode integrated optical circuit, with the goal of providing strong evidence against the Extended Church‑Turing thesis by scaling to larger photon numbers. The experiment employs a 6‑mode integrated optical circuit to generate a unitary, from which submatrix permanents predict 3‑photon scattering amplitudes that are measured. The protocol proved robust, accurately reproducing the predicted amplitudes despite photon loss, imperfect sources, and detection inefficiencies.

Abstract

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 BosonSampling: obtaining a distribution of n bosons scattered by some linear-optical unitary process. Here we test the central premise of 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.