BosonSampling with controllable distinguishability of photons

The BosonSampling Problem requires samples of output\r\nphoton-coincidence probability distributions for an interferometer\r\nwith either single photons or nothing injected into each input port\r\n[1]. This computational problem is classically hard to simulate as\r\nthese probabilities are weighted by permanents of sub-matrices of the\r\ninterferometer transition matrix yet the problem appears to be\r\nefficiently solvable just by doing the experiment. The classical\r\nhardness and quantum easiness of this problem makes it special in\r\nstudies of quantum computing because a demonstrable exponential\r\ncomputational speedup by quantum means would be evidence that the\r\nstrong Church-Turing thesis of computer science is false. Our\r\ninnovation [2,3,4] introduces distinguishability between photons by\r\ncontrolling arrival times of otherwise identical photons in order to\r\ntest the model, assess sampling errors and generalize BosonSampling\r\nbeyond permanent-weighted to immanant-weighted probabilities.\r\n