**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.