Threshold and Parity BosonSampling in the Linear-Mode Regime

Abstract:BosonSampling is among the most prominent candidates for demonstrating quantum advantage. However, while the hardness of BosonSampling relies on photon-number-resolving detection, many experimentally relevant settings and applications instead use binary readout based on threshold or parity measurements, whose computational complexity has not yet been rigorously characterized. In this work, we investigate the computational complexity of BosonSampling with threshold and parity measurements in the linear-mode regime, where the number of modes scales linearly with the number of photons and is most relevant to current experiments. In particular, we establish average-case #P-hardness of estimating typical output probabilities in threshold and parity BosonSampling, a crucial ingredient in proving the classical hardness of the corresponding sampling problems. The resulting imprecision bounds match those obtained in prior hardness results for standard photon-number-resolving BosonSampling in the linear-mode regime. The key technical ingredient is a Fourier-coefficient extraction method, induced by coherent beam-splitter rotations, that extracts hidden hard components within coarse-grained output probabilities. These results indicate that the hard output-probability structure of photon-number-resolving BosonSampling can persist under natural binary coarse-grainings, even in collision-dominant regimes.

arXiv:2608.24008 [quant-ph]

(or arXiv:2608.24008v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2608.24008 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.