Quantum Computational Advantage of Noisy Boson Sampling with Partially Distinguishable Photons

Boson sampling stands out as a promising approach toward experimental demonstration of quantum computational advantage. However, the presence of physical noise in near-term experiments hinders the realization of quantum computational advantage with boson sampling. Since physical noise in near-term boson-sampling devices is inevitable, precise characterization of the boundary of noise rates where the classical intractability of boson sampling is maintained is crucial for quantum computational advantage using near-term devices. In this work, we identify the level of partial-distinguishability noise that upholds the classical intractability of boson sampling. We find that boson sampling with on average <a:math xmlns:a="http://www.w3.org/1998/Math/MathML" display="inline"><a:mi>O</a:mi><a:mo stretchy="false">(</a:mo><a:mi>log</a:mi><a:mo></a:mo><a:mi>N</a:mi><a:mo stretchy="false">)</a:mo></a:math> distinguishable photons out of <e:math xmlns:e="http://www.w3.org/1998/Math/MathML" display="inline"><e:mi>N</e:mi></e:math> input photons maintains the equivalent complexity to the ideal boson-sampling case. By providing strong complexity-theoretical evidence for the classical intractability of noisy boson sampling, we expect that our findings will ultimately facilitate the demonstration of quantum computational advantage with noisy boson-sampling experiments in the near future.