BosonSampling with non-simultaneous photons

Quantum computing aims to transform certain classically hard computational problems into easy-to-solve problems by using the resources of quantum computation, but onerous space and time resources are required to answer problem instances beyond the reach of current classical computational capability. The BosonSampling problem introduces a new paradigm to quantum computing by seeking efficient sampling of a distribution of matix transformations, weighted by the submatrix permanents. Scaling current photon interferometer technology to dozens of photons in more than double the number of interferometric channels puts this form of quantum computing within reach of violating the extended Church thesis of computer science for the first time. This thesis will be falsified empirically if a quantum computer, even a problem-specific purpose-built system such as photonic interferometery that eschews quantum bits and quantum gates, solves a computational problem efficiently in a case where classical computing is believed not to solve the same problem efficiently. We review the BosonSampling problem and recent dramatic experimental successes to realize the system for few photons. Then we discuss the importance and unavoidability of non-simultaneity of photon arrivals and how we propose using photon-arrival statistics parametrized by delay times to characterize inteferometers and sample with respect to submatrix immanants rather than submatrix permanents. Our work shows that non-simultaneity is a strength rather than a weakness in interferometric BosonSampling.